嗨，我很难展示T(n)的这三种算法的运行时间。假设包括T(0)=0。
1) 我知道这一个接近Fibonacci，所以我知道它接近O(n)时间，但很难显示：T(n)=T(n-1)+T(n-2)+1
2) 关于这个，我很困惑，但我认为它大致是关于O(log log n)：T(n)＝T([sqrt(n)])+n.n大于或等于1。sqrt(n)是下界。
3) 我相信这个大约在O(n*log log n)中：T(n)=2T(n/2)+(n/(logn))+n。
感谢您提前提供的帮助。
T(n)=T(n-1)+T(n-2)+1
假设T(0)=0，T(1)=a，对于某个常数a，我们注意到T(n)-T(n-1)=T(n-2)+1。也就是说，函数的增长率是由函数本身给出的，这表明该函数具有指数增长。
设T’(n)=T(n)+1。然后T’(n)=T’(n-1)+T’(n-2)，通过上述递推关系，我们消除了麻烦的常数项。T(n)和U(n)相差一个常数因子1，因此假设它们都是非递减的(它们是)，那么它们将具有相同的渐近复杂度，尽管对于不同的常数n0。
为了证明T'(n)具有O(b^n)的渐近增长，我们需要一些基本情况，然后假设该条件适用于所有n，比如说，k-1，然后我们需要证明它适用于k，也就是说，cb^(n-2)+cb^(n-1)<cb^n。我们可以除以cb^(n-2)，将其简化为1+b<=b^2。重新排列，我们得到b^2-b-1>0；根是(1+-sqrt(5))/2，我们必须丢弃负数，因为我们不能使用负数作为指数的基数。因此，对于b>=(1+sqrt(5))/2，T'(n)可以是O(b^n)。类似的思维实验将表明，对于b<1+sqrt(5))/2，T'(n)可以是Omega(b^n)。因此，仅对于b=(1+sqrt(5))/2，T'(n)可以是Theta(b^n)。
通过归纳法完成证明T(n)=O(b^n)是一个练习。
T(n)=T([sqrt(n)])+n
显然，假设边界条件要求T(n)是非负的，T(n)至少是线性的。我们可以猜测T(n)是Theta(n)，并试图证明它。基本情况：设T(0)=a，T(1)=b。然后T(2)=b+2，T(4)=b+6。在这两种情况下，选择c>=1.5将使T(n)<假设无论我们的c的固定值是什么，都适用于直到并包括k的所有n。我们必须证明T([sqrt(k+1)])+(k+1c*(k+1)。我们知道T([sqrt(k+1)])<=csqrt(k+1)。所以T([sqrt(k+1)])+(k+1csqrt(k+1)+(k+1c(k+1)可以重写为cx+x^2<=cx^2(其中x=sqrt(k+1))；除以x(好的，因为k>1)，我们得到c+x<=cx，并且对c求解这个问题，我们得到c>=x/(x-1)=sqrt(k+1)/(sqrt(k=1)-1)。这最终接近1，所以对于足够大的n，任何常数c>1都会起作用。
通过修正以下几点来证明这一点是完全严格的，这只是一个练习：
- 确保有足够的基本情况得到证明，以便所有假设都成立
- 区分其中(a)k+1是完美正方形(因此[sqrt(k+1)]＝sqrt(k+1；[sqrt(k+1)]<sqrt(k+1))
T(n)=2T(n/2)+(n/(logn))+n
这个T(n)>2T(n/2)+n，我们知道它是Mergesort运行时的递归关系，根据主定理，它是O(n log n)，我们知道我们的复杂性不亚于此。
事实上，根据主定理：T(n)=2T(n/2)+(n/(logn))+n=2T
- a=2
- b=2
- f(n)=n(1+1/(logn))是O(n)(对于n>2，它总是小于2n)
- f(n)=O(n)=O(n^log_2(2)*log^0 n)
我们仍然处于主定理的情况2，因此渐近界与Mergesort的Theta(n-logn)相同。