如果下面有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/