大哦分析

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))。