大O符號Python函數

-2

foo（A）函數（其中n等於A的長度）的大O是什麼？據我所知，foo（4）語句對於遞歸的每次迭代都是O（1）。我也理解foo（A // 8）語句的運行時間將是對數的。大O符號Python函數

因此，程序的運行時間是否會是bigO（log（n））？

此功能用於練習測試的運行時間。

def foo(A): 
    if A <= 6: 
     return 7 
    return foo(A//8) + foo(4)

來源

2017-08-10 Roy Levy

是的，它會... –

你的分析是正確的。 foo(4)需要一定的時間，並且您必須執行關於log n（基數8）次的操作 - 當然是O(log n)。

如果使用公式是更加舒適，驗證與Master Theorem（A = 1，B = 8，K = 1 = 0）。

來源

2017-08-10 05:49:27 perigon

你的程序可以被寫成如下recurrsion：

T(n) = T(n/8) + C

應用Master theorem其中一個= 1和B = 8

我們落入第二種情況：

n^(log(1) base 8) = n^0 = 1 
C = ϴ(1). 
==> T(n) = O(n^(log(a) base b) * log(n)) = O(n^(log(1) base 8) * log(n)) 
     = n^0 * log(n) = 1*log(n) = O(log(n))

來源

2017-08-10 06:11:15

A不是一個向量，而是一個整數，因此有n N在這個問題中，複雜性必須用A來表示。

讓我們模擬的執行與A=1000：

foo(1000) 
    calls foo(125) and foo(4), i.e. 
    calls foo(15) and foo(4), and foo(4), i.e. 
    calls foo(1) and foo(4), and foo(4), and foo(4).

你得到的格局。因此，對foo的間接呼叫總數等於您可以將A除以8，直到它小於或等於6加上最終呼叫的次數。

這正是Floor(Log8(Ceil(A/7)))+1，這確實是O(Log(A))。

只是爲了好玩：

如果你寫的八進制A（基數爲8），該函數foo計算的八進制數字7時間的總和，但最右邊，加上7或14（如果最後數字是7）。

來源

2017-08-10 07:15:13

請注意解釋downvote。 –

我沒有投票給你。但我可以想，也許這是因爲你的回答不明確。（即使它是正確的）。也許是因爲已經有答案，你的沒有添加任何東西。 –

@TonyTannous：我寫了一個具體的答案（即顯示在特定情況下采取的確切步驟，然後推廣）。我還提供了呼叫次數的確切公式，並修正了OP的概念錯誤。我認爲這不值得讚揚。 [但感謝您留心評論。] –

大O符號Python函數

回答

相關問題