算法复杂度，解决递归方程

Question

我正在学习数据结构和算法课程，目前被这个递归方程卡住了：

T(n) = logn*T(logn) + n

显然，这个问题不能使用Master定理解决，因此我想知道是否有任何解决这个递归方程的想法。我相信它应该通过改变参数来解决，比如将n视为2 ^ m，但我无法找到任何好的修复方法。

- Ashkan Kazemi

---

我认为这些理由不足以证明这不是一个递归方程，因为毕竟T(n)取决于另一个T的值，这使得它成为递归方程。根据我们的教师，起始条件应该由自己猜测，有时甚至不需要起始条件，比如使用主定理。 - Ashkan Kazemi

准确地说，函数可以被递归定义，方程可以具有循环性。你试过枚举这个函数的一些值吗？聪明的猜测应该是首选，通过归纳法检查猜测是否正确是很容易的。 - DanielKO

谢谢你的纠正，但我对这个问题没有任何猜测，你有什么想法吗？ - Ashkan Kazemi

这个问题在这个主题中已经得到解决，链接为http://cs.stackexchange.com/questions/14775/recursive-equation-for-complexity-tn-logn-tlogn-n。 - Ashkan Kazemi

这个问题似乎不是关于编程的，因此被认为是不相关的。 - Johan Råde

Answer 1

这绝不是正式证明，但我认为它是这样的。

关键在于“+n”部分。由于这一点，T受到o(n)的下限约束。(或者应该是大omega?我有点生疏)。因此，让我们假设T(n)=O(n)，然后试着进行计算。

将其代入原始关系式中。

T(n) = (log n)O(log n) + n
     = O(log^2(n)) + O(n)
     = O(n)

所以它仍然有效。

- Worakarn Isaratham

---

这完全是错误的，我的朋友，我想给你投反对票，但我不能。 - Ashkan Kazemi

好的，我承认我对这个解决方案不太确定。能否详细说明一下？ - Worakarn Isaratham

我认为你的错误在于对于 T(logn) ，你不能仅仅写成 O(logn)，因为我们不知道函数 T(logn) 中 logn 会发生什么。 - Ashkan Kazemi

@AshkanKzme：为什么这个答案说T(n)是O(n)是“完全错误的”，当您在cs.SE上发布的问题的接受答案的解决方案也表明T(n)是O(n)吗？上面的回答中有一些符号滥用，但并不比问题本身所涉及的更多。 - hardmath

这是正确的。你可以通过说“假设对于n<5，T(n)<cn”，然后使用强归纳法来使它更加严谨。(是大omega) - Teepeemm

小心这种证明（归纳证明）和大O符号。简单的“假设这个或那个”的方法可能会产生错误的结果！ - phimuemue

Answer 2

答案是 Theta(n)。要证明某个东西是 Theta(n)，你必须展示它是 Omega(n) 和 O(n)。在这种情况下，Omega(n) 是显然的，因为 T(n)>=n。为了展示 T(n)=O(n)，首先：

1. 选择一个大的有限值 N，使得对于所有的 n>N，log(n)^2 < n/100。这是可能的，因为 log(n)^2=o(n)。
2. 选择一个常数 C>100，使得对于所有的 n<=N，T(n)<Cn。这是可能的，因为 N 是有限的。

我们将归纳地展示对于所有的 n>N，T(n)<Cn。由于 log(n)<n，根据归纳假设，我们有：

T(n) < n + log(n) C log(n) 
     = n + C log(n)^2
     < n + (C/100) n 
     = C * (1/100 + 1/C) * n
     < C/50 * n
     < C*n

事实上，对于这个函数，甚至可以使用类似的论证来展示T(n) = n + o(n)。

- mrip

---

兄弟，你的最终答案是正确的，但是你的证明有误！它不是logn^2，而是logn*T(logn)！我想你忘记了那个！ - Ashkan Kazemi

T(log n) < C log(n)可以从归纳假设得出。您熟悉归纳证明吗？http://en.wikipedia.org/wiki/Mathematical_induction - mrip

是的，当我检查我的教科书时发现你的方法是对的，而我错了。我犯了这个错误是因为你使用归纳法的方式略有不同于我学到的方法（比如选择常数c和n）。不管怎么样，谢谢。 - Ashkan Kazemi