算法复杂度循环

Question

三重嵌套循环的时间复杂度

for(int i=0; i<n; i++)
    for(int j=i+1; j<n; j++)
        for(int k=j+1; k<n; k++)

我想知道时间复杂性的正确解决方案。

Answer 1

确定算法增长顺序的正式解决方案：

​

​

Answer 2

第一个猜测:依赖于n的三个循环，所以它应该是O(n³)

如果你试图计算精确的复杂性，你必须计算它的内部，乘以它与外部循环。

内环采用O(n-k)

中间回路采用O(n-j + n-j-1 + ... + n-j-n) = O((n-j) ⋅ (n-j+1) / 2) = O((n-j)²)

外循环采用O((n-1)² + (n-2)² + ... + (n-n+1)²) = O(n³)

当然，这不是精确的，但就大-O而言，它是精确的。