带While的算法线性日志.使用大o

Question

算法的复杂度是多少?

我有下面的句子:

m = 12
while m>0:
n = 0
while n<m:
n+=1 
m/=3

我知道复杂度是(n+1)(log_3(n))所以结果是O(nlog_3(n) + log_3(n))

这对吗?

Answer 1

将m//=3替换为m//=3以确保处理整数并消除副作用(m/3四舍五入到0所需的时间)，我们可以做一些测试:

def counter(m):
count = 0
while m>0:
count += 1
n = 0
while n<m:
n+=1
count += 1
m//=3
return count

测试:

counter(12)
# 20
counter(1000)
# 1505
counter (1000000)
# 1500006

表示复杂度为0 (1.5 m)。

解释很简单:迭代次数(对于内循环，外循环的迭代次数可以忽略不计)为m + m/3 + m/3^2 + m/3^3 +…，其数学极限为m * 1/(1 - 1/3) = m * 1/(2/3) = 3m/2。

最后两点:

• 在评估复杂性时，不要保留可忽略的(可添加的)元素。
复杂度为0 (1.5 m)的
• 实际上会被写成O(m)(线性复杂度)。

Answer 2

复杂度不是0 (nlog_3(n) + log_2(n))。外部循环运行直到m变为0。循环执行的次数为log_3(m)。

在循环内部，内循环运行n次，其中n为外循环每次迭代开始时m的值。

因此算法的复杂度为O(m * log_3(m))。