我們的教授給了我們這個代碼作為大 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當(dāng)我在循環(huán)中有一個循環(huán)時，我認(rèn)為代碼在 O(n2) 中。這段代碼顯示了兩個單獨(dú)的循環(huán)，所以它應(yīng)該是 O(2n)，但我可以忽略常量，我得到了 O(n)。如果我錯了，請糾正我。謝謝你的幫助！
3 回答
手掌心
TA貢獻(xiàn)1942條經(jīng)驗(yàn) 獲得超3個贊
第一個循環(huán)是 O(N)。它運(yùn)行的次數(shù)與 n 的大小成正比。
第二個循環(huán)運(yùn)行的次數(shù)與 y 的大小成正比。由于 y 在循環(huán)開始時等于 n**2，所以它是 O(N^2)。
由于該函數(shù)包含一個 O(N) 循環(huán)和一個 O(N^2) 循環(huán)，因此該函數(shù)總共為 O(N^2)。
神不在的星期二
TA貢獻(xiàn)1963條經(jīng)驗(yàn) 獲得超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)?y 的值最終為 n + n^2，所以 O(n^2) 是時間復(fù)雜度。
森林海
TA貢獻(xiàn)2011條經(jīng)驗(yàn) 獲得超2個贊
你的代碼的復(fù)雜度是O(n^2)因?yàn)?code>y在第一個循環(huán)中總是以 n * n 結(jié)束，這將 n 添加到yn 次，所以第二個循環(huán)將迭代 n * n 次。
添加回答
舉報(bào)
0/150
提交
取消