复杂度

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

时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。

在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译 器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。

2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。

3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

下面我们来看个案例：

// 请计算⼀下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; 
 } 
}

Func1执⾏的基本操作次数：

T (N) = N^2+2∗N+10

• N=10   T(N)=130

• N=100  T(N)=10210 

• N=1000  T(N)=1002010 

通过对N取值分析，对结果影响最⼤的⼀项是N^2。

实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤， 因为我么计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

大O渐进表示法

⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号。

推导大O阶的规则：

1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。

2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。

3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

通过以上⽅法，可以得到 Func1 的时间复杂度为：O(N^2)。

时间复杂度案例分析

案例一： 

// 计算Func2的时间复杂度？ 
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); 
} 

 Func2执⾏的基本操作次数：

F(N) = 2N + 10

根据推导规则第3条得出

Func2的时间复杂度为：O(N)。

案例二：

// 计算Func3的时间复杂度？ 
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); 
}

Func3执⾏的基本操作次数：

F (N) = M + N 

因此：Func3的时间复杂度为：O(M+N)

案例三：

// 计算Func4的时间复杂度？ 
void Func4(int N) 
{ 
 int count = 0; 
 for (int k = 0; k < 100; ++ k) 
 { 
 ++count; 
 } 
 printf("%d\n", count); 
}

Func4执⾏的基本操作次数：

F (N) = 100

根据推导规则第1条得出

Func4的时间复杂度为：O(1)

案例四：

// 计算strchr的时间复杂度？ 
const char * strchr ( const char 
* str, int character)
{
 const char* p_begin = s;
 while (*p_begin != character)
 {
 if (*p_begin == '\0')
 return NULL;
 p_begin++;
}
 return p_begin;
}

strchr执⾏的基本操作次数：

1）若要查找的字符在字符串第⼀个位置，则：F (N) = 1

2）若要查找的字符在字符串最后的⼀个位置， 则：F (N) = N 

3）若要查找的字符在字符串中间位置，则：F (N) = N/2 

因此：strchr的时间复杂度分为：

最好情况：O(1)

最坏情况：O(N)

平均情况：O(N)

小结：

通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况：任意输⼊规模的最⼤运⾏次数(上界)

平均情况：任意输⼊规模的期望运⾏次数

最好情况：任意输⼊规模的最⼩运⾏次数(下界)

⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

---

案例五：

// 计算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; 
 } 
}

BubbleSort执⾏的基本操作次数：

1）若数组有序，则：F (N) = N 

2）若数组有序且为降序，则：F (N) = （N∗(N + 1)）/2

3）若要查找的字符在字符串中间位置，则为2）中情况的1/2.

因此：BubbleSort的时间复杂度取最差情况为：O(N^2).

案例六：

void func5(int n)
{
 int cnt = 1;
 while (cnt < n)
 {
 cnt *= 2;
 }
}

当n=2时，执⾏次数为1

当n=4时，执⾏次数为2

当n=16时，执⾏次数为4

假设执⾏次数为x ，则2^x = n

因此执⾏次数：x = log n

因此：func5的时间复杂度取最差情况为： O(log2 n)

*特别的，当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表⽰为log n 。

案例七：

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

调⽤⼀次Fac函数的时间复杂度为O(1)

⽽在Fac函数中，存在n次递归调⽤Fac函数

因此：

阶乘递归的时间复杂度为：O(n)。

---

空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。

注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。

空间复杂度的计算示例

示例一：

// 计算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; 
 } 
}

函数栈帧在编译期间已经确定好了， 只需要关注函数在运⾏时额外申请的空间。

BubbleSort额外申请的空间有exchange等有限个局部变量，使⽤了常数个额外空间

因此空间复杂度为：O(1)

示例二：

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

Fac递归调⽤了N次，额外开辟了N个函数栈帧， 每个栈帧使⽤了常数个空间

因此空间复杂度为：O(N)

---

常见复杂度对比

小结

以上便是我对复杂度的分享，不是高手，但是有颗成为高手的心态，欢迎各位在评论区提出问题，纠正不足。感谢观看！