algorithm - 我对关于 fibonacc 时间复杂度的解决方案感到困惑
问题描述
long fib(int n)
{
if (n <= 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
虽然我见过很多不同的解决方案,但其中一些对我来说没有意义。就像这个非常受欢迎的解决方案一样(我将整个内容粘贴到这里并感谢您的耐心等待,因为这需要一些时间)
让我们首先假设 T(n-2) ≈ T(n-1)。暂时不要担心为什么——这很快就会变得明显。
将 T(n-1) = T(n-2) 的值代入我们的关系 T(n),我们得到:
T(n) = T(n-1) + T(n-1) + 1 = 2T(n-1) + 1
通过这样做,我们将 T(n) 简化为更简单的递归。因此,我们现在可以使用反向替换来求解 T(n)。为此,我们首先将 T(n-1) 代入递归式的右侧。由于 T(n-1) = 2T(n-2) + 1,我们得到:
T(n) = 2[2T(n-2) + 1] + 1 = 4T(n-2) + 3
接下来,我们可以代入 T(n-2) = 2T(n-3) + 1:
T(n) = 2[2[2T(n-3) + 1] + 1] + 1 = 8T(n-3) + 7
对于 T(n-3) = 2T(n-4) + 1 再一次:
T(n) = 2[2[2[2T(n-4) + 1]+ 1] + 1] + 1 = 16T(n-4) + 15
我们可以看到这里开始出现一种模式,所以让我们尝试形成 T(n) 的一般解决方案。看来是这样的:
T(n) = 2kT(n–k) + (2k-1)
对于任何正整数 k。我们可以通过简单的归纳证明这个等式成立——为简洁起见,我们将跳过这个过程。
最后,我们可以通过代入 T(0) = 1 来找到 k,从而求解 T(n)。
对于 T(0),我们可以看到 n – k = 0。重新排列,我们得到 k = n。现在,将我们的值代入 T(0) 和 k,我们得到:
T(n) = 2nT(0) + (2n-1) = 2n + 2n – 1 = O(2n)
我的问题是为什么它可以用 0 代替 n。在我看来,当 n 达到 1 时程序将终止,因为 T(n-2) 已被 T(n-1) 替换。因此,不可能将 n 的值设为 0。
解决方案
添加了一个简单的 cout 语句。
考虑调用 f(2)
long fib(2)
{
std::cout<<n<<"\n";
if (2 <= 1)
return 1;
else{
return fib(1) + fib(0); --- > here there are two calls > fib(1) will return 1 and secod will be fib(0) which prints 0
}
}
f(2) 的输出
2
1
0
此外,请注意:
return fib(n - 1) + fib(n - 2);
上面的陈述不能保证你的评估顺序,所以对于 f(2) 没有顺序是否 f(1) 将被称为 f(0) 的第一个。
推荐阅读
- c# - 将 Animator 附加到克隆 GameObject
- python - 优化从每个可评估为列表的字符串列表中制作平面列表
- amazon-web-services - AWS Elasticsearch - 建议为 m4.large.elasticsearch 实例创建多少个分片和副本
- python - pyqt5 QTranslator() 在通过 pyinstaller 编译后加载不工作,但在 pycharm 运行它的工作
- css - 如何在不同的浏览器中测试奇怪的“字体大小”定义
- typescript - Office.initialize 在打字稿中
- laravel - 在 vps 上管理大约 5 个 laravel 网站的最佳方法是什么?
- alibaba-cloud - 恢复阿里云 ECS Linux 实例丢失的密钥对
- c++ - Windows 上的 Clang/LLVM 7 和 8 多次初始化内联静态数据成员(同时使用 link.exe 和 lld-link.exe)
- android - 仅当 minifyEnabled 设置为 true 时,应用程序因 java.lang.String.trim() 而崩溃