时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储空间很小，所以对空间复杂度很是在乎。但是随着计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以如今已经不需要再特别关注一个算法的空间复杂度。这就是为什么我们大多时候听到的是时间复杂度，而很少听到空间复杂度的原因。

什么是大O

这里的大O是指什么?说到时间复杂度，大家都知道O(n),O(n^2),却说不清什么是大O.

算法导论中说道:大O是用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论中给出了例子:拿插入排序来说，插入排序的时间复杂度为O(n^2).

输入数据的形式对程序运算时间是有很大影响的，在数据本来就有序的情况下时间复杂度为O(n),但如果数据是逆序的话，插入排序的时间复杂度就是O(n^2),也就对于所有输入情况来说，最坏是O(n^2)的时间复杂度，所以称插入排序的时间复杂度为O(n^2)。

同样的同理再看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，所以严格从大O的定义来讲，快速排序的时间复杂度应该O(n^2)。

但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。如图所示：

我们主要关心的还是一般情况下的数据形式。

面试中说道算法的时间复杂度是多少指的都是一般情况。但是如果面试官和我们深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的，这一点是一定要注意的。

时间复杂度分析

概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

先来看看下面这串代码，计算一下Func1中++count语句总共执行了多少次?


void Func1(int N)
{
	int count = 0;
	//代码1
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	//代码2
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	//代码3
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

在代码1中++count执行了N*N次
在代码2中++count执行了N次
在代码2中++count执行了10次
所以总共执行次数为（N^2+N+10）次。
我们得到只有一个函数关系：
F(N)=N^2+N+10

当N足够大时F(N)的大小主要由N^2决定，实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，所以这里我们使用大O的渐进表示法。
什么是大O渐进表示法呢？

大O渐进表示法

大O符号:用于描述函数渐进行为的数学符号。

推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

所以上面所说的F(N)=N^2+N+10函数用大O渐进表示法得到的结果是O(N ^ 2)，这样我们就舍去了影响不大的项，简单明了地表示出了执行的次数。

不同数据规模的差异

如下图中可以看出不同算法的时间复杂度在不同数据输入规模下的差异。

在决定使用哪些算法的时候，不是时间复杂越低的越好(因为简化后的时间复杂度忽略了常数项等等), 要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适(在有常数项的时候)。

就像上图中 O(5n^2) 和 O(100n) 在n为20之前很明显 O(5n^2)是更优的，所花费的时间也是最少的。

那为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度，而且要默认O(n) 优于O(n^2) 呢？

这里就又涉及到大O的定义，因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

例如上图中20就是那个点，n只要大于20 常数项系数已经不起决定性作用了。

所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

但是也要注意大常数，如果这个常数非常大，例如10^7 ，10^9 ，那么常数就是不得不考虑的因素了。

复杂表达式的化简

有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2)，而是一个复杂的表达式，例如：

O(2*n^2 + 10*n + 1000)

那这里如何描述这个算法的时间复杂度呢，一种方法就是简化法。

去掉运行时间中的加法常数项（因为常数项并不会因为n的增大而增加计算机的操作次数）。

O(2*n^2 + 10*n)

去掉常数系数（上文中已经详细讲过为什么可以去掉常数项的原因）。

O(n^2 + n)

只保留保留最高项，去掉数量级小一级的n （因为n^2 的数据规模远大于n），最终简化为：

O(n^2)

所以最后我们说：这个算法的算法时间复杂度是O(n^2) 。

O(logn)中的log是以什么为底?

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

为什么可以这么做呢？如下图所示：

假如有两个算法的时间复杂度，分别是log以2为底n的对数和log以10为底n的对数，那么这里如果还记得高中数学的话，应该不难理解以2为底n的对数 = 以2为底10的对数 * 以10为底n的对数。

而以2为底10的对数是一个常数，在上文已经讲述了我们计算时间复杂度是忽略常数项系数的。

抽象一下就是在时间复杂度的计算过程中，log以i为底n的对数等于log 以j为底n的对数，所以忽略了i，直接说是logn。

