算法中的运算次数方法

有多种方法可以估计某个算法的成本。其中一种方法是使用运算次数。我们可以通过选择不同的运算之一来估计算法的时间复杂度。例如加法、减法等。我们必须检查执行了多少次这些运算。这种方法的成功取决于我们识别出对时间复杂度贡献最大的运算的能力。

假设我们有一个大小为 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+ 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习