我們的教授給了我們這個代碼作為大 O 符號 O(n) 的一個例子。但我想知道為什么。在我看來，這段代碼是 O(n2)。我希望你能幫助我。def g(n): x = n y = 1 while x > 0: x = x - 1 y = y + n while y > 0: y = y - 1 return True當我在循環中有一個循環時，我認為代碼在 O(n2) 中。這段代碼顯示了兩個單獨的循環，所以它應該是 O(2n)，但我可以忽略常量，我得到了 O(n)。如果我錯了，請糾正我。謝謝你的幫助！
3 回答
手掌心
TA貢獻1942條經驗 獲得超3個贊
第一個循環是 O(N)。它運行的次數與 n 的大小成正比。
第二個循環運行的次數與 y 的大小成正比。由于 y 在循環開始時等于 n**2，所以它是 O(N^2)。
由于該函數包含一個 O(N) 循環和一個 O(N^2) 循環，因此該函數總共為 O(N^2)。
神不在的星期二
TA貢獻1963條經驗 獲得超6個贊
def g(n):
x = n # x = n
y = 1
while x > 0:
x = x - 1 # loop through x times (since x=n, n times)
y = y + n # in the end, y = (1 + n) + ((1+n) + n) + (((1+n) + n) + n) ... = n + n*n
while y > 0: # loops n + n^2 number of times
y = y - 1
return True
如您所見，這是因為 y 的值最終為 n + n^2，所以 O(n^2) 是時間復雜度。
添加回答
舉報
0/150
提交
取消