如何使用大哦符號來編寫程序的複雜性？

Question

來自「MITx：6.00.1x計算機科學與使用Python編程入門」。

我在做這個課程，在解決問題的過程中我遇到了問題。我是一個非常新的程序員，我沒有足夠的編程思想。

在最壞的情況下運行程序2將需要多少步驟？用n表示你的答案，n是輸入x的大小。

def program2(x): 
    total = 0 
    for i in range(1000): 
     total = i 

    while x > 0: 
     x = x//2 
     total += x 

    return total 

Answer 1

重寫

程序從自身得到答案

def program(x): 
    count = 0 
    while x > 0: 
     x = x // 2 
     count += 1 
    return count 

X = 2 ** 31 =>計數= 32

X = 2 ** 10 =>計數= 11

。 。 。

結果：O(log n)

Answer 2

在最好的情況下，x是小於或等於0。我們首先執行分配用於一個步驟總= 0。接下來我們在範圍（1000）循環中執行for。該循環執行1000次，並且每次迭代都有三個步驟（一個用於每次通過循環分配i，另外兩個用於+ =操作）。我們接下來檢查x> 0 - 它不是我們不進入循環。爲return語句添加一個步驟，在最好的情況下，我們執行1 + 3 * 1000 + 1 + 1 = 3003步。

在最壞的情況下，x是一個很大的正數。在這種情況下，我們首先執行一次賦值total = 0。接下來我們執行第一個循環1000次（總共3000步），然後執行第二個循環（x> 0）n次。該循環有五個步驟（一個用於條件檢查，x> 0，兩個用於 - =和+ =操作）。當我們最終達到x = 0的點時，我們最後一次執行條件檢查x> 0 - 因爲它不是，所以我們不進入循環。爲return語句增加一個步驟，在最壞的情況下，我們執行1 + 3 * 1000 + 5 * n + 1 + 1 = 5 * n + 3003步。