1

我无法计算这些 for 循环的时间复杂度：

for(int i=0; i<len; i++){
    countOne++;
    for(int j=i/2; j<len; j++){
        countTwo++;
        for(int k=i/2; k<len; k++){
            countThree++;
        }
    }
}

我不明白如何计算 2 个最内层循环的时间复杂度。

4

2 回答 2

3

这听起来像是一个很大的问题。但是您应该在将来指定。

  • countOne是递增的len次数。
  • 对于每i,countTwo是递增的len-i/2次数。i从 0 到len-1，因此在和（或 O(len)) 次countTwo之间递增，或总共为 O(len 2 )。len/2leni
  • 类似countThree的故事，它增加了 O(len 3 ) 次。

因此整个算法是 O(len 3 )。

于 2013-10-13T05:47:02.823 回答
0

You proceed methodically with Sigma notation:

enter image description here

于 2014-07-02T00:57:10.380 回答