演算法複雜度

所有演算法都是解決問題的步驟列表。每個步驟都依賴於某些先前步驟或演算法的開始。一個小問題可能如下所示：

該結構稱為有向無環圖，或簡稱為 DAG。圖中每個節點之間的連結表示操作順序的依賴關係，圖中沒有迴圈。

依賴如何發生？以下面的程式碼為例：

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

在這個虛擬碼中，for 迴圈的每次迭代都依賴於前一次迭代的結果，因為我們在下一次迭代中使用了前一次迭代中計算的值。此程式碼的 DAG 可能如下所示：

如果你瞭解演算法的這種表示，你可以使用它來了解演算法複雜性的工作和跨度。

工作

工作是為了實現給定輸入大小 n 的演算法目標而需要執行的實際運算元。

跨度

跨度有時被稱為關鍵路徑，並且是演算法必須達到的最少步數才能實現演算法的目標。

下圖突出顯示了示例 DAG 上工作和跨度之間差異的圖表。

工作是整個圖中節點的數量。這由左上方的圖表表示。跨度是關鍵路徑，或從開始到結束的最長路徑。當工作可以並行完成時，右側的黃色突出顯示的節點表示跨度，所需的步驟數最少。當工作必須連續進行時，跨度與工作相同。

工作和跨度都可以在分析方面獨立評估。演算法的速度由跨度決定。所需的計算能力量由工作決定。