带If的嵌套For循环的时间复杂度 [英] Time Complexity of Nested For Loop with If

问题描述

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语句执行的次数:总和i = 1到n(theta(1)).

My thinking process: number of times execute if statement: sum i=1 to n (theta(1)).

在以下情况下执行内部事物的次数:总和i = 1到sqrt(n)(用于循环)

number of times execute things inside if: sum i=1 to sqrt(n) (for loop)

执行循环的次数:和k = 0到i ^ 3(theta(1))= i ^ 3

number of times execute for loops: sum k=0 to i^3 (theta(1)) = i^3

这将给我:theta(n)+和i = 0到sqrt(n)(theta(i ^ 3))= theta(n)+ theta(n ^ 2)

This will give me: theta(n) + sum i=0 to sqrt(n) (theta(i^3)) = theta(n) + theta(n^2)

这给了我theta(n ^ 2)

which gives me theta(n^2)

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

The answer key he gave is theta(n^3.5)

我只是想知道我在思考过程中是否犯了任何错误.我已经问过我的教授两次关于这个问题.只想看看是否有什么我没看见的东西，然后再打扰他..谢谢！

I am just wondering if i made any mistake on my thinking process. I have asked my professor twice about this question. Just want to see if there is anything I didn't see before I bother him again.. Thanks!

推荐答案

使用Sigma表示法，我想出了确切的封闭形式.

Using Sigma notation, I came up with the exact closed-form.

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

Besides, the formula below assumes the process, which doesn't verify the condition that executes the innermost loop, is negligible.

由于地板功能和平方根等因素，取决于您确定增长边界的紧密顺序.

It's up to you to determine tight order of growth bounds, because of flooring function and square root etc.

此处的更多详细信息: https://math .stackexchange.com/questions/1840414/summary-with-floor-and-square-root-functions-tight-bounds

Further details here: https://math.stackexchange.com/questions/1840414/summation-with-floor-and-square-root-functions-tight-bounds

这篇关于带If的嵌套For循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！