这样就应该不难理解为什么忽略底数了。

案例分析

案例1:


void Func1(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

时间复杂度:

第一个循环执行了2*N次，第二个循环执行了10次。总共执行了 2 * N+10次。
最高阶项是2 * N，所以时间复杂度是O(N)。

案例2


void Func2(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

时间复杂度:

第一个循环执行了M次，第二个循环执行了N次。总共执行了 M+N次。
最高阶项是M和N，所以时间复杂度是O(M+N)
当M>>N时，时间复杂度是O(M)
当M近似等于N时，时间复杂度是O(M+N)
当M<<N时，时间复杂度是O(N)

案例3:


void Func3(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

时间复杂度

这个循环执行了100次，总共执行了100次。
最高阶项是100，执行次数为常数次，所以时间复杂度是O(1)。

案例4


// 计算strchr的时间复杂度？
const char * strchr(const char * str, int character);

strchr是一个在字符串中查找某个字符的算法，计算strchr的时间复杂度？

在一个字符串中查找一个字符，肯定要变量这个字符串，所以会利用循环，遍历长度次，由于长度是未知的，所以最高阶项N。
最好是1，最坏是N，平均是N/2，由于时间复杂度的计算看的是最坏的情况，所以时间复杂度是O(N)。

时间复杂度:

这个循环执行了100次，总共执行了100次。
最高阶项是100，执行次数为常数次，所以时间复杂度是O(1)。

案例5


void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

时间复杂度

执行次数为(n-1)+…2+1
这是一个等查数列求和，结果是n *（n-1）/2。
最高阶项是N ^ 2，所以时间复杂度是O(N ^ 2)

案例6


int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

二分查找算法的时间复杂度

N/2/2/2..../2/2=1

假设除了n次2，所以有:N/2^n=1->N=2^n

n=log2(N)

所以计算得到时间复杂度为:O(logN)

案例7


// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1)*N;
}

计算阶乘递归Fac的时间复杂度?

计算F(N)，利用递归调用F(N) = N*F(N-1)
F(N-1) = (N-1) * F(N-2)
F(N-2) = (N-2) * F(N-3)
…
F(2) = 2 * F(1)
F(1) = 1
这样一共递归调用了N次，所以时间复杂度是O(N)。

案例8


// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

时间复杂度

调用次数求得:2^0+2^1...2^(n-1)=2^n-1

时间复杂度为:O(2^n)

算法为什么会超时

一些同学可能对计算机运行的速度还没有概念，就是感觉计算机运行速度应该会很快，那么在leetcode上做算法题目的时候为什么会超时呢？

计算机究竟1s可以执行多少次操作呢？接下来探讨一下这个问题。

大家在leetcode上练习算法的时候应该都遇到过一种错误是“超时”。

也就是说程序运行的时间超过了规定的时间，一般OJ（online judge）的超时时间就是1s，也就是用例数据输入后最多要1s内得到结果，暂时还不清楚leetcode的判题规则，下文为了方便讲解，暂定超时时间就是1s。

如果写出了一个$O(n)$的算法，其实可以估算出来n是多大的时候算法的执行时间就会超过1s了。

如果n的规模已经足够让$O(n)$的算法运行时间超过了1s，就应该考虑log(n)的解法了。

计算机的运算速度主要看CPU的配置，以2015年MacPro为例，CPU配置：2.7 GHz Dual-Core Intel Core i5 。

也就是 2.7 GHz 奔腾双核，i5处理器，GHz是指什么呢，1Hz = 1/s，1Hz 是CPU的一次脉冲（可以理解为一次改变状态，也叫时钟周期），称之为为赫兹，那么1GHz等于多少赫兹呢

1GHz（兆赫）= 1000MHz（兆赫）
1MHz（兆赫）= 1百万赫兹

所以 1GHz = 10亿Hz，表示CPU可以一秒脉冲10亿次（有10亿个时钟周期），这里不要简单理解一个时钟周期就是一次CPU运算。

例如1 + 2 = 3，cpu要执行四次才能完整这个操作，步骤一：把1放入寄存机，步骤二：把2放入寄存器，步骤三：做加法，步骤四：保存3。

而且计算机的cpu也不会只运行我们自己写的程序上，同时cpu也要执行计算机的各种进程任务等等，我们的程序仅仅是其中的一个进程而已。

所以我们的程序在计算机上究竟1s真正能执行多少次操作呢？

在写测试程序测1s内处理多大数量级数据的时候，有三点需要注意：

CPU执行每条指令所需的时间实际上并不相同，例如CPU执行加法和乘法操作的耗时实际上都是不一样的。
现在大多计算机系统的内存管理都有缓存技术，所以频繁访问相同地址的数据和访问不相邻元素所需的时间也是不同的。
计算机同时运行多个程序，每个程序里还有不同的进程线程在抢占资源。

尽管有很多因素影响，但是还是可以对自己程序的运行时间有一个大体的评估的。

所以任何开发计算机程序员的软件工程师都应该能够估计这个程序的运行时间是一秒钟还是一年。

这个是最基本的，所以以上误差就不算事了。

以下以C++代码为例：

测试硬件：2015年MacPro，CPU配置：2.7 GHz Dual-Core Intel Core i5

实现三个函数，时间复杂度分别是 $O(n)$ , $O(n^2)$, $O(n\log n)$，使用加法运算来统一测试。


// O(n)
void function1(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        k++;
    }
}
// O(n^2)
void function2(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            k++;
        }
    }
 
}
// O(nlogn)
void function3(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 1; j < n; j = j*2) { // 注意这里j=1
            k++;
        }
    }
}

