2

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

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

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

4

1 回答 1

1

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

在此处输入图像描述

于 2014-03-14T21:52:46.763 回答