数据结构与算法初阶1：算法的时间复杂度和空间复杂度讲解_算法的空间复杂度为 ▁▁▁▁▁。 int foo(int n) { int i, j, s = 0;

目录

1、什么是算法的复杂度？

2、时间复杂度

3、大O的渐进表示法

4、时间复杂度算法练习

5、算法的空间复杂度

6、复杂度的OJ练习 

---

---

1、什么是算法的复杂度？

   我们在将算法编写成可执行程序的时候，运行时需要耗费时间资源和计算机内存(空间)资源，因此，在衡量算法的优劣需要从时间和空间两个维度来衡量，也就是本文将要介绍的时间复杂度和空间复杂度。

• 时间复杂度：其主要衡量一个算法运行的快慢问题；
• 空间复杂度：其主要衡量一个算法运行时所需要的额外空间。

   目前随着计算机存储容量的快速发展，对算法空间复杂度的关注点逐步降低，人们将注意力集中在时间复杂度方面。为了掌握好一个算法的优劣性，我们有必要掌握如何判断算法的复杂度问题，从而在今后的工作学习中，根据实际的需求选择出或写出最优算法。

2、时间复杂度

      在计算机科学中，时间复杂度是一个函数，它定量的描述了该算法的运行时间。但我们知道算法的运行时间在不同的硬件设备上运行时，会得到不同的结果，即在硬件好的平台上运行，同一个算法的运行时间和较差的硬件运行相比耗时很少。为此，我们需要换一种时间复杂度的分析方式：一个算法所花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，即为算法的时间复杂度。

      通俗来讲，就是在算法中找到某条基本语句与问题规模N之间的数学表达式，也就可以算出该算法近似的时间复杂度。

下面我们先来看一个例子，感受时间复杂度在算法中是如何识别出来的：

#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
void Func(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);
}
int main()
{
	//写一个统计次数的Func函数
	Func(10);
	return 0;
}
'
运行
运行

      从上图分析中，我们可以看出，函数Func中包含有四个循环，然后利用count计数，在该函数中经历的每一次循环都是时间上的叠加，Func函数执行的基本操作次数为：

        上述表达式表示的是Func函数在执行过程中具体的执行次数，但当我们遇到很复杂的函数时，这是准确的执行次数是不可行的，为此，我们一般采用简化的方式，只需要能大概表示出执行次数，在这里将引出另一个概念：大O的渐进表示法。

3、大O的渐进表示法

注：在上述的分析中，我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简