さて、今日は中間試験があり、レビューしている項目の 1 つは big-O です。今、私は昔宿題をして100％を取りました....しかし、今はそれを見つけることができず、自分が何をしているのかわかりません. 誰かが私が間違っていることについて説明してくれませんか...もし私が正しいことをしているなら...なぜ私が自分自身を疑っているのか知っているでしょうか? ありがとう！
また、以前宿題で総和を使っていたのを覚えています。そして、各合計が終了したら、いくつかの「式」を使用して最大の n を計算し、その値を保持して次の合計に進み、合計がすべて完了するまで繰り返しました。
問題1。
sum = 0;
for (i = 0; i < n; i++)
sum++;
したがって、これの合計の側面全体を忘れてしまったので、直感的に、これは O(N) であるとわかりました。これは、最大ランタイムが N 回であるためです...ループの 1 つに過ぎないためです。
問題2。
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum++;
これについては、両方のループが n に依存しており、if ループごとに N * N で最大化できるため、最高の実行時間は O(N^2) であると「考えています」。
問題3。
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n * n; j++)
sum++;
これが私が行き詰まるところです...実際には、それらを合計するための式とともに合計レイアウトを使用する必要があるように感じます。最も内側のループは n*n で最大化できるため、n^2 になります。その上、最も外側のループの N で再び最大化できるので、0(N^3) と推測します。
問題4。
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
sum++;
繰り返しますが、私はこれについてもっと迷っています。内側のループは i 回最大化できます...これは i に依存しますが、これは N に依存します....だから...3 つの最大化された変数が表示され、それらを比較して最大化された変数を見つける方法が文字通りわかりませんランタイム。（その合計の設定と式を覚えておく必要があります）。
次の問題についても同じことが言えます。どこから始めればよいかわかりません。頭の中で間違った考えを持ちたくないので、始めたくないのです。公式をもう一度見ると、すぐにクリックされると確信しています。以前に取得したためです...どういうわけか紛失しただけです。どんな助けでも大歓迎です！
問題 5:
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i * i; j++)
for (k = 0; k < j; k++)
sum++;
問題 6:
sum = 0;
for (i = 1; i < n; i++)
for (j = 1; j < i * i; j++)
if (j % i == 0)
for (k = 0; k < j; k++)
sum++;