【神秘海域】[动图] 数据结构与算法初探：复杂度详解分析「附代码」

复杂度引言

本篇文章是数据结构与算法正式内容的第一篇文章。
要介绍的也是数据结构与算法中最重要的概念之一：**

复杂度

复杂度，是贯穿整个数据结构与算法学习的一个重要概念。

它是衡量一个算法好坏的重要指标，它包括两个维度：**

时间

、

空间

**，被称为 **

时间复杂度

、

空间复杂度

**。
**

时间复杂度

** 主要衡量一个算法的运行快慢
**

空间复杂度

** 主要衡量一个算法运行所需要的额外空间

算法的复杂度，一般与需要处理的数据量挂钩，如果数据量为

，那复杂度就有可能是：

、

logN

、

N*logN

、

N^2

等等。

究竟什么是复杂度？

时间复杂度

上面提到：**

时间复杂度

** 主要衡量一个算法的运行快慢。
但是，这里的快慢并不是指算法运行所需要执行的具体的时间。而是指：

算法中的基本操作的执行次数

。并且，算法的时间复杂度用一个函数表示.

举个简单的例子：

// 一个简单的循环voidFun1(int n){for(int i =0; i < n; i++){printf("%d ", i);}}

这段代码，

for

循环执行的次数，是根据传入的参数来具体决定的，即循环

次。就可以说，这个函数的时间复杂度是

O(N)

。

看起来非常简单？

那么再看一个例子：

voidFun2(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;}}

函数

Fun2

中存在三个循环体，其中一个是嵌套的双重循环
那么，这个函数的时间复杂度是多少呢？该怎么计算？

逐个分析：

int count =0;for(int i =0; i < N ;++ i){for(int j =0; j < N ;++ j){++count;}}
这个循环是一个循环的嵌套，执行次数是
N*N

for(int k =0; k <2* N ;++ k){++count;}
这个循环就是一个普通的循环，执行次数是
2*N

int M =10;while(M--){++count;}
这个循环是可以确定次数的循环，每次函数调用执行的次数是一定的，执行次数是
10
次

结合起来，这个函数的时间复杂度就是

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

但是，事实并不是这样的。
这个函数的时间复杂度其实是

O(N^2)

为什么？

来进行一个计算：

N = 10，执行次数：10*10 + 2*10 + 10 = 130
N = 100，执行次数：100*100 + 2*100 + 10 = 10210
N = 1000，执行次数：1000*1000 + 2*1000 + 10 = 1002010
N = 10000，执行次数：10000*10000 + 2*10000 + 10 = 100020010

有没有发现什么规律？
随着

的增大，

2*N + 10

在最终执行次数中的

占比越来越小

了，也代表着其对最终执行次数的

影响越来越小

了

2*N + 10

在结果中的占比：

23%

2%

0.2%

0.02%

当

足够大的时候，就已经可以忽略

2*N + 10

的影响了，所以只需要计算

N^2

就能够代表函数的执行次数，所以函数

Fun2

的时间复杂度其实是

O(N^2)

。

这时候计算时间复杂度，就只是计算了大概了执行次数，使用的是

大 0 的渐进表示法

大 O 的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进 行为 的数学符号

用

大O表示法

计算复杂度的方法一般有：

基本操作的执行次数中，相加的常数一般用 1 取代即：N^2 + 2*N + 10 —> N^2 + 2*N + 1 或： O(100) —> O(1)，即常数的时间复杂度，均计算为 O(1)
在常数转后之后的执行次数函数中，取最高次幂项作为时间复杂度，即： O(N^2 + 2*N + 1) —> O(N^2)
如果转换后的执行次数函数中，存在 最高次幂项且此项不为1，则只保留单个此项作为时间复杂度(即放弃与其相乘的常数) 即：O(4 * N^2) —> O(N^2)

即，大O的渐进表示法

去掉了那些对结果影响不大的项

，简洁明了的表示出了时间复杂度。
所以函数

Fun2

的时间复杂度为：

O(N^2)

忽略了

2*N + 10

时间复杂度的最好、最坏、平均情况

虽然知道了大O渐进表示法的计算方法，但是总有一些算法代码是拥有多种情况的。
比如：

//查找整型数组中第一个 10 的位置intFind_10(int*arr,int arrSize){int i =0;while(arrSize--){if(*arr ==10){return i;}
        arr++;
        i++;}return-1;}

这个函数目的是寻找数组中第一个

的位置，但是第一个

有可能出现在一个数组中的任何位置，甚至不出现在数组中。

可能是在

arr[0]

arr[n - 1]

arr[n / 2]

，被查找的数的位置是不定的，所以这个函数中

基本操作的执行次数也是不定的

。

那么这个时候，

一个算法的时间复杂度，就用最坏情况下的复杂度来表示

Find_10

这个函数的时间复杂度，实际就是

O(N)

。

「PS:计算基本操作的执行次数，结果中的未知数用 N 或 M 代表(只有一个未知数 用 N,两个未知数 用 N 和 M, 多个可以用其他)」

时间复杂度计算举例

// 计算Func1的时间复杂度？  voidFunc1(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
次
按照大O 渐进表示法，时间复杂度为
O(N)

// 计算Func2的时间复杂度？  voidFunc2(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
次
按照大O 渐进表示法，时间复杂度为
O(M + N)

