我必须找到以下函数的运行时间。
S=0
For i=4 to n^2
For j=5 to 3*i*log(i)
S=S+i-j
Return S
到目前为止我相信运行时间 T(n)=((n^2)-3)*(3*i*log(i)-4) 但我无法得到第二部分以 n 表示。我还发现它的最大值或大 O 符号是 ((n^2)-3)(3(n^2)*log(n^2 )) 也就是说,如果 n^2 是 i 对于通过内部循环的每次迭代的值,但事实并非如此,这基本上告诉我它可以写成 O((n^4)*log(n^2))。为了找出大的 theta 值,我一直在尝试计算 3*i*log(i) 的平均值,以用作每次迭代的 i 值,但我似乎无法弄清楚这一点。
有什么建议吗?或者其他方法来解决这个问题?
最佳答案
使用 Sigma 表示法是正式提出算法增长顺序的有效方法:
关于algorithm - 嵌套 For 循环的运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22200958/