浅谈时间复杂度与空间复杂度_论文中时间复杂度

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

第一次进入数据结构，不可避免的就是时间复杂度与空间复杂度，这篇文章就来浅浅入门一下这两个概念。

---

一、时间、空间复杂度是什么？

• 时间复杂度主要衡量一个算法的运行快慢。例如运行一次for循环语句。
• 空间复杂度主要衡量一个算法运行所需要的额外空间。例如新建变量。

二、时间复杂度

1.定义：

准确来说是一种数学函数，就像数学一样找到关于一个变量（通常取n）的函数，例如：F(n)=n^{2}+2*n+10，算法中的基本操作的执行次数，为算法
的时间复杂度。

2.大0渐进法

然而，我们并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
所以上面的F(n)=n²+2*n+10就可以缩写为O(n²)

3.三种情况

时间复杂度分为三种情况

1. 最好情况
2. 最坏情况
3. 平均情况

例如快速查找法有时可能一次就找到了想要的数字，这就是最好情况，但是往往我们都会说这个算法的最坏情况。

4.举例说明

//代码1
void Func2(int N)
{
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {
 ++count;
 }
 int M = 10;
 while (M--)
 {
 ++count;
 }
 printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码1的时间复杂度为2N+10；估记为O(N)

//代码2
void Func3(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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码2由于M与N都是变量不是常数，所以不可省略时间复杂度为O(M+N)

//代码3
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10

代码3由于100是常数 所以记为O(1)

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]：begin和end是左闭右闭区间，因此有=号
 while (begin <= end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid-1;
 else
 return mid;
 }
 return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二分查找基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。
即使二分查找复杂度很低，但是由于二分查找的前提是排序，排序需要的准备工作过多，所以不经常使用。

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

此代码段通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。

三、空间复杂度

空间复杂度比时间复杂度简单的多，也是一个数字表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。
函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因
此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

1.举例说明

// 计算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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

由于此代码段只开辟了N个空间 故空间复杂度为O(N);

四、结尾

这只是一个开端，后面还需更加深入，敬请期待。