0

以下のコード セグメントでは、big-oh 表記で時間の複雑さを見積もります。

for (int i=0; i< n; i++)

for (int j=0; j*j <n;j++)

for (int k=0; k < n/2;k++)
    System.out.println (i+j+k);

それらはネストされたループだと思いますが、100％確信はありません。私が把握できることから、最初のループの最悪の時間は O(n)、2 番目は O(sqrt(n))、3 番目は O(log n) です。あれは正しいですか？そして、これらの値を乗算して、ループ全体の時間計算量を取得しますか?

4

5 に答える 5

2 
for (int i=0; i< n; i++)  ------------------------------------
                                                             |
    for (int j=0; j*j <n;j++) ----------------------         |
                                                   |         | O(n)
        for (int k=0; k < n/2;k++)  -------        |         |
                                          |O(n/2)  |O(n^1/2) |   
            System.out.println (i+j+k); ---        |         |
                                                   |         |
                              ----------------------         |        
                                                             |
                          ------------------------------------

したがって、ランタイム

O(n)*O(n^1/2)*O(n/2) = O(n^(5/2))
于 2013-10-02T05:43:14.930 に答える
0

ループ 1 の変化率は n -> O(n) に線形に依存します -- 線形

ループ 2 の変化率は、n の平方根に依存します -> O(n^0.5) -- 分数の累乗

ループ 3 の変化率は n/2 に線形に依存しますが、1/2 の定数は削除できます -> O(n/2) -- 線形

したがって、全体的な複雑さは O(n) * O (n^0.5) * O (n) = O (n^2.5) になります。

詳細については、こちらを確認してください: http://www.brpreiss.com/books/opus5/html/page72.html

于 2013-10-04T16:23:12.177 に答える