1

私はこのコードに本当に近いことをしています:

for(int k=0; k<n; k++) {            // n
    for(int a=0; a<k; a++) {        // n/2 -> n (watch the a<k)
        ...                         // c
    }
    for(int i=0; i<n; i++) {        // n
        for(int a=0; a<i; a++) {    // n/2 -> n (watch the a<i)
            ...                     // c
        }
        for(int j=0; j<n; j++) {    //n
            ...                     //c
        }
    }
}

私が見つけようとしているのは複雑さです... O(n^3) を見つけましたが、この答えを「受け入れ」たくありません..基本的に 2 for(a) ループを削除すると、同じ複雑さ？

しかし、実際には、これらのコードの実行時間は同じではなく、おそらくそれほど近くないでしょう.. なぜまだ O(n^3) なのですか :/

4

1 に答える 1

2

for(a) を削除した後も O(n^3) のままです。

https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

また、ネストされた for ループと単一の for ループを使用した Big O 表記

于 2016-11-09T00:47:04.447 に答える