具有常量的递归树 - T(n) = T(n/3) + T(2n/3) + cn
Recursive tree with constant - T(n) = T(n/3) + T(2n/3) + cn
我有一个任务，只是有点问题，但我找不到答案。
通过使用递归树解释解决方案：
T(n)=T(n/3)+T(2n/3)+cn
其中 c 是常数，是 Omega(n lg n)
我的解决方案：
1. T(n)=T(n/3)+T(2n/3)+cn的递归树
最短路径将是最左边的路径，因为它对最低值进行操作，而最右边的路径将是最长的路径，这意味着树是不平衡的。
最短路径可以定义为：
n -> 1/3 n -> (1/3)^2 n ->...->1
- 递归树上的cn值：
每个完整级别的总和等于cn。
- 最短路径的元素被除以 3，因此这条路径的长度将等于 log_3 n。因此，如果最短路径的递归树的完整层数等于 log_3 n，则意味着该路径的算法成本为：
T(n)=cn log_3 n=Omega(cn lg n)
这个解决方案是否正确？如何在最后去掉 "c" 因为任务是解释 Omega(n\lg n) 而不是 Omega(cn lg n)？我认为大 Omega 符号会有所帮助，我可以忽略 "c"，但我的老师说 "constant according to definition [I don't know which definition] is important"
是的，您的解决方案是正确的。是的，你可以忽略常量。如果 c 是一个常量（根据定义 f(n) = Omega(g(n)) 如果存在这样的 C0 > 0 和 N0 则 Omega(c * n * log n) 与 Omega(n * log n) 相同对于任何 n >= N0 f(n) >= C0 * g(n)。如果我们有 g'(n) = c * g(n)，我们可以只选择 C0' = C0 * c)。
我有一个任务，只是有点问题，但我找不到答案。
通过使用递归树解释解决方案： T(n)=T(n/3)+T(2n/3)+cn 其中 c 是常数，是 Omega(n lg n)
我的解决方案：
1. T(n)=T(n/3)+T(2n/3)+cn的递归树
最短路径将是最左边的路径，因为它对最低值进行操作，而最右边的路径将是最长的路径，这意味着树是不平衡的。
最短路径可以定义为： n -> 1/3 n -> (1/3)^2 n ->...->1
- 递归树上的cn值：
每个完整级别的总和等于cn。
- 最短路径的元素被除以 3，因此这条路径的长度将等于 log_3 n。因此，如果最短路径的递归树的完整层数等于 log_3 n，则意味着该路径的算法成本为： T(n)=cn log_3 n=Omega(cn lg n)
这个解决方案是否正确？如何在最后去掉 "c" 因为任务是解释 Omega(n\lg n) 而不是 Omega(cn lg n)？我认为大 Omega 符号会有所帮助，我可以忽略 "c"，但我的老师说 "constant according to definition [I don't know which definition] is important"
是的，您的解决方案是正确的。是的，你可以忽略常量。如果 c 是一个常量（根据定义 f(n) = Omega(g(n)) 如果存在这样的 C0 > 0 和 N0 则 Omega(c * n * log n) 与 Omega(n * log n) 相同对于任何 n >= N0 f(n) >= C0 * g(n)。如果我们有 g'(n) = c * g(n)，我们可以只选择 C0' = C0 * c)。