Python算法分析

Question

确定确切的次数 BigFn() 被调用。

for i in range(1,N+1):
   for j in range(1,N*N+1):
      myList[i][j] = BigFn(i,j)

这是我的猜测。

for i in range(1,N+1): # N times
   for j in range(1,N*N+1): # N^2 times
      myList[i][j] = BigFn(i,j) #Here is where I don't know what to do...?

我如何找出最佳和最坏情况下的行为？

提前致谢!

Answer 1

您的猜测是正确的，bigFn() 被调用了 O(n³) 次。正如你所说:

for i in range(1,N+1): # N times
   for j in range(1,N*N+1): # N^2 times

所以基于rule of product , BigFn() 被调用了 O(n³) 次。