1 
def fd(n):
    x,y,count1,count2 = n,1,0,0
    while (x > 1): (x,count1) = (x/5,1+count1)
    while (y < n): (y,count2) = (count1+y,1+count2)
    return count2
4

2 に答える 2

10

どれどれ。最初のループはn、5で除算できる回数をカウントし、 count1log（n）もカウントします（定数はO（）計算にはカウントされません）。count1次に、2番目のループは（= log（n））を1に追加してに到達できる回数をカウントするnため、基本的にn / log（n）回ループします。

これはO（log（n）+（n / log（n）））のように見えます。

JFセバスティアンが指摘しているように、n / log（n）がlog（n）を支配しているため、最終的な答えはO（n / log（n））になります。

于 2012-10-18T03:40:01.153 に答える
0

この質問への答えは、私たちが話していることについての合意に依存していることを指摘したいと思います（二重の数字が操作されるという事実は重要ですか？不十分に聞こえるかもしれない理論的な答えまたは実際的な答えが必要ですか？ ）。

この答えを言い換えさせてください：https ：//stackoverflow.com/a/2027842/512225 ：

人々はbig-O表記で少し速く緩く演奏します。

アルゴリズムの複雑さ、つまりbig-O表記は、入力の値ではなく、入力のビット単位のサイズで表す必要があります。2進入力と任意に大きい数、およびNを入力のビット数とすると、N = log（n）です。2番目のループにはn/log（n）ステップ= exp（N）/ Nステップが必要なため、複雑さはO（exp（N）/ N）= O（exp（N）/ N）です。

実際には、Nが入力のサイズではなく、入力自体であるかのように複雑さについて話すことは理にかなっています。その場合、関数の複雑さはn / log（n）です。

とにかく、nがdoubleの定義によって制限されるという事実によって与えられる問題を無視しているので、厳密に言えば、漸近的な振る舞い（n->無限大）について話すことは意味がありません。また、入力が2倍の場合、そのサイズは一定であるため、アルゴリズムの複雑さは（厳密に言えば）O（1）（huge_constant x 1）であり、huge_constantは最悪の場合の時間（おそらくその定数）に等しいという事実も無視します。 Pythonのdoubleで表現できる最大数によって異なります）。

要約：

正式な答えはO（1）ですが、O（exp（N））は答えほど悪くはありません。O（n / log（n））も良い答えです（そしておそらくあなたが本当に必要としているものです）。

于 2012-10-18T05:03:52.077 に答える