整個算法的時間複雜度是多少？

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」錯誤。

從這個question，我們知道：

算法d在Knuth的著作 「計算機程序設計藝術」（第2卷）的4.3.1執行在O（M）的步驟，其中任何長除法m是A的位數，所以我們有一個上限。

這樣的時間複雜度爲：* O（L * M）*

現在這個：

print(A mod B) 

假設IO是恆定的（這是當然的東西是不正確的實世界國際），你需要的模本身的複雜性，從this，我們知道這是：

爲O（log日誌B）

並將運行l次。

因此，我們有：

O（L *（M +登錄日誌B））

Answer 2

這不是一個很好的問題。首先，如果B是統一的，算法將永遠不會完成。推測B必須是2或更大。所以我們有O（log A）步驟。但現在的問題是該部門本身是否是「操作」。如果A和B是無界的，那麼它本身也必須是對數的。但通常代碼將運行在實現32位或64位所有分區的處理器上，並且不能將數字劃分超出範圍。所以通常我們說分裂是「操作」。

如果我們說劃分是對數的而B小的話我們是O（log A）^ 2。