演算法中的步數法

步數法是分析演算法的一種方法。在這種方法中，我們計算一條指令執行的次數。由此，我們將嘗試找到演算法的複雜度。

假設我們有一個演算法來執行順序搜尋。假設每條指令執行需要 c1、c2、…… 的時間，那麼我們將嘗試找出該演算法的時間複雜度。

現在，如果我們透過將執行次數乘以代價來累加代價（考慮最壞情況），我們將得到

                  代價=c1+(n+1)c 2+nc3+c 4+c 5

                  代價=c1+nc 2+c2+nc 3+c 4+c5

                  代價=n(c 2+c3)+c 1+c 4+c5

                  代價=n(c 2+c3)+C

考慮到 c1 + c4 + c5 為 C，因此最終方程類似於直線 y = mx + b。因此，我們可以說該函式是線性的。複雜度將為 O(n)。

Arnab Chakraborty

更新於： 2019年8月27日

9K+ 瀏覽量

啟動您的 職業生涯

透過完成課程獲得認證

開始