アルゴリズム全体の時間複雑度はどのくらいですか？

Question

私は漸近表記法を初めて習得しました。ここにアルゴリズムがあります。時間の複雑さのための最悪の場合のタイトボンドとは何ですか？

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

Answer 1

この時の複雑さ：

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

は、ループが実行される回数に等しい、のlとは、Bが作るために分割しなければならない回数に等しいことを呼ぶことにしましょう"A> 0"は偽です。 O（M）のステップ、のいずれかの長い除算を実行Knuthの著書 "コンピュータプログラミングの芸術"（2巻）の4.3.1で

アルゴリズムD：このquestionから

、我々はそれを知っていますmはAの桁数なので、上限があります。

このように時間計算は次のとおりです。* O（L×m個）*

今、この：

print(A mod B) 

はIOが一定であると仮定すると（つまり、リアルで正確ではありませんもちろんの何か世の中）、あなたはthisから、我々はそれを知っているされ、剰余自体の複雑さを必要とする：

O（ログBをログ）

となり、l回実行されます。

その結果、我々は持っている：

O（のL *（M +ログBをログ））

Answer 2

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

除算がlogarithimicでBが小さいとすると、O（log A）^ 2となります。