performance - 计算嵌套for循环的时间复杂度

Question

我无法计算这些 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 个最内层循环的时间复杂度。

Answer 1

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

• countOne 递增 len 次。
• 对于每个 i，countTwo 递增 len-i/2 次。 i 从 0 到 len-1，因此 countTwo 在 len/2 和 len 之间递增(或 O(len))次，每个 i，或总共 O(len²)。
• countThree 的情况类似，它增加了 O(len³) 次。

因此整个算法的复杂度为O(len³)。