演算法中的運算次數方法

有多種方法可以估計某個演算法的成本。其中一種方法是使用運算次數。我們可以透過選擇不同的運算之一來估計算法的時間複雜度。例如加法、減法等。我們必須檢查執行了多少次這些運算。這種方法的成功取決於我們識別出對時間複雜度貢獻最大的運算的能力。

假設我們有一個大小為 n（0 到 n - 1）的陣列。我們的演算法將找到最大元素的索引。我們可以透過計算陣列中每對元素之間執行的比較運算次數來估計成本。我們必須記住，我們只選擇一個運算。在這個演算法中，還有其他一些運算，例如迭代變數 i 的增量，或為索引賦值等。但在這種情況下，它們不被考慮。

演算法

getMax(arr, n):
   index := 0
   max := arr[0]
   for i in range 1 to n - 1, do
      if arr[i] > max, then
         max := arr[i]
         index := i
      end if
   done
   return index

為了估計成本，我們必須選擇那些執行次數最多的運算。假設我們有一個氣泡排序演算法，並且我們計算交換運算的次數。然後我們必須記住它將在何時達到最大值。這將在分析過程中給我們提供最大結果。

Arnab Chakraborty

更新於： 2020年8月10日

3K+ 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習