algorithm - アルゴリズム全体の時間計算量は?

Question

私は漸近記法が初めてで、これがアルゴリズムです。時間の複雑さに対する最悪のケースのタイト ボンドとは何ですか?またその理由は何ですか?

F(A,B) {  //A and B are positive
  while A>0 
    print(A mod B)
    A=A div B
}

Answer 1

あまり良い質問ではありません。まず、B が 1 の場合、アルゴリズムは決して完了しません。おそらく、B は 2 以上でなければなりません。したがって、O(log A) のステップがあります。しかし、ここで問題になるのは、分割自体が「操作」であるかどうかです。A と B が無制限の場合、本質的に対数的でなければなりません。しかし通常、コードはすべての除算を 32 ビットまたは 64 ビットで実装するプロセッサ上で実行され、範囲外の数値を除算することはできません。したがって、一般的に部門は「操作」であると言います。

割り算が対数で、B が小さいと言うと、O(log A)^2 になります。

Answer 2

これの時間の複雑さ:

F(A,B) {  //A and B are positive
  while A>0 
    A=A/B
}

は、ループが実行される回数に等しく、それを呼び出しましょう。lまた、B が A を分割して "A > 0" を false にする回数に等しくなります。

この質問から、次のことがわかります。

Knuth の著書「The Art of Computer Programming」(Volume 2) の 4.3.1 のアルゴリズム D は、O(m) ステップで長い除算を実行します。ここmで、 は A の桁数であるため、上限があります。

したがって、時間計算量は次のようになります: *O(l * m)*

今これ：

print(A mod B)

IO が一定であると仮定すると (これはもちろん現実世界では正しくありません)、モジュロ自体の複雑さが必要になります。

O(対数A対数B)

と実行されますl。

その結果、次のようになります。

O(l * (m + log A log B))