来看一下这三个函数随着n的规模变化，耗时会产生多大的变化，先测function1 ，就把 function2 和 function3 注释掉


int main() {
    long long n; // 数据规模
    while (1) {
        cout << "输入n：";
        cin >> n;
        milliseconds start_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        function1(n);
//        function2(n);
//        function3(n);
        milliseconds end_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        cout << "耗时:" << milliseconds(end_time).count() - milliseconds(start_time).count()
            <<" ms"<< endl;
    }
}

来看一下运行的效果，如下图:

O(n)的算法，1s内大概计算机可以运行 5 * (10^8)次计算，可以推测一下$O(n^2)$ 的算法应该1s可以处理的数量级的规模是 5 * (10^8)开根号，实验数据如下。

O(n^2)的算法，1s内大概计算机可以运行 22500次计算，验证了刚刚的推测。

在推测一下$O(n\log n)$的话， 1s可以处理的数据规模是什么呢？

理论上应该是比 $O(n)$少一个数量级，因为$\log n$的复杂度其实是很快，看一下实验数据。

$O(n\log n)$的算法，1s内大概计算机可以运行 2 * (10^7)次计算，符合预期。

时间复杂度	1S内可以处理的大概n的规模
O(n)	5*10^8
O(n^2)	2.25*10^4
O(nlogn)	2*10^7

递归算法的时间复杂度

相信很多同学对递归算法的时间复杂度都很模糊，那么这篇来给大家通透的讲一讲。

同一道题目，同样使用递归算法，有的同学会写出了O(n)的代码，有的同学就写出了O(logn)的代码。

这是为什么呢？

如果对递归的时间复杂度理解的不够深入的话，就会这样！

那么我通过一道简单的面试题，模拟面试的场景，来带大家逐步分析递归算法的时间复杂度，最后找出最优解，来看看同样是递归，怎么就写成了O(n)的代码。

面试题：求x的n次方

想一下这么简单的一道题目，代码应该如何写呢。最直观的方式应该就是，一个for循环求出结果，代码如下：


