Sum <- 0  // 1 Operation
for i <- 1 to n do // 2n operations
 for j <-1 to n do // 2(n-1) operations
  k <-1 // 1 operation
while k < n do // n-1 operations
k <- k *c // 2 operations
sum <- sum +1  // 2 operations


该代码中的操作总数为:

1 + 2n + 2(n-1)+1+(n-1)+ 2 + 2 == 5n + 3个操作总数,

这是您如何计算它的,因为我理解每个stmt的概念都有3个部分(比较,赋值,增量)

请随时纠正我,因为我的观察不正确

最佳答案

不,那可能不正确。

首先:您想得太辛苦了。至少出于Big-O计算的目的,您可以将每个赋值视为一个单独的操作,而不管它是常量赋值还是计算值。

第二:您没有认真思考。第四行是单个操作,但是它运行了n * n次,因此应计为n^2,而不是1。对于循环中的其他行类似。

10-08 00:35