我有一个任务,只是有点小问题,但我找不到答案。
通过使用递归树解释解决方案:
t(n)=t(n/3)+t(2n/3)+cn
其中c是常数,是ω(n lg n)
我的解决方案:
一t(n)=t(n/3)+t(2n/3)+cn的递归树
最短路径将是最左边的路径,因为它以最小的值运行,而最右边的路径将是最长的路径,这意味着树是不平衡的。
最短路径可以定义为:
n->1/3 n->(1/3)^2 n->…>.1
递归树上的cn值:
每个完整级别的总和等于cn。
最短路径中的元素被3除,因此此路径的长度将等于logu 3n。因此,如果最短路径的递归树的完整级别数等于logu 3n,则表示此路径的算法成本将为:
T(n)=cn log_3 n=ω(cn lg n)
这个解决方案正确吗如何在最后去掉“c”,因为任务是解释Ω(n\lgn)而不是Ω(cn lgn)?我以为大欧米茄符号会有帮助,我可以忽略“c”,但我的老师说“根据定义(我不知道哪个定义)常数很重要”
最佳答案
是的,你的解决方案是正确的。是的,你可以忽略常数。Omega(c * n * log n)
与Omega(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
)。
关于algorithm - 具有常数的递归树-T(n)= T(n/3)+ T(2n/3)+ cn,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28090361/