使用递归树的Big O Notation分析
Big O Notation analysis using recursion tree
问题来自：http://qpleple.com/divide-and-conquer/
算法比较
You are product manager at Facebook and three engineers from your team come up with these three algorithms to detect fake Facebook accounts in the list of n=1 billion Facebook accounts.
Rakesh solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
Chris solves problems of size n by recursively solving two subproblems of size n−1 and then combining the solutions in constant time.
Matus solves problems of size n by dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n²) time
所以通过使用主定理我发现：
- Rakesh 算法的 运行 时间为
O(n<sup>log2(5)</sup>)
- Matus 算法的 运行 时间为
O(n<sup>2log(n)</sup>)
绘制递归树并使用：
Rasket 的算法有：
#levels = log₂(n)
#of nodes at level k = 5k
overhead per node at level k = n/2k
但不管我怎么努力，我总不能得到等于 O(n<sup>log₂(5)</sup>) ，Matus 的算法也是如此。
还有，有没有办法用主定理解决克里斯算法的 运行 时间？
正在申请
#levels = log₂(n)
#of nodes at level k = 5k
overhead per node at level k = n/2k
到
你得到（使用geometric formula）
T(n) = Σk=0,...,log₂(n) 5k ⋅ n/2k
= n ⋅ Σk=0,...,log₂(n) (5/2)k
= n ⋅ (1 - (5/2)log₂(n)+1) / (1 - 5/2)
= (n - n ⋅ (5/2) ⋅ 5log₂(n) / 2log₂(n)) / (1 - 5/2)
= (n - n ⋅ (5/2) ⋅ 5log₂(n) / n) / (1 - 5/2)
= (n - (5/2) ⋅ 5log₂(n)) / (1 - 5/2)
= ((5/2) ⋅ 5log₂(n) - n) / (5/2 - 1)
= ((5/2) ⋅ 5log₂(n) - n) / (3/2)
= (5/3) ⋅ 5log₂(n) - (2/3) ⋅ n ∈ Θ(5log₂(n))
现在你只需要显示 5<sup>log₂(n)</sup> = n<sup>log₂(5)</sup>, 大约一行就可以搞定。
我为 Chris 得到的递归方程是
T(n) = 2⋅T(n-1) + O(1)
这不能用主定理求解，但你可以将它展开为求和求解：
T(n) = 2⋅T(n-1) + Θ(1)
= 2⋅(2⋅T(n-2)+ Θ(1)) + Θ(1)
= 2²⋅T(n-2) + 2⋅Θ(1) + Θ(1)
...
= 2n⋅T(1) + 2n-1⋅Θ(1) + ... + 2⋅Θ(1) + Θ(1)
= 2n+1⋅Θ(1) - 1 ∈ Θ(2n)
这适用于 T(1) ∈ Θ(1)。
问题来自：http://qpleple.com/divide-and-conquer/ 算法比较
You are product manager at Facebook and three engineers from your team come up with these three algorithms to detect fake Facebook accounts in the list of n=1 billion Facebook accounts.
Rakesh solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
Chris solves problems of size n by recursively solving two subproblems of size n−1 and then combining the solutions in constant time.
Matus solves problems of size n by dividing them into nine subproblems of size
n/3, recursively solving each subproblem, and then combining the solutions inO(n²)time
所以通过使用主定理我发现：
- Rakesh 算法的 运行 时间为
O(n<sup>log2(5)</sup>) - Matus 算法的 运行 时间为
O(n<sup>2log(n)</sup>)
绘制递归树并使用：
Rasket 的算法有：
#levels = log₂(n) #of nodes at level k = 5k overhead per node at level k = n/2k
但不管我怎么努力，我总不能得到等于 O(n<sup>log₂(5)</sup>) ，Matus 的算法也是如此。
还有，有没有办法用主定理解决克里斯算法的 运行 时间？
正在申请
#levels = log₂(n) #of nodes at level k = 5k overhead per node at level k = n/2k
到
你得到（使用geometric formula）
T(n) = Σk=0,...,log₂(n) 5k ⋅ n/2k
= n ⋅ Σk=0,...,log₂(n) (5/2)k
= n ⋅ (1 - (5/2)log₂(n)+1) / (1 - 5/2)
= (n - n ⋅ (5/2) ⋅ 5log₂(n) / 2log₂(n)) / (1 - 5/2)
= (n - n ⋅ (5/2) ⋅ 5log₂(n) / n) / (1 - 5/2)
= (n - (5/2) ⋅ 5log₂(n)) / (1 - 5/2)
= ((5/2) ⋅ 5log₂(n) - n) / (5/2 - 1)
= ((5/2) ⋅ 5log₂(n) - n) / (3/2)
= (5/3) ⋅ 5log₂(n) - (2/3) ⋅ n ∈ Θ(5log₂(n))
现在你只需要显示 5<sup>log₂(n)</sup> = n<sup>log₂(5)</sup>, 大约一行就可以搞定。
我为 Chris 得到的递归方程是
T(n) = 2⋅T(n-1) + O(1)
这不能用主定理求解，但你可以将它展开为求和求解：
T(n) = 2⋅T(n-1) + Θ(1)
= 2⋅(2⋅T(n-2)+ Θ(1)) + Θ(1)
= 2²⋅T(n-2) + 2⋅Θ(1) + Θ(1)
...
= 2n⋅T(1) + 2n-1⋅Θ(1) + ... + 2⋅Θ(1) + Θ(1)
= 2n+1⋅Θ(1) - 1 ∈ Θ(2n)
这适用于 T(1) ∈ Θ(1)。