如何使用求和法解决时间复杂性

Question

我熟悉一些较简单的示例，但遇到了较难的示例：

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

有人可以帮我吗？

谢谢。

Answer 1

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