0

私はこのコードを持っていて、その時間の複雑さを知りたいです:

    int N,M; // let N and M be any two numbers 
    while(N != M && N > 0 && M > 0){
       if(N > M)N -= M;
       else M -= N;
    }

M と N の値が異常な方法で減少するため、これを分析する方法がわかりません。これにアプローチする標準的な方法はありますか？

4

1 に答える 1

5

このコードは、ユークリッド アルゴリズムの単純な実装です。反復のたびに、大きい方の数値から小さい方の数値を引いているため、アルゴリズムを「フェーズ」に分割できます。各フェーズは、大きい方の数値が小さい方の数値を下回るまで、大きい方の数値から小さい方の数値のコピーをできるだけ多く減算することで構成されます。(これは、古代ギリシャ人が call anythpharesisについて知っていた手順に関連しています) これの現代版は、O(log min{M, N}) 内で終了することが知られている、より大きな数をより小さな数で変更することです。ステップ (これは現代のユークリッド アルゴリズムです) であり、数値が整数として表されると仮定すると、各ステップに O(1) の時間を費やします。

この場合、O(log min{M, N}) フェーズがあることがわかっていますが、各フェーズにかかる時間は一定ではありません。Anythpharesis の背後にある幾何学的な直感を使用して、個々のフェーズが終了するのに非常に長い時間がかかる数のペアを構築することが可能です。 + M)。

要するに、このコードは、対数時間で実行される最新の実装と比較して非効率的です。ランタイムの適切な上限を取得するのは困難ですが、現実的に言えば、コードを書き直してより効率的にするだけなので問題ありません。:-)

お役に立てれば！

于 2013-10-08T20:39:25.307 に答える