algorithm - 具有常量的递归树 - T(n) = T(n/3) + T(2n/3) + cn

Question

我有一个任务，只是有点问题，但我找不到答案。

通过使用递归树解释解决方案: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

1. 递归树上的 cn 值:

每个完整级别的总和等于cn。

1. 来自最短路径的元素被除以 3，所以这条路径的长度将等于 log_3 n。因此，如果最短路径的递归树的完整层数等于 log_3 n，则意味着该路径的算法成本将为:T(n)=cn log_3 n=Omega(cn lg n)

这个解决方案是否正确？由于任务是解释 Omega(n\lg n) 而不是 Omega(cn lg n)，因此如何去掉末尾的“c”？我认为大 Omega 符号会有所帮助，我可以忽略“c”，但我的老师说“根据定义 [我不知道哪个定义] 很重要”

Answer 1

是的，您的解决方案是正确的。是的，你可以忽略常量。 Omega(c * n * log n) 如果 c 是常数(根据定义 f(n) = Omega(g(n)) 如果存在这样的 C0 > 0 和 N0 对于任何 n >= N0 f(n) >= C0 * g(n). 如果我们有 g'(n) = c * g(n) , 我们可以只选择 C0' = C0 * c).