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个部分(比较,赋值,递增)
如果我的观察结果不正确,请随时纠正我
发布于 2012-01-29 04:02:07
不,这可能是不正确的。
首先:你想得太多了。至少对于Big-O计算而言,您可能可以将每个赋值视为单个操作,而不管它是常量赋值还是计算值。
其次:你的思考还不够认真。第四行是一个单独的操作,但是它是运行n * n时间,所以它应该被算作n^2,而不是1。循环中的其他行也是如此。
https://stackoverflow.com/questions/9048089
复制相似问题