-1

我的一项家庭作业的解决方案刚刚发布，我有一个问题错误。它涉及找到算法执行乘法运算的最坏情况次数（T（n））。

function power2n(n)
  counter = n
  product = 1
  while (counter > 0) {
    product = product * n * n
    counter = counter - 1
  }
  return product

据我的老师说，最坏的情况是2n，但我不明白为什么..

4

1 回答 1

3

观察变量counter。它是如何变化的？它最初是n，然后在循环的每次迭代中减 1，因此我们知道循环将准确执行n次数。

现在，执行了多少次乘法？

我们确定每个循环有 2 次乘法（n*n*product）。

所以总体上将执行 n*(2) = 2n 次乘法。在大 O 表示法中，这仍然是 O(n)

于 2013-10-23T18:22:52.233 回答