c++ - 带 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))。

if: sum i=1 to sqrt(n) (for loop) 在里面执行东西的次数

执行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

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

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

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

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