带 If 的嵌套 For 循环的时间复杂度

Question

void f(int n)
{
  for(int i =1; i<=n; i++){
    if(i % (int)sqrt(n)==0){
      for(int k=0; k< pow(i,3); k++){
        //do something
      }
    }
  }
}

我的思考过程：执行 if 语句的次数：sum i=1 to n (theta(1)).

如果：sum i=1 to sqrt(n)（for 循环）

执行for循环的次数：sum k=0 to i^3 (theta(1)) = i^3

这会给我：theta(n) + sum i=0 to sqrt(n) (theta(i^3)) = theta(n) + theta(n^2)

这给了我 theta(n^2)

他给出的答案是theta(n^3.5)

我只是想知道我的思考过程是否有任何错误。关于这个问题，我已经问过我的教授两次。就是想看看有没有什么我没看到的再打扰他。。谢谢！

Answer 1

void f(int n) {   
  for(int i =1; i<=n; i++){     //---   n times
    if(i % (int)sqrt(n)==0){    // ---  2 times (constant)
      for(int k=0; k< pow(i,3); k++){  // sqrt(n)^3 and n^3 times
        //do something
      }
    }   
  } 
}

Taking the highest order term it should be Theta(n^3)

Assuming do something is constant

c = do somrthing + plus running cost of single iteration of inner loop

a = runnning cost of running single iteration of outer most loop

b = running cost of if block Thinking more about it cn^3/2 + cn^3 + a*n + b*2)

Taking the highest order term Theta(n^3) or since c is same coefficient for both the n^3 and n^3/2 we can reduce it

= cn^3 + cn^3/2

= cn^3(n^1/2+1)

~ cn^3 * n^1/2

= cn^3.5

Answer 2

使用 Sigma 表示法，我得出了精确的封闭形式。

此外，下面的公式假设不验证执行最内层循环的条件的过程可以忽略不计。

由于地板功能和平方根等，您可以确定增长界限的严格顺序。

这里有更多详细信息：https://math.stackexchange.com/questions/1840414/summation-with-floor-and-square-root-functions-tight-bounds

带 If 的嵌套 For 循环的时间复杂度

Time Complexity of Nested For Loop with If

c++

big-o

loops

runtime

time-complexity