咱把递归算法的时间复杂度和空间复杂度讲清楚！

2023-03-19 16:59| 来源: 网络整理| 查看: 265

相信很多小伙伴刷题的时候面对力扣上近两千道题目，感觉无从下手，我花费半年时间整理了Github项目：

里面有200道经典算法题目刷题顺序、配有60w字的详细图解，常用算法模板总结，以及难点视频讲解，按照list一道一道刷就可以了！star支持一波吧！

之前在

中详细讲解了递归算法的时间复杂度，但没有讲空间复杂度。

本篇讲通过求斐波那契数列和二分法再来深入分析一波递归算法的时间和空间复杂度，细心看完，会刷新对递归的认知！

递归求斐波那契数列的性能分析

先来看一下求斐波那契数的递归写法。

int fibonacci(int i) { if(i

从图中，可以看出f(5)是由f(4)和f(3)相加而来，那么f(4)是由f(3)和f(2)相加而来以此类推。

在这颗二叉树中每一个节点都是一次递归，那么这棵树有多少个节点呢？

我们之前也有说到，一棵深度（按根节点深度为1）为k的二叉树最多可以有 2^k - 1 个节点。

所以该递归算法的时间复杂度为 O(2^n) ，这个复杂度是非常大的，随着n的增大，耗时是指数上升的。

来做一个实验，大家可以有一个直观的感受。

以下为C++代码，来测一下，让我们输入n的时候，这段递归求斐波那契代码的耗时。

#include #include #include using namespace std; using namespace chrono; int fibonacci(int i) { if(i > n) { milliseconds start_time = duration_cast( system_clock::now().time_since_epoch() ); fibonacci(n); milliseconds end_time = duration_cast( system_clock::now().time_since_epoch() ); cout

【本文地址】

公司简介

联系我们