大哦分析

Question

代碼1：

我我看來這段代碼是O（n^3），因爲外部循環運行N^2次，內循環運行n次。根據我的教授，這個代碼不是O（n^3）。有人能解釋爲什麼嗎？我很困惑。

i, j, sum = 1, 1, 0 

while i < n**3: 
    while j < n: 
    sum = sum + i 
    j += 1 
    i = i + n 

代碼2：

我覺得這個代碼爲O（n）。有人可以確認嗎？

i, j, sum = 0, 0, 0 

while i ** 2 < n: 
    while j ** 2 < n: 
    sum += i*j 
    j += 2 
    i += 4 

Answer 1

i, j, sum = 1, 1, 0 

while i < n**3: 
    while j < n: 
    sum = sum + i 
    j += 1 
    i = i + n 

注意，內環在外環的第一次通過期間，才執行，因爲j沒有被重新初始化爲for循環。很明顯，內部循環的運行時間恰好是n。另一方面，外循環執行n^2次。爲什麼？觀看i如何更改：首先是1，然後是n+1，然後2n+1，...，最後是n^2*n+1，所以i得到增加n^210次。因此，總運行時間爲n + n^2，即O(n^2)。

i, j, sum = 0, 0, 0 

while i ** 2 < n: 
    while j ** 2 < n: 
    sum += i*j 
    j += 2 
    i += 4 

類似的分析如在第一情況下，與附加註釋該條件while i ** 2 < n相當於while i < sqrt(n)。內循環僅在外循環的第一次執行期間執行，其運行時間爲sqrt(n)/2，因爲j會增加2（而不是1）。外環運行sqrt(n)/4次，所以總運行時間爲sqrt(n)/2 + sqrt(n)/4，即O(sqrt(n))。