算法复杂度

所有算法都是解决问题的步骤列表。每个步骤都依赖于某些先前步骤或算法的开始。一个小问题可能如下所示：

该结构称为有向无环图，或简称为 DAG。图中每个节点之间的链接表示操作顺序的依赖关系，图中没有循环。

依赖如何发生？以下面的代码为例：

total = 0
for(i = 1; i < 10; i++)
    total = total + i

在这个伪代码中，for 循环的每次迭代都依赖于前一次迭代的结果，因为我们在下一次迭代中使用了前一次迭代中计算的值。此代码的 DAG 可能如下所示：

如果你了解算法的这种表示，你可以使用它来了解算法复杂性的工作和跨度。

工作

工作是为了实现给定输入大小 n 的算法目标而需要执行的实际操作数。

跨度

跨度有时被称为关键路径，并且是算法必须达到的最少步数才能实现算法的目标。

下图突出显示了示例 DAG 上工作和跨度之间差异的图表。

工作是整个图中节点的数量。这由左上方的图表表示。跨度是关键路径，或从开始到结束的最长路径。当工作可以并行完成时，右侧的黄色突出显示的节点表示跨度，所需的步骤数最少。当工作必须连续进行时，跨度与工作相同。

工作和跨度都可以在分析方面独立评估。算法的速度由跨度决定。所需的计算能力量由工作决定。