对数时间复杂度的总和

Question

什么是 O(logn) + O(2log(n/2)) + O(4log(n/4)) ... + O(nlog1) ？

我认为是 O(nlogn) 。请澄清我是否正确。

我在这里试图解决的递推关系是T(n)=2T(n/2)+ log(n), T(1)=1。请帮我解决这个问题。

Answer 1

在递归关系中，我假设 log𝑛 是 log₂𝑛。

我们可以如下证明𝑇(𝑛) 是 O(𝑛)：

首先，我们可以看到𝑇(𝑛)随着𝑛的增加而增加，因此对于渐近分析，我们可以只查看那些2的幂的𝑛，即我们可以替换𝑛 = 2^𝑘。

然后：

      𝑇(2^𝑘) = 2⁰log(2^𝑘) + 2¹log(2^𝑘−1) + 2²log(2^𝑘−2) + . .. + 2^𝑘−1log(2¹) + 2^𝑘log(2⁰)

对于非负整数 𝑖，log₂(2^𝑖) = 𝑖，我们可以简化：

      𝑇(2^𝑘) = 𝑘2⁰ + (𝑘−1)2¹ + (𝑘−2)2² + ... + 1⋅2^𝑘−1 + 0

将积极因素和消极因素归为一组：

      𝑇(2^𝑘) = 𝑘(2⁰ + 2¹ + 2² + 2³ + ... + 2^𝑘−1) − [1⋅2¹ + 2⋅2² + 3⋅2³ + ... + (𝑘−1)2^𝑘−1]

第一个括号包含几何级数的部分和，因此等于 2𝑘^−1:

      𝑇(2

𝑘^{) = 𝑘(2}𝑘^{−1) − [1⋅2}1 ^{+ 2⋅2}2 ^{+ 3⋅2}3 ^{+ ... + (𝑘−1) 2}𝑘−1^]

方括号中的部分可以分成单独的总和，再次使用几何序列属性：

[1⋅2222...22

1 + 2⋅22 + 3⋅23 + ... + (𝑘−1)2𝑘−1] 是以下各项之和：
1 + 22 + 23 + ... + 2𝑘−2 + 2𝑘−1 = 2𝑘 − 21
2 + 23 + ... + 2𝑘−2 + 2𝑘−1 = 2𝑘 − 22
3 + ... + 2𝑘−2 + 2𝑘−1 = 2𝑘 − 23
𝑘−2 + 2𝑘−1 = 2𝑘 − 2𝑘−2
𝑘−1 = 2𝑘 − 2𝑘−1

右侧表达式之和为：

      (𝑘−1)2

𝑘 ^{− (2}1 ^{+ 2}2 ^{+ ... + 2}𝑘−1⁾

我们在括号中再次看到了几何序列的部分和：

      (𝑘−1)2

𝑘 ^{− (2}𝑘 ^{− 2) = (𝑘−2)2}𝑘 ^{+ 2}

将其注入回 𝑇(2

𝑘^{) 中的方括号表达式：}

      𝑇(2

𝑘^{) = 𝑘(2}𝑘^{−1) − (𝑘−2)2}𝑘 ^{− 2}

      𝑇(2

𝑘^{) = 𝑘2}𝑘 ^{− 𝑘 − 𝑘2}𝑘 ^{+ 2}𝑘+1 ^{− 2}

      𝑇(2

𝑘^{) = 2}𝑘+1 ^{− 𝑘 − 2，即 O(2}𝑘^{)，即 O(𝑛)。}