0 
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        for (int k = 0; k < 5; k++) {
            for (int l = 0; l < 5; l++) {
                look up in a perfect constant time hash table
            }
        }
    }
}

これの実行時間はビッグ シータでどのくらいになりますか?

私の最善の推測、暗所でのショット: ネストされた for ループは O(n^k) であることが常にわかります。ここで、k はループの数です。したがって、ループは O(n^4) になり、O を掛けますか? (1)一定時間？これはすべて大きなシータで何になるでしょうか?

4

3 に答える 3

2

ハッシュ テーブルへのアクセスが実際には theta(1) であると考える場合、このアルゴリズムは theta(1) でも実行されます。これは、ハッシュ テーブルで一定数 (5^4) のルックアップしか行わないためです。

ただし、5 を n に変更すると、正確に n^4 の定数時間操作を行うため、theta(n^4) になります。

于 2013-10-22T12:02:25.267 に答える
1

ビッグシータの実行時間はΘ(n^4).

Big-O は上限であり、big-theta はタイト バウンドです。これが意味することは、コードがO(n^5)正しい (しかしΘ(n^5)そうではない) と言うのは、big-O の内部にあるものは何でも、漸近的に よりも大きくなければならないということn^4です。

別の値 (つまり is ) に置き換える5ことができると仮定しています。nO(1)Θ(1)5^4

于 2013-10-22T12:06:42.943 に答える
0

シグマ表記の使用:

ここに画像の説明を入力

実際、最も内側のループ内の命令は625回実行されます。

于 2014-04-23T22:42:16.380 に答える