algorithm - 算法的最佳和最坏情况运行时间

Question

我需要计算以下算法的最佳和最差情况下的运行时间。我的问题是我需要在第二个循环中考虑 i*i 吗？并获得该循环的复杂性作为 Q(N^2)？

    for i=1 to 2*n do
       for j=1 to i*i do
          for k=1 to k<j do
             if j%i==0 then
                 sum=sum+1;

这是完整的代码

    procedure proc(n:integer){
    var i,j,k :integer
    var sum: integer
   begin
 sum=0;
 for i=1 to 2*n do
 begin
       for j=1 to i*i do
       begin 
              for k=1 to k<j do
              begin
                       if j%i==0 then
                       sum=sum+1;
                       end if
                       k=k+1;
    end
   j=j+1;
  end 
 i=i+i;
 end
 end }

Answer 1

让我们从内到外分析一下。

         if j%i==0 then
             sum=sum+1;

每次到达都需要常数时间。

      for k=1 to k<j do

最内层的循环运行 O(j) 次，从 1 到 j(不包括)的每个 k 值都运行一次。到目前为止，我们有 O(j*1) = O(j)

   for j=1 to i*i do

对于中间循环 - j 的每个值都必须以 O(j) 的复杂度完成工作。这意味着，您将需要整个循环(对于 i 的每个值):

1 + 2 + .... + i*i = i*i*(i*i+1)/2 = i^2(i^2+1)/2  [sum of arithmetic progression]

以上是O(i^4)

for i=1 to 2*n do

总和{i^2*(i^2+1)/2 |我从 1 到 2n which is in O(n^5)