我熟悉一些较简单的示例,但遇到了较难的示例:
DoSomething(n)
a ← 1
b ← n
s ← 0
while a ≤ b do
t ← a
while t ≤ b
s ← s + 2 * t
t ← t + 2
a ← 16 * a
b ← 2 * b
return s
有人可以帮我吗?
谢谢。
DoSomething(n)
n
是复杂度方程式中的主要变量
a ← 1
b ← n
s ← 0
这里有3个归因运算= O(1)
while a ≤ b do
//code
a ← 16 * a
b ← 2 * b
这里有花招。 code
将运行多少时间?它仅取决于a
和b
。可能需要注意的是,如果a
乘以16,b
乘以2,则等于a
乘以8,而不是b
乘以任何东西,因此我们可以将其重写为
while a ≤ b do
//code
a ← 8 * a
这样,可以说code
将被执行log8(n)次。现在让我们检查code
的复杂度:
t ← a
while t ≤ b
s ← s + 2 * t
t ← t + 2
[在最坏的情况下,即当a
离b
最远时,将花费时间O(n / 2),因为t
步行2乘2直到到达n
。
我们最终可以说复杂度为O(log8(n))* O(n / 2)+ O(1)= O(n lg(n))。