数据结构：时间复杂度与空间复杂度

🕗 发布于 2024-09-19 19:26 数据结构 算法 c语言

算法效率

算法在编写成可执行程序后，运⾏时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运行快慢，⽽空间复杂度主要衡量⼀个算法运行所需要的额外空间。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度，有时我们会用空间复杂度来分担时间复杂度。

时间复杂度

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

因为程序运行时间和编译环境和运行机器的配置都有关系，比如同⼀个算法程序，用⼀个老编译器进⾏编译和新编译器编译，在同样机器下运行时间不同。
同⼀个算法程序，用⼀个老的低配置机器和新的高配置机器，运行时间也不同。
并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执行次数。假设每个语句编译的时间都一样，那程序语句执行的次数就与时间成正比，用次数就可以间接反映算法的时间。
假设同一个问题，算法a程序T(N)=N,算法b程序T(N)=N^2，那算法a就优于算法b。
举个例子：

// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)//外循环n次
{
for (int j = 0; j < N ; ++ j)//内循环n次
{
++count;//一共循环n*n次
}
}
for (int k = 0; k < 2 * N ; ++ k)//循环2n次
{
++count;
}
int M = 10;
while (M--)//循环10次
{
++count;
}
}

每个循环的语句都标注在程序后面，得出T(N)如下：
有的会问那些int M等语句不算吗？但是那些算上的话一共就两次，与N^2和2N比太小了，这里就直接忽略了。
T(N)=N^2+2N+10;
实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别，上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

大O渐进表示法

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

时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。
用上面的列子来说：T(N)就可以写为N^2，后面的低阶项和常数就可以忽略了。
如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数对结果影响越来越小，当N无穷大时，就可以忽略不计了。
例如：2N^2 与 N^2是等价的，当N无穷大，系数2的影响可以忽略。
T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

时间复杂度计算案例

案例1：

void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)//循环n次
{
++count;
}
int M = 10;
while (M--)//循环10次
{
++count;
}
printf("%d\n", count);
}

T(N)=2N+10;
最高阶是2N，后面的低阶项和常数项忽略，最高阶的的系数也可以忽略；
所以这段程序的时间复杂度就是：O(N)。

案例2：

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

T(N)=M+N;
当M<<N时：复杂度为O(N);
当M>>N时：复杂度为O(M);
当M==N时：复杂度为O(M+N);
因为他有两个影响次数的参数，分别是M和N，复杂度算的是情况最坏的情况，也就是M和N都趋于无穷，那他们两个共同决定运行次数；
所以复杂度就是O(M+N);

案例3：

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

T(N)=100；
由大O渐进表示法第三条可得：
时间复杂度为O(1);

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

第一种情况：
要找的字符串在源字符串前面：Y(N)=常数；时间复杂度：O(I)；
第二种情况：
在中间位置：T(N)=N/2;时间复杂度：O(N)；
第三种情况：
在末尾：T(N)=N;时间复杂度：O(N)；
取最坏结果：时间复杂度为O(N)；

案例5：

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

递归就相当与循环调用一个函数N次；
通过判断可知这个递归函数一共调用N次；
所以它的时间复杂度：O(N)。

空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候申请的额外空间来确定。

空间复杂度案例

案例1：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n//1次; end > 0; --end)
{
int exchange = 0;//2次
for (size_t i = 1//3次; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

由分析可知在运行时创建的临时变量有三个，T(N)=3；
所以空间复杂度为O(1);

案例2：

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

在c语言学习中，函数的使用要创建栈帧空间，前面分析了这个递归要运行N次这个函数，运行一次就创建一个函数栈帧空间，所以T(N)=N；
它的空间复杂度：O(N)。

复杂度算法题

轮转N个数据：
数组元素： 0 1 2 3 4
轮转1次：4 0 1 2 3
轮转2次：3 4 0 1 2

void rotate(int* nums, int numsSize, int k) {
while(k--)
{
int end = nums[numsSize-1];
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i] = nums[i-1];
}
nums[0] = end;
}
}

外循环K次，内循环N次。
可知一共循环KN次。
最欢结果，让数据轮转N次，即T(N)=NN=N^2;
时间复杂度：O(N^2)。

现在出个问题，让它的时间复杂度降低。
思路1：刚开始提到可以用空间复杂度来分担时间复杂度。
代码实现：