int function1(int x, int n) {
    int result = 1;  // 注意 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

时间复杂度为O(n)，此时面试官会说，有没有效率更好的算法呢。

如果此时没有思路，不要说：我不会，我不知道了等等。

可以和面试官探讨一下，询问：“可不可以给点提示”。面试官提示：“考虑一下递归算法”。

那么就可以写出了如下这样的一个递归的算法，使用递归解决了这个问题。


int function2(int x, int n) {
    if (n == 0) {
        return 1; // return 1 同样是因为0次方是等于1的
    }
    return function2(x, n - 1) * x;
}

面试官问：“那么这个代码的时间复杂度是多少？”。

一些同学可能一看到递归就想到了O(log n)，其实并不是这样，递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。

那再来看代码，这里递归了几次呢？

每次n-1，递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1)，所以这份代码的时间复杂度是 n × 1 = O(n)。

这个时间复杂度就没有达到面试官的预期。于是又写出了如下的递归算法的代码：


int function3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return function3(x, n / 2) * function3(x, n / 2)*x;
    }
    return function3(x, n / 2) * function3(x, n / 2);
}

面试官看到后微微一笑，问：“这份代码的时间复杂度又是多少呢？” 此刻有些同学可能要陷入了沉思了。

我们来分析一下，首先看递归了多少次呢，可以把递归抽象出一棵满二叉树。刚刚同学写的这个算法，可以用一棵满二叉树来表示（为了方便表示，选择n为偶数16）。

当前这棵二叉树就是求x的n次方，n为16的情况，n为16的时候，进行了多少次乘法运算呢？

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以进行了多少次递归的话，就是看这棵树上有多少个节点。

熟悉二叉树话应该知道如何求满二叉树节点数量，这棵满二叉树的节点数量就是2^3 + 2^2 + 2^1 + 2^0 = 15，可以发现：这其实是等比数列的求和公式，这个结论在二叉树相关的面试题里也经常出现。

这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示：(m为深度，从0开始)

时间复杂度忽略掉常数项-1之后，这个递归算法的时间复杂度依然是O(n)。对，你没看错，依然是O(n)的时间复杂度！

此时面试官就会说：“这个递归的算法依然还是O(n)啊”，很明显没有达到面试官的预期。

那么O(logn)的递归算法应该怎么写呢？

想一想刚刚给出的那份递归算法的代码，是不是有哪里比较冗余呢，其实有重复计算的部分。

于是又写出如下递归算法的代码：


int function4(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

再来看一下现在这份代码时间复杂度是多少呢？

依然还是看他递归了多少次，可以看到这里仅仅有一个递归调用，且每次都是n/2 ，所以这里我们一共调用了log以2为底n的对数次。

每次递归了做都是一次乘法操作，这也是一个常数项的操作，那么这个递归算法的时间复杂度才是真正的O(logn)。

此时大家最后写出了这样的代码并且将时间复杂度分析的非常清晰，相信面试官是比较满意的。

空间复杂度分析

概念

什么是空间复杂度呢？

是对一个算法在运行过程中占用内存空间大小的量度，记做S(n)=O(f(n)。

空间复杂度(Space Complexity)记作S(n) 依然使用大O来表示。利用程序的空间复杂度，可以对程序运行中需要多少内存有个预先估计。

关注空间复杂度有两个常见的相关问题

空间复杂度是考虑程序（可执行文件）的大小么？

很多同学都会混淆程序运行时内存大小和程序本身的大小。这里强调一下空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。

2.空间复杂度是准确算出程序运行时所占用的内存么？

不要以为空间复杂度就已经精准的掌握了程序的内存使用大小，很多因素会影响程序真正内存使用大小，例如编译器的内存对齐，编程语言容器的底层实现等等这些都会影响到程序内存的开销。

所以空间复杂度是预先大体评估程序内存使用的大小。

说到空间复杂度，我想同学们在OJ（online judge）上应该遇到过这种错误，就是超出内存限制，一般OJ对程序运行时的所消耗的内存都有一个限制。

为了避免内存超出限制，这也需要我们对算法占用多大的内存有一个大体的预估。

同样在工程实践中，计算机的内存空间也不是无限的，需要工程师对软件运行时所使用的内存有一个大体评估，这都需要用到算法空间复杂度的分析。

来看一下例子，什么时候的空间复杂度是$O(1)$呢，C++代码如下：


int j = 0;
for (int i = 0; i < n; i++) {
    j++;
}

第一段代码可以看出，随着n的变化，所需开辟的内存空间并不会随着n的变化而变化。即此算法空间复杂度为一个常量，所以表示为大O(1)。

什么时候的空间复杂度是O(n)？

当消耗空间和输入参数n保持线性增长，这样的空间复杂度为O(n)，来看一下这段C++代码


int* a = new int(n);
for (int i = 0; i < n; i++) {
    a[i] = i;
}

我们定义了一个数组出来，这个数组占用的大小为n，虽然有一个for循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，随着n的增大，开辟的内存大小呈线性增长，即 O(n)。

其他的 O(n^2)， O(n^3) 我想大家应该都可以以此例举出来了，那么思考一下什么时候空间复杂度是 O(logn)呢？

空间复杂度是logn的情况确实有些特殊，其实是在递归的时候，会出现空间复杂度为logn的情况。

案例分析

示例1


// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

空间复杂度

这串代码中开辟了exchange，end和i三个变量的空间，也就是常数个空间，所以空间复杂度是O(1)

示例2:


// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
	if (n == 0)
		return NULL;
	long long * fibArray = (long long *)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}

空间复杂度

这里动态内存申请了一块（n+1）个大小的空间，其它都是常数次，所以空间复杂度为O(N)

示例3


// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
	if (N == 0)
		return 1;
	return Fac(N - 1)*N;
}

