確定循環的大O運行時？

問：根據N來說，下列最壞情況下的大運行時間是什麼？假設x是一個正整數，其中N = math.log（x，2）。確定循環的大O運行時？

def bigOh(x): 
    c = 1 
    while (x > 0) : 
     (x, c) = (x // 42, c + 1) 
    x = 1 
    while (x ** 2 < c) : 
     x += 1 
    return x

我無法計算第二個while循環所涉及的步驟數。第一個應該在O(N).

執行log x/log 42的次數即對於第二個循環，檢查(x + n) ** 2 < c每次，其中n是第n次迭代做，但我在此之後幾乎卡住。

任何人都可以請幫忙嗎？

編輯：正如註釋中指出的那樣，第一個循環以O（N）而不是O（log N）運行。

來源

2017-08-05 theguyoverthere

你可能喜歡簡單的'while'陳述，但是它讓我們很難掌握你的代碼來檢查它。起初，我認爲你有一個語法錯誤，直到我看到埋在這些線條中間的'：'。請使用標準的縮進內容重新格式化'while'語句。我知道這聽起來像是一個挑剔的問題，但如果您發佈人們可以快速輕鬆掌握的示例代碼，您將獲得更好的迴應。 – PaulMcG

感謝您的建議。我已經重新格式化了代碼片段。 – theguyoverthere

提示：'while x ** 2

第一個循環執行log x/log 42次。就N = log x/log 2而言，這只是O(N)時間。

第一次循環後，c ~ O(log x)。第二個循環在x ~ sqrt(c)時終止。因此它應該循環sqrt(c)次，即O(sqrt(log x)) = O(sqrt(N))。因此bigOh的總運行時間爲O(N + sqrt(N)) = O(N)。

來源

2017-08-05 09:33:24 extratype

確定循環的大O運行時？

回答

相關問題