ランダウの記号-してくださいコードのこの作品は、そのランダウの記号のためのO（2^n個のログを記録）である理由私は悩みの理解を持っていますO（log2n）

を説明します。ランダウの記号-してくださいコードのこの作品は、そのランダウの記号のためのO（2^n個のログを記録）である理由私は悩みの理解を持っていますO（log2n）

for (int i = n; i>=1; i=i/2){ 
    sum = i+j; 
}

私はそれが可能だろうと思いましたに）。

出典

2017-10-29 sukiyo

どの部分が混乱していますか？ 'i = i/2'に気付く？ –

@ElliottFrisch私はforループを見て、私はそれがちょうど0（n）と思った。私はforループでi = i/2の意義を得られません。私は2で除算されることを知っています（forループの1つのループごとに2で割っていますか？） – sukiyo

@sukiyo：ループを通過するたびに 'i'を2で割るので、' i'が1024ループが終了した時点で、512,256,128,64,32,16,8,4,2,1、そして0（整数除算のため）になります。したがって、 'n'が2倍になるたびに、ループが終了する前に1回繰り返します。これは 'log（base 2）of n 'の定義です。 – StriplingWarrior

O(log_2 n)です。 n 1.

になるまで、それはそうn/2^k = 1

k=log_2 n

複雑さは、私はそれを得るO(log_2 n)

出典

2017-10-29 03:22:27 coderredoc

は、n/2^k i = i/2部分ですか？ – sukiyo

@sukiyo：すべてのステップで、基本的にnを2で割っています。あなたはそれを正しく持っています。 – coderredoc

ありがとうございます。私はそれをログ形式で書く方法を理解していません。 n/2はどこに行きましたか？ – sukiyo

で全体のものが1

になったとステップk番目の後に実行されますので、最初は間違っていますが、これを見て、forの各ループでは、i/2を実行するので、最後にn個のlog2要素をスローします。 @coderredocは、このコードスニペットは、O（n個のログ）で説明したように

：だから結論には0（のlog2 N）

出典

2017-10-29 03:34:06

簡単な答えになります。対数の基底は、恒等式の表記において重要ではない。

詳細回答：これは学問的な文脈で尋ねられます。 big-O表記法とbig-Θ表記法の違いについての詳細をお読みください。特定の質問、Oであり、任意のコード（ログn）について http://web.mit.edu/16.070/www/lecture/big_o.pdf https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation

theroritically O（2^N）またはO（N）またはO（2^n個のログ）であると言うことができます。なぜなら、big-Oの表記法は、拘束された拘束であり、拘束された拘束ではないからです

出典

2017-10-29 06:30:52

ランダウの記号-してくださいコードのこの作品は、そのランダウの記号のためのO（2^n個のログを記録）である理由私は悩みの理解を持っていますO（log2n）

答えて

関連する問題