問題を解決できません。誰かが私を助けることができますか？
以下のステートメントの Big O 表記法は何ですか:-
for (int i=2;i<=n;i=i*4)
sum++;
2173 次
7 に答える
12
i が指数関数的に成長すると、O(log(n)) になります。
n が 16 倍大きい場合、ループを 2 回だけ多く実行することが期待されます。
于 2009-08-10T02:37:38.737 に答える
5
n のいくつかの (小さな) 値についてループ回数を数え、結果をグラフ化してみてください (横軸に n、縦軸にループ回数)。問題をいじってみるのは、学習が初めての場合に最適です。
n に選択する値によっては、パターンが表示されない場合があります。たとえば、n=10 と n=20 のループ回数は同じです。ループ回数がいつ変化するかを考えると、ビッグオーのタイミングを知ることができるパターンも明らかになります。
アルゴリズムのタイミングについて理解が深まれば、このやや時間のかかる手順を実行する必要はなくなります。コード分析を通じて、big-O のタイミングを代数的に把握できるようになります。
于 2009-08-10T02:42:40.820 に答える
4
ビッグ O 表記について私が考える方法は、完了するまでにかかる時間、つまり複雑さです。たとえば、バブル ソートがある場合、ソート対象のアイテムに移動すると、完了までに約 n*n 操作 (O(N^2)) がかかります。
二分探索の場合、n のサイズを大きくすると、log2(n) 操作で値を見つける必要があります。操作の数は対数なので、二分探索の場合は O(log N) (対数は 2 の対数) です。
あなたが持っているものについては、O（N）である線形的に増加しているため、N個の操作があります（これはオフセットの場合でも）。これは線形検索の表記法です。これは、値を見つけるのに n/2 オプションの平均が必要な場合があるためです。それでも O(N) です。
ウィキペディアの O(N) 表記を見てみましょう。より技術的な説明と、より大きな O 表記情報があります。
于 2009-08-10T03:03:40.317 に答える
3
の開始点と乗数が > 1 であることがわかったらi、それらの正確な値は big-O 項に違いはありません (コア コンポーネント に追加または乗算される定数に変換されるだけでO(log N)あり、そのような定数は big-O 推論では無視されます)。 --結局のところ、それが Big-O 推論の核心です!!!)。
于 2009-08-10T02:42:24.657 に答える
1
これは宿題の演習として行っているため、実際に行う必要があるのは、最初の原則に戻ることです。つまり、O 記法の数学的定義です。「n」が増えるにつれて単純な計算ステップがいくつあるかを計算し、代数的に極限を計算してから、答えに進みます。
実際には、ほとんどの人は、古典的な例の知識と経験に基づいて「O」の複雑さを見積もっています。そして、彼らはそれを誤解することがよくあります。
于 2009-08-10T03:10:28.933 に答える
0
「sum++」が定数であると仮定すると、アルゴリズムは O(log 4 n) であるというかなり合理的な仮定です。
ループは 2 から n になるため、最大でも O(n) であることがわかります。ただし、インクリメントはループごとに 4 倍されるため、ループに費やされる時間は指数関数的に少なくなります。
于 2009-08-10T03:42:57.347 に答える
0
i の最初の 4 つの値は 2、8、32、128 であるため、ループの反復回数を示す式は次のとおりです。
((log(n)/log(2))/2)+0.5
于 2009-08-10T21:21:50.663 に答える