ユークリッドのGCD空間複雑度アルゴリズム

これは愚かな疑問に思えるかもしれませんが、反復的な実装でEuclidのGCDアルゴリズムO（1）の空間複雑さですか？私はちょうど（Googleでそれを見つけることができなかった）確認したかったユークリッドのGCD空間複雑度アルゴリズム

2016-03-25 a_123

あなたは、入力に依存しない一時変数または2つが必要なので、それはO（1）です。

2016-03-25 22:19:32 maniek

ありがとう:)私たちが再帰的な実装を行う場合、空間の複雑さはO（logn）です（nは2つの数値のうち大きい方です）。 –

@ s_123 O（ログ（小さい番号））です。これはすべて、算術演算が一定の時間/空間を取ると仮定している。これは1000桁の数字で作業する場合には必ずしも当てはまりません。 – maniek

なぜあなたはそのO（ログ（小さい番号））と言うのですか？アルゴリズムを見ると、2つの反復ごとに、より大きな数が少なくとも半分に減少します。だから私はそのO（ログ（大きい番号））と言った。なぜそれがO（ログ（小さい番号））になるのかわかりません。 –

答えて