loops - 興味深いネストされたループのビッグオー-それを数える方法は？

Question

Big Oh表記について同様の質問がたくさんあることは知っていますが、この例は非常に興味深く、些細なことではありません。

int sum = 0;
for (int i = 1; i <= N; i = i*2)
    for (int j = 0; j < i; j++)
        sum++;

外側のループはlg（N）回繰り返されますが、内側のループはどうでしょうか。そして、すべての操作のT（N）は何ですか？私は3つの可能性しか見ることができません：

私の意見-T（N）= N-しかし、これは、Nを何度も乗算したときの合計変数の観測値からの私の直感です-合計はほぼ2Nに等しく、Nが得られます。

基本的に私はそれを数える方法を知りません。このタスクを手伝って、解決策を説明してください-それは私にとって非常に重要です。

ありがとう

score 0 · Accepted Answer

内側のループは最後に最大時間を繰り返します。N.最後の実行の前に、N/2を繰り返します。合計するとN+N / 2 + N / 4 + N/8これは2*Nになります。そして、あなたがすべての実行を数えたので、それはすべてです。T（N）= N

1 に答える 1