当前位置：首页 > news >正文

算法复杂度

news 文章来源：https://blog.csdn.net/wdnmdfky/article/details/142503109 2025/5/10 15:21:11

1. 数据结构前⾔

1.1数据结构

数据结构是计算机存储数据，组织数据的方式，指相互之间存在⼀种或多种特定关系的数
据元素的集合。常见的数据结构有线性表，树，图，哈希等。

1.2 算法

算法是一种计算过程，输入一些数据，通过一系列的计算，输出数据。

1.3 数据结构和算法的重要性

在一些工作岗位中，数据结构和算法是必需的。

很多大厂的笔试题都对数据结构和算法有严格的需求，因此我们要认真着手数据结构和算法。

那如何学好数据结构呢，

就是要多写代码，多思考，只能考一点一点的积累。

2. 算法效率

如何评判一个算法的好坏呢，从空间和时间两个方面去判断，即时间复杂度和空间复杂度。

时间复杂度评判根据一个算法的快慢，空间复杂度则根据一个算法所需开辟的空间大小。

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

2.2 复杂度的重要性

在企业的校招中，很多面试笔试都或多或少的设计到了复杂度。

3. 时间复杂度

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

在不同的编译环境下，在不同的运行环境下，相同的程序会有不同的运行时间，换句话说，有的机器比较好时间就会段，而有的机器比较慢，这样相同的程序就产生了不同的运行时间，因此研究运行时间的意义并不大。

那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执⾏次数。通
过c语⾔编译链接章节学习，我们知道算法程序被编译后⽣成⼆进制指令，程序运⾏，就是cpu执⾏这
些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每
句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执⾏次数和运⾏时间就是等⽐正相关，
这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的

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

计算一下count++这条语句执行了多少次，

第一个循环嵌套执行N^2，第二个循环执行2N次，第三个循环执行10次，所以一共执行N^2+2N+10次。

Func1 执⾏的基本操作次数：
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010
通过对N取值分析，对结果影响最⼤
的⼀项是 N^2

在计算时间复杂度时，计算的也不是语句的执行次数，因为一条语句可能不止一条二进制语句，所以只通过计算执行次数是计算不出来的，因此，大O的渐进表示法就出现了。

3.1 ⼤O的渐进表⽰法

规则如下

推导⼤O阶规则
1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，
低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数
对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数

通过大O表示法，就可以得到上述代码的时间复杂度是O(N^2)，因为2N和10对结果影响较小，所以就忽略不计了。

3.2 时间复杂度计算⽰例

3.2.1 ⽰例1

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

简单分析下，时间复杂度为2N,10忽略不计，但是时间复杂度并不是2N，而是N，2对计算机影响并不大，参考第三条法则，所以最后时间复杂度就是O(N)；

3.2.2 ⽰例2

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

T(N)=M+N,在这里不确定m和n的关系，无法忽略，

m>>n,T(N)=M

m<<n,t(n)=N

m==n,t(N)=N

O(N)=m+n

3.2.3 ⽰例3

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

Func4循环只执行了100次，复杂度应该为100，根据第三条法则，只要是常数项通为O(1)

3.2.4 ⽰例4

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

很明显这是一个求字符串长度的函数，我们并不确定字符串的长度，可能为1，也可能为n，最坏的打算就是n，平均情况是n/2，也就是平均时间复杂度O(N)。

小总结

通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
平均情况：任意输⼊规模的期望运⾏次数
最好情况：任意输⼊规模的最⼩运⾏次数(下界)
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

3.2.5 ⽰例5

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

这是一段冒泡排序的函数，冒泡排序是将各个数据一次放到最后面，像冒泡一样，当n个数据时，第1个数据，要经历n次冒泡，第二个数据要经历n-1次，一直到第n个数据经历0次冒泡才停止，其中exchange是判断是不是有序的，如果有序直接退出冒泡排序，最坏的打算就是要经历最多次冒泡，就是0+1+2·····+n-1,根据等差数列求和，最后经历n*(n+1)/2,最后时间复杂度是O(N^2).

3.2.6 ⽰例6

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

那这个函数呢，cnt每次*2，当cnt>n时就退出循环，

当n=2时，执⾏次数为1
当n=4时，执⾏次数为2
当n=16时，执⾏次数为4
假设执⾏次数为 x ，则 2
x = n
因此执⾏次数： x = log n

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

注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰
当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不
写，即可以表⽰为 log n
不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n

3.2.7 示例7

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

递归经历1,次时间复杂度是O(1)，递归n次时间复杂度就是o(N)

4. 空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。

空间复杂度也用大O渐进表示法。

4.1 空间复杂度计算⽰例

4.1.1 例1

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

一共开辟了三个空间，end,i,exchange，用大O表示法就是O（1）

4.1.2 例2

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

首先N先进入递归，然后再进入N-1的递归，当N进入N-1的递归，此时N的函数栈帧并没有销毁，并且同时又创建了一个函数栈帧，以此类推，一共创建了N个函数栈帧。空间复杂度就是O(N)

5. 常⻅复杂度对⽐

6. 复杂度算法题

. - 力扣（LeetCode）

这种每次将最后一个元素存储，然后将前面一个元素向后面移动一个，很容易想到，通过运行两个案例也是通过了，接着，我们提交一下试试，

提交却是错的，看下，我们有38个案例，通过了37个，其中有一个没有通过案例，是因为超出时间限制了，显而易见，是我们的时间超过了最大限度。

说明这个时间复杂度较大，此时我们要通过新的算法来解决这道题了，要对算法进行一下优化。

先将数组元素存储在一个新的元素，然后再将新元素赋值给旧的数组返回即可。