基于异构多核处理器的静态任务调度研究（一）

务被映射到处理器上的时间复杂度为O (kp)，k为每层的任务数量，p为处理器的数量，冗余任务处理的时间复杂度为O (k2)，将所有任务映射到处理器上并完成调度结果优化所需的时间复杂度为O (kpm+k2 m)，m 为任务DAG图的层数，其在最坏情况下等于任务数量v.

图3　任务到处理器映射阶段流程

综上所述，WPTS算法的时间复杂度为O (v+e)+O(n+e)+O (n2)+O (kpm+k2 m)，即O (v3)，算法没有提高时间复杂度，且能有效处理使用任务复制技术带来的冗余任务，减少任务的调度长度，避免处理器资源的浪费。