如果下面有for循环:

for(k = 1; k <= n; ++k){
    for(j = 1; j * j <= k; ++j){
        //O(1) operations
    }
}

我知道外循环将迭代n次,内循环将为从外循环进行的每次floor(sqrt(k))迭代迭代k

因此,为了确定时间复杂度,我们有类似
\sum_{k=1}^{n} \floor{\sqrt{k}}
不知道如何进行并获得以n表示的闭合形式的时间复杂度。

最佳答案

我要说的是,您需要集成sqrt(n)=> n ^(1/2)。结果是n ^(3/2)。忘记发言权功能。

关于c++ - 循环复杂度,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/36479959/

10-14 14:09
查看更多