// 计算Func3的时间复杂度？  voidFunc3(int N){int count =0;for(int k =0; k <100;++k){++count;}printf("%d\n", count);}
此函数，通过分析
有一个循环体，但是循环体循环次数与传入参数无关，固定循环
100
次
按照大O 渐进表示法，时间复杂度为
O(1)

// 计算BubbleSort的时间复杂度？  voidBubbleSort(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
次，即
将第一位数据冒泡至最后一位
最坏的情况是：数据按照降序排列，则每一个数据都要进行排序，计算执行次数的结果为：
(N*(N+1)/2
次
按照大O 渐进表示法，取最坏的情况时间复杂度为
O(N^2)

// 计算BinarySearch的时间复杂度？  intBinarySearch(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;elseif(a[mid]> x)  
            end = mid;elsereturn mid;}return-1;}
此函数为
二分查找
，
(被查找的数据必须是有序的)
同样需要分情况分析：
最好的情况：
指定数据在数组中间位置，只需要执行一次
，即第一次查找就查找到指定数据
最坏的情况：
二分查找的原理：
因为使用二分查找的数据必须是有序的，所以可以通过缩小查找范围来进行查找
二分查找每次查找一次，
下一次查找的范围会缩小为当前范围的一半
只需要一张动图就可解释：

可以看出，每次查找之后，下一次需要查找的元素只剩下一半，所以最坏的情况其实是需要查找：
log N
次
复杂度中，log N即为 以2为底N的对数
所以按照大O 渐进表示法，取最坏的情况时间复杂度为
O(log N)

// 计算阶乘递归Fac的时间复杂度？  longlongFac(size_t N){if(0== N)return1;returnFac(N-1)*N;}
此函数为
递归求阶乘
递归求阶乘，通过计算可以算出，求
N的阶乘
则函数调用了
N
次
所以按照大O 渐进表示法，时间复杂度为
O(N)

// 计算斐波那契递归Fib的时间复杂度longlongFib(size_t N){if(N <3)return1;returnFib(N-1)+Fib(N-2);}
此函数为
递归求斐波那契数列
递归求斐波那契数列，一个简单的递归分析图：

发现正常调用函数，会再发生两次递归，所以应该是
2^N
但是因为当
N < 3
会返回
1
，不再递归，所以应该是
2^N - x
(不容易计算所以用 x 表示)
，但是无论怎样，相减的常数因该是对
2^N
造不成多大影响的
所以按照大O 渐进表示法，时间复杂度为
O(2^N)

练习结束，感觉如何？？

空间复杂度

空间复杂度

** 主要衡量一个算法运行所需要的额外空间
这里提到一个词：**

额外空间

为什么是

额外空间

？
因为，

函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，在函数运行前就已经确定了一部分空间，这些空间的占用不能由算法本身决定

所以，空间复杂度主要通过

函数在运行时候申请的额外空间

来确定。

这里推荐一篇详细又简单的函数栈帧的好文章：
【程序员的自我修养】[动态图文] 超详解函数栈帧

在函数内使用动态开辟内存的函数，以及创建柔性数组等操作，就会增加函数的额外空间哦

空间复杂度

和

时间复杂度

的表示方法一样，都用大O渐进表示法。

空间复杂度的计算举例

依然举几个例子：

// 计算BubbleSort的空间复杂度？  voidBubbleSort(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
发生关联。使用了常量个额外空间
所以按照大O 渐进表示法，空间复杂度为
O(1)

// 计算Fibonacci的空间复杂度？  // 返回斐波那契数列的前n项  longlong*Fibonacci(size_t n){if(n==0)returnNULL;longlong* fibArray =(longlong*)malloc((n+1)*sizeof(longlong));  
    fibArray[0]=0;  
    fibArray[1]=1;for(int i =2; i <= n ;++i){  
        fibArray[i]= fibArray[i -1]+ fibArray [i -2];}return fibArray;}
这是使用
数组实现的计算斐波那契数列的 前N 项
分析代码可以看出，这段代码使用
malloc
函数开辟了
n+1
个
long long
类型的空间，即额外使用的空间与
N
1:1相关
所以按照大O 渐进表示法，空间复杂度为
O(N)

// 计算阶乘递归Fac的空间复杂度？  longlongFac(size_t N){if(N ==0)return1;returnFac(N-1)*N;}
递归求N的阶乘
分析代码可以看出，代码执行需要递归
N
次，且每次递归都需要开辟函数栈帧，
每次函数栈帧开辟都会消耗常量个空间
，所以是
常量 * N
按照大O 渐进表示法，空间复杂度为
O(N)

以上内容就是关于 **

时间复杂度

** 和 **

空间复杂度

** 的介绍。
复杂度需要进行学习的已经介绍的差不多了。
但是，需要注意的是

其实大部分的代码，时间、空间复杂度是不容易直接看出来的，一定要执行分析。对存在循环体的代码，也不要直接简单粗暴的去数循环体执行的次数，因为循环并不一定是都需要执行的。一定要分析。

复杂度对比

常见的复杂度都有什么呢？

结束语

数据结构与算法关于复杂度的部分到这里就介绍完了。
本篇文章是对

数据结构与算法

这片

神秘海域

的初探索。
同样也是

向更深海域探索的重要基石

感谢阅读！

求三连！求三连！

标签： c语言算法数据结构

本文转载自: https://blog.csdn.net/dxyt2002/article/details/124157851
版权归原作者 七月July. 所有，如有侵权，请联系我们删除。