algorithm - 嵌套 For 循环的运行时间

Question

我必须找到以下函数的运行时间。

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 值，但我似乎无法弄清楚这一点。

有什么建议吗？或者其他方法来解决这个问题？

Answer 1

使用 Sigma 表示法是正式提出算法增长顺序的有效方法: