三个嵌套for循环的渐近分析 [英] Asymptotic analysis of three nested for loops

问题描述

我想计算这个嵌套的for循环的theta复杂度:

I want to calculate the theta complexity of this nested for loop:

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                // statement

我会说这是n ^ 3，但是我认为这是不正确的，因为每个for循环不会从1变为n.我做了一些测试:

I'd say it's n^3, but I don't think this is correct, because each for loop does not go from 1 to n. I did some tests:

n = 5-> 10

n = 5 -> 10

10-> 120

30-> 4060

30 -> 4060

50-> 19600

50 -> 19600

因此它必须在n ^ 2和n ^ 3之间.我尝试了求和公式，但结果却太高了.虽然是n ^ 2 log(n)，但这也是错误的...

So it must be between n^2 and n^3. I tried the summation formula and such, but my results are way too high. Though of n^2 log(n), but that's also wrong...

推荐答案

它是O(N^3).确切公式为

It is O(N^3). The exact formula is (N*(N+1)*(N+2))/6

这篇关于三个嵌套for循环的渐近分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！