算法的时间复杂度和空间复杂度

 算法效率

如何衡量一个算法的好坏

如何衡量一个算法的好坏呢？比如对于以下斐波那契数列

long long Fib(int N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

复杂度在校招中的考察

时间复杂度

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
 for (int j = 0; j < N ; ++ j)
 {
 ++count;
 }
}
 
for (int k = 0; k < 2 * N ; ++ k)
{
 ++count;
}
int M = 10;
while (M--)
{
 ++count;
}
printf("%d\n", count);
}

计算算法复杂度只需计算大概次数（量级）就可以了，比如这个合计是我们就取N^2作为其时间复杂度，因为当我们N足够大的时候，后边的低阶次方根本不算事，占比总次数可以忽略不计

大O的渐进表示法

总结：算法复杂度一般用大O的渐进表示法，计算结果取最大次方的项，并且一定要取最坏情况作为时间复杂度（比如我们要暴力求解N个数字找某一个随机值，for循环我们可能找一次就找到了，也可能找一半次数，也可能找N次最后一次才找到，时间复杂度肯定是取最坏O(N)，而不是取第一次就找到O(1)）；因为时间复杂度是一个稳健保守预期。

常见时间复杂度计算举例

依照对算法复杂度的总结，我们很轻松能算出来时间复杂度

注意常数次数统一是O(1)

接下来我们看几个我们熟悉的例子

冒泡排序，算法复杂度是O(N^2)，注意我们算这种略微复杂的函数时，要算其中心思想，而不是看代码，冒泡的算法思想就是每一轮循环至少将最大值排到最后，接着是次大值，也就是第一最坏要排序n-1次，第2轮最坏要排序n-2次（n是排序数字个数）。。。第n轮排1次

可以理解为一个等差数列1+2+。。+n  结果去最高次方项是n^2

我们看一下二分查找

二分查找的思想更简单了，每次找一半，最坏找到我们要查的数字时刚好结束，也就是2^x=N，x是次数，N是要查数据总个数，x=logN（注意）logN本质上是，因为我们平常很难打出来，所以统一将看成logN。

有些同学可能没有感受到logN的意义

如果N足够大，N是10亿，我们暴力搜索要搞10亿次，二分查找只需要30次（最坏情况）

更牛逼的是14亿数据二分查找只需要多查找1次，而暴力查找需要多查找4亿次！！

我们要知道这些的算法的优势，并且再关键时候可以用上它，提高我们的效率

接下来看一下关于递归的算法

递归的算法复杂度是函数调用累加（记住就好）调用次数总和是1+1+。。+n可以看做O(N)

这个是重头戏 O（2^N）通过画图讲解

前面说了递归时间复杂度是函数调用次数累加

累加结果是2^N-1，可以看成2^N

这个图就是我们算次数总和的抽象图，意思是右边的函数调用先结束，但是不影响我们总体的套用数学公式（计算等比数列求和）

以上就是我对时间复杂度的见解

空间复杂度

注意，我们计算空间复杂度要比时间复杂度好计算，只需计算函数体内新开辟的空间大小即可（函数参数不需要参与计算，在编译期间已经确定，我们要计算的是额外开辟的空间）

冒泡排序的空间复杂度很好计算，也就是图上标注的是新开辟的空间，常量个数所以是O(1)

（函数参数int* a和int n已经在编译期间确定，不需要算关于这两个的）

这个很简单malloc了n+1块空间，即O(N).还有一些局部变量开辟的 O(1)不需要计算，只算最高次方项

重点是关于递归的空间复杂计算（要记住计算的是开辟的空间深度，和宽度没有关系）

递归是要在栈上开辟很多栈帧的

比如N次调用会开辟N个空间所以空间复杂度是O(N)

很多人会以为斐波那契数列会开辟2的n次方空间，实则不然

空间是可以重复利用的

前面我说过计算的是开辟空间的深度，其实斐波那契和求阶乘递归的深度在参数是N的时候深度都是一样的，只不过斐波那契数列看起来复杂一点，实际上在最后一次函数调用建立栈帧结束要返回的时候，栈帧会销毁，紧接着下一次函数调用建立栈帧就会在这次销毁的地方建立并且复用，还理解不了的话就理解成空间是重复利用的就行，开辟的深度都是N层所以空间复杂度是O(N)

   我在举一个例子帮助理解函数栈帧的复用

void Func1()
{
	int a = 0;
	printf("%p\n", &a);
}

void Func2()
{
	int b = 1;
	printf("%p\n", &b);

}

int main()
{
	Func1();
	Func2();
	return 0;
}

我们很清晰的看到两个函数调用创建的栈帧是同一块空间的，Func1函数调用结束-》销毁栈帧-》调用Func2函数-》建立Func2函数建立栈帧，两个栈帧其实是重复利用的

经历这个例子应该很好理解栈帧的复用了吧

还有一个关键的栈溢出问题

代码样例

long long Fac(size_t N)
{
	if (0 == N)
		return 1;

	return Fac(N - 1) * N;
}

long long Fib(size_t N)
{
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}

int main()
{
	Fac(10000);
	//Fib(5);

	return 0;
}

深度太深的话，会建立深度个栈帧，假如要建立10000个栈帧，会消费大量的内存空间，可能在我们建立2000个左右栈帧的时候，程序就崩溃了（这就是经典的栈溢出问题）

可以看到我们建立5层栈帧是可以的，不会栈溢出（日常计算一般有个几百上千层栈帧就够了，不需要建立太多）

常见复杂度对比

一般算法常见的复杂度如下：

以上就是我对算法复杂度的讲解，以后会创作更多的作品

感谢大家的支持！！！