void rotate(int* nums, int numsize, int k) {
int newnums[numsize];//创建大小为N的字符串
for(int i =0;i<numsize;i++)
{
newnums[i]=nums[(i+k)%numsize];
}
for(int i=0;i<numsize;i++)
{
nums[i]=newnums[i];
}

时间复杂度：T(N)=2N–> O(N);
空间复杂度：T(N)=N–>O(N)。

思路2：
在这里插入图片描述
如图数组里存放5个数，轮转2次。
先操作前半部分：交换第一个与第二个数据，如果前半部分数据较多（交换第二个跟倒数第二的数据，依次类推）
交换后数组变成：2 1 3 4 5；
然后相同的方法交换后半部分，
交换后数组：2 1 5 4 3；
然后交换整个数组，
交换后：3 4 5 1 2，
交换完成。
空间复杂度O(1),时间复杂度O(N)

void swap(int* nums,int left, int right)
{
while (left < right)
{
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;

left++;
right--;
}

}
void rotate(int* nums, int numsize, int k) {

k%= numsize;
swap(nums, 0,k-1);
swap(nums, k,numsize-1);
swap(nums, 0,numsize-1);
}

这个思路不难，就是不容易想出来。它既节省了空间复杂度，还优化了时间复杂度。
----------------------------------------------分隔符
时间复杂度与空间复杂度就介绍完了，希望对各位看官有所帮助。
有错请在评论区指正，谢谢。

原文地址：https://blog.csdn.net/qq_71391318/article/details/142301484

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：前端入门：HTML案例（表格、按钮、下拉款、文本域等）
下一篇：苍穹外卖Day01-2

vue3 + element-plus 的 upload + axios + django 文件上传并保存
之前在网上搜了好多教程，一直没有找到合适自己的，要么只有前端部分没有后端，要么就是写的不是很明白。所以还得靠自己摸索出来后，来此记录一下整个过程。环境安装什么的就不讲了，直接上代码好吧，这个是样式图。
阅读更多2024-11-06
Cuebric：用AI重新定义3D创作的未来
Cuebric 是一家成立于2022年夏天的好莱坞创新公司，致力于为电影、电视、游戏和时尚等行业提供先进的AI多模态SaaS平台。自2024年1月正式推出以来，Cuebric 已经在市场上获得了广泛的
阅读更多2024-11-06
easyui+vue 数据表更新问题的解决
数据的增删改查可以实时刷新出来,不建议在封装组件。nextTick 保证DOM 渲染完成。
阅读更多2024-11-06
软件测试基础：单元测试与集成测试
单元测试和集成测试是软件测试的基础，它们的重要性不言而喻。通过对软件的不同部分进行有序的测试，可以提高软件质量、减少后期维护成本，保证软件的可靠性和稳定性。软件开发者和测试人员应当重视并深入理解单元测
阅读更多2024-11-06
RxJS基本介绍以及与Promise的区别
Promise 适合处理单一的异步操作，具有更简单的 API，但缺乏灵活性和对多值的支持。RxJS (Observable) 适合处理复杂的异步流和多事件流，具有更多的操作符、错误处理机制和强大的组合
阅读更多2024-11-06
第三节 Vim编辑器与Shell命令脚本
这里的脚本主要使用 ping 命令来测试与对方主机的网络连通性，而 Linux 系统中的 ping 命令不像 Windows 一样尝试 4 次就结束，因此为了避免用户等待时间过长，需要通过-c 参数来
阅读更多2024-11-06
【JavaEE初阶 — 多线程】线程安全问题＆ synchronized
【JavaEE初阶 — 多线程】线程安全问题＆ Synchronized观察线程安全问题，分析了造成线程安全问题造成的三个原因：线程的随机调度，多个线程修改共享数据（修改同一个变量），以及原子性问题
阅读更多2024-11-06
十月末补充（？
【代码】十月末补充（？
阅读更多2024-11-06
13-鸿蒙开发中的综合实战：华为登录界面
通过本文，你已经学会了如何在鸿蒙开发中实现一个简单的登录界面，涵盖了输入框组件、按钮组件、文本组件和布局容器的使用。这个实战项目不仅帮助你巩固了基础知识，还提供了一个实际的应用场景。希望这篇文章对你有
阅读更多2024-11-06
python全栈开发《59.集合的增删改》
目录1.集合的add函数2.集合的update函数3.集合的remove函数4.集合的clear函数5.用del删除集合6.重要说明7.代码1.集合的add函数1.1add的功能用于集合中添加一个元素
阅读更多2024-11-06