ビッグOの表記法とアルゴリズム

私は現在、いくつかのアルゴリズムを研究して実装しようとしています。私は、ランダウの記号を理解しようとしていると私は下のアルゴリズムのためのビッグOの複雑さを把握することはできません。（数学者ではありません）ほとんどの人は、その原料を見つける必要がありませんビッグOの表記法とアルゴリズム

while (a != 0 && b != 0) 
{ 
    if (a > b) 
     a %= b; 
    else 
     b %= a; 
} 

if (a == 0) 
    common=b; 
else 
    common=a;

出典

2010-12-26 Tristan Demanuele

2回の繰り返しの後に、数字の最小値が少なくとも2倍小さくなることは容易にわかります。それが最初に等しいmだった場合、2Kの反復後にはそれはm/2^Kを超えないでしょう。ここでK = [log_2（m）] + 1を入力すると、2Kの反復の後に数字の最小値がゼロになり、ループが終了することがわかります。したがって、反復回数は2（log 2 m + 1）= O（log m）を超えない。

出典

2010-12-26 21:31:02 adamax

このバインドが厳しいことを示すために、 'O（log m）'ステップが必要な数字の例を追加することもできればうれしいです。 – liori

上記のコードにコメントを追加できますか？あなたはこの結論にどのようにできるかを示すことができます。 –

@tristanなぜこのように数字の最小値が減少するのでしょうか？ a> bとし、1回の反復の後に最小値はc = a％bであり、2回反復した後はb％cである。 c <= b/2ならば、b％c b/2の場合、b％c = b-c adamax

、それはすでにです文書番号：http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency

出典

2010-12-26 21:15:36 fejesjoco

質問に答えません（指定されたアルゴリズムの大きな表記です）（-1） –

質問に答えます。 "ユークリッドのアルゴリズムは、最初の2つの数値aとbの平均桁数hで二次的に（h2）増加します。 - > O（h^2） – fejesjoco

私は文脈なしでこれに答える場合を除いて、彼は理解しません。私はまた、証拠全体を表示しません。だから私はウィキペディアの記事が最高の答えだったと信じています。 – fejesjoco

これは、2つの整数の最大公約数を計算するためのユークリッドアルゴリズムです。私はあなたにこのアルゴリズムの複雑さに関する研究をさせるが、フィボナッチ数は重要な役割を果たす。

出典

2010-12-26 21:16:24 jason

ビッグOの表記法とアルゴリズム

答えて

関連する問題