空间复杂度

计算F(N)，利用递归调用F(N) = N*F(N-1)
F(N-1) = (N-1) * F(N-2)
F(N-2) = (N-2) * F(N-3)
…
F(2) = 2 * F(1)
F(1) = 1
这样一共递归开辟了N个函数栈帧，所以空间复杂度是O(N)。

示例4


// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

空间复杂度

上面我们也分析过了，这个函数会递归调用2^n-1次，会建立 2 ^ n-1次函数栈帧，所以说空间复杂度是O(2 ^ n)吗？
当然不能这样想，因为空间是可以重复利用，然而时间是一区不复返的。有一部分栈帧是利用同一块空间，最多利用N个函数栈帧的空间，所以空间复杂度是O(N)。

递归算法的性能分析

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


int fibonacci(int i) {
       if(i <= 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonacci(i-2);
}

对于递归算法来说，代码一般都比较简短，从算法逻辑上看，所用的存储空间也非常少，但运行时需要内存可不见得会少。

时间复杂度分析

来看看这个求斐波那契的递归算法的时间复杂度是多少呢？

在讲解递归时间复杂度的时候，我们提到了递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。

可以看出上面的代码每次递归都是O(1)的操作。再来看递归了多少次，这里将i为5作为输入的递归过程抽象成一棵递归树

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

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

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

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

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

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


#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace chrono;
int fibonacci(int i) {
       if(i <= 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i - 1) + fibonacci(i - 2);
}
void time_consumption() {
    int n;
    while (cin >> n) {
        milliseconds start_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
 
        fibonacci(n);
 
        milliseconds end_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        cout << milliseconds(end_time).count() - milliseconds(start_time).count()
            <<" ms"<< endl;
    }
}
int main()
{
    time_consumption();
    return 0;
}

根据以上代码，给出几组实验数据：

测试电脑以2015版MacPro为例，CPU配置：2.7 GHz Dual-Core Intel Core i5

测试数据如下：

n = 40，耗时：837 ms
n = 50，耗时：110306 ms

可以看出，O(2^n)这种指数级别的复杂度是非常大的。

所以这种求斐波那契数的算法看似简洁，其实时间复杂度非常高，一般不推荐这样来实现斐波那契。

其实罪魁祸首就是这里的两次递归，导致了时间复杂度以指数上升。

return fibonacci(i-1) + fibonacci(i-2);

可不可以优化一下这个递归算法呢。主要是减少递归的调用次数。

来看一下如下代码：


// 版本二
int fibonacci(int first, int second, int n) {
    if (n <= 0) {
        return 0;
    }
    if (n < 3) {
        return 1;
    }
    else if (n == 3) {
        return first + second;
    }
    else {
        return fibonacci(second, first + second, n - 1);
    }
}

这里相当于用first和second来记录当前相加的两个数值，此时就不用两次递归了。

因为每次递归的时候n减1，即只是递归了n次，所以时间复杂度是 O(n)。

同理递归的深度依然是n，每次递归所需的空间也是常数，所以空间复杂度依然是O(n)。

代码（版本二）的复杂度如下：

时间复杂度：O(n)
空间复杂度：O(n)

此时再来测一下耗时情况验证一下：


#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace chrono;
int fibonacci_3(int first, int second, int n) {
    if (n <= 0) {
        return 0;
    }
    if (n < 3) {
        return 1;
    }
    else if (n == 3) {
        return first + second;
    }
    else {
        return fibonacci_3(second, first + second, n - 1);
    }
}
 
void time_consumption() {
    int n;
    while (cin >> n) {
        milliseconds start_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
 
        fibonacci_3(1, 1, n);
 
        milliseconds end_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        cout << milliseconds(end_time).count() - milliseconds(start_time).count()
            <<" ms"<< endl;
    }
}
int main()
{
    time_consumption();
    return 0;
}

测试数据如下：

n = 40，耗时：0 ms
n = 50，耗时：0 ms

大家此时应该可以看出差距了！！

空间复杂度分析

说完了这段递归代码的时间复杂度，再看看如何求其空间复杂度呢，这里给大家提供一个公式：递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

为什么要求递归的深度呢？

因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

此时可以分析这段递归的空间复杂度，从代码中可以看出每次递归所需要的空间大小都是一样的，所以每次递归中需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度就是$O(1)$。

在看递归的深度是多少呢？如图所示：

递归第n个斐波那契数的话，递归调用栈的深度就是n。

那么每次递归的空间复杂度是O(1)，调用栈深度为n，所以这段递归代码的空间复杂度就是O(n)。


int fibonacci(int i) {
       if(i <= 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonacci(i-2);
}

最后对各种求斐波那契数列方法的性能做一下分析，如题：

可以看出，求斐波那契数的时候，使用递归算法并不一定是在性能上是最优的，但递归确实简化的代码层面的复杂度。

二分法(递归实现)的性能分析

带大家再分析一段二分查找的递归实现。


int binary_search( int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x);
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}

都知道二分查找的时间复杂度是O(logn)，那么递归二分查找的空间复杂度是多少呢？

我们依然看 每次递归的空间复杂度和递归的深度

每次递归的空间复杂度可以看出主要就是参数里传入的这个arr数组，但需要注意的是在C/C++中函数传递数组参数，不是整个数组拷贝一份传入函数而是传入的数组首元素地址。

也就是说每一层递归都是公用一块数组地址空间的，所以每次递归的空间复杂度是常数即：O(1)。

再来看递归的深度，二分查找的递归深度是logn ，递归深度就是调用栈的长度，那么这段代码的空间复杂度为 1 * logn = O(logn)。

大家要注意自己所用的语言在传递函数参数的时，是拷贝整个数值还是拷贝地址，如果是拷贝整个数值那么该二分法的空间复杂度就是O(nlogn)。

代码的内存消耗

不同的编程语言各自的内存管理方式。

C/C++这种内存堆空间的申请和释放完全靠自己管理
Java 依赖JVM来做内存管理，不了解jvm内存管理的机制，很可能会因一些错误的代码写法而导致内存泄漏或内存溢出
Python内存管理是由私有堆空间管理的，所有的python对象和数据结构都存储在私有堆空间中。程序员没有访问堆的权限，只有解释器才能操作。

例如Python万物皆对象，并且将内存操作封装的很好，所以python的基本数据类型所用的内存会要远大于存放纯数据类型所占的内存，例如，我们都知道存储int型数据需要四个字节，但是使用Python 申请一个对象来存放数据的话，所用空间要远大于四个字节。

以C++为例来介绍一下编程语言的内存管理。

如果我们写C++的程序，就要知道栈和堆的概念，程序运行时所需的内存空间分为固定部分，和可变部分，如下：

固定部分的内存消耗是不会随着代码运行产生变化的，可变部分则是会产生变化的

更具体一些，一个由C/C++编译的程序占用的内存分为以下几个部分：

栈区(Stack) ：由编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构中的栈。
堆区(Heap) ：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS收回
未初始化数据区(Uninitialized Data)：存放未初始化的全局变量和静态变量
初始化数据区(Initialized Data)：存放已经初始化的全局变量和静态变量
程序代码区(Text)：存放函数体的二进制代码

代码区和数据区所占空间都是固定的，而且占用的空间非常小，那么看运行时消耗的内存主要看可变部分。

在可变部分中，栈区间的数据在代码块执行结束之后，系统会自动回收，而堆区间数据是需要程序员自己回收，所以也就是造成内存泄漏的发源地。

而Java、Python的话则不需要程序员去考虑内存泄漏的问题，虚拟机都做了这些事情。

想要算出自己程序会占用多少内存就一定要了解自己定义的数据类型的大小，如下：

再介绍一下内存管理中另一个重要的知识点：内存对齐。

不要以为只有C/C++才会有内存对齐，只要可以跨平台的编程语言都需要做内存对齐，Java、Python都是一样的。

而且这是面试中面试官非常喜欢问到的问题，就是：为什么会有内存对齐？

主要是两个原因

平台原因：不是所有的硬件平台都能访问任意内存地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。为了同一个程序可以在多平台运行，需要内存对齐。
硬件原因：经过内存对齐后，CPU访问内存的速度大大提升。

可以看一下这段C++代码输出的各个数据类型大小是多少？


struct node{
   int num;
   char cha;
}st;
int main() {
    int a[100];
    char b[100];
    cout << sizeof(int) << endl;
    cout << sizeof(char) << endl;
    cout << sizeof(a) << endl;
    cout << sizeof(b) << endl;
    cout << sizeof(st) << endl;
}

看一下和自己想的结果一样么，我们来逐一分析一下。

其输出的结果依次为：

此时会发现，和单纯计算字节数的话是有一些误差的。

这就是因为内存对齐的原因。

来看一下内存对齐和非内存对齐产生的效果区别。

CPU读取内存不是一次读取单个字节，而是一块一块的来读取内存，块的大小可以是2，4，8，16个字节，具体取多少个字节取决于硬件。

假设CPU把内存划分为4字节大小的块，要读取一个4字节大小的int型数据，来看一下这两种情况下CPU的工作量：

第一种就是内存对齐的情况，如图：

一字节的char占用了四个字节，空了三个字节的内存地址，int数据从地址4开始。

此时，直接将地址4，5，6，7处的四个字节数据读取到即可。

第二种是没有内存对齐的情况如图：

char型的数据和int型的数据挨在一起，该int数据从地址1开始，那么CPU想要读这个数据的话来看看需要几步操作：

因为CPU是四个字节四个字节来寻址，首先CPU读取0，1，2，3处的四个字节数据
CPU读取4，5，6，7处的四个字节数据
合并地址1，2，3，4处四个字节的数据才是本次操作需要的int数据

此时一共需要两次寻址，一次合并的操作。

大家可能会发现内存对齐岂不是浪费的内存资源么？

是这样的，但事实上，相对来说计算机内存资源一般都是充足的，我们更希望的是提高运行速度。

编译器一般都会做内存对齐的优化操作，也就是说当考虑程序真正占用的内存大小的时候，也需要认识到内存对齐的影响。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/632295