解决递归T（N）=日志（T（N-1））+ 1

我试图解决这个递归：解决递归T（N）=日志（T（N-1））+ 1

      T(n)=log(T(n-1))+1 :n>2 
          T(n)=O(1)    :n=2

我得到O（1）的答案，但我觉得我错过了一些东西。

我很乐意获得一些帮助。

在此先感谢！

来源

2016-03-01 sky_knight

'n'有什么限制吗？ “0”还是什么？你的代码在哪里？ –

谢谢我编辑了这篇文章。 –

你现在还不清楚你在问什么。没有代码表明你甚至在尝试！ 'T（n）= O（1）：n = 2'那是什么？ 'T（2）= O（1）'什么？ –

你的递推关系收敛至1.0的任何值> = 1.0

你的答案Ô（1）是相当正确的。递归关系可以用这种简单的方式表达出来，而不是被赋予算法吗？

让我再试一次。另外，也许我们都有点困惑。我在单一电话层面回答;也许你需要整体的答案（更可能的是，现在我想到了）。

首先，让我们来一个电话。如果n = 2，那是恒定的时间。如果n> 2 ...这是我对符号不太熟悉的地方。这是表示调用单个的时间，还是表示整个递归序列降至n = 2？由于实际考虑，我认为它必须针对单个呼叫。这使我以前的答案不正确。

看看n = 3的呼叫。此膨胀并解决了作为

T(3) = log(T(2)) + 1 
T(3) = log(1) + 1 
T(3) = 0 + 1 = 1

通过感应T（N）= 1对于n> = 2。事实证明，即使基础案例 - T（2） - 具有除1以外的值，只要它是有限的并且超过1 /（无论我们用于日志的基础是什么），该系列将会收敛到1，并且每个呼叫将保持不变。因此，要解决T（n），我们有n-2个调用，每个调用都是T（1）。这给出了总体复杂度为O（n）。

更清楚了吗？

来源

2016-03-01 22:24:35 Prune

非常感谢您的回答。尽管如此，解决方案对我来说依然没有意义。 –

非常感谢您的扩展。根据你的解释，我通过归纳了解到：如果T（n-1）= 1，那么： T（n）= log（T（n-1））+ 1 = log（1）+1 = 1。所以T（n）= O（1）。这似乎不适合我。当c是某个常数时，T（n-1）= c，并且然后：T（n）= log（T（n-1）+1 = log（c）+1 其不等于O （1）？ –

解决递归T（N）=日志（T（N-1））+ 1

回答

相关问题