【数据结构与算法】时间复杂度与空间复杂度(上)

简介: 【数据结构与算法】时间复杂度与空间复杂度

一.前言

从这篇文章开始,C语言的学习就结束了,接下来将会开启数据结构与算法的学习。

早期,计算机刚被发明出来,内存空间并不是很大,所以不仅追求程序运行时的时间效率,还追求空间效率,但发展到今天,已经不太追求空间效率了,时间效率的追求是不变的。

下面就让我们一起学习时间复杂度和空间复杂度是什么吧~

二.时间复杂度

1.概念

1.时间复杂度是一个函数(注意这不是编程语言里的函数,而是数学意义上的函数)

2.这个函数指的是算法跑的次数的函数,并不是算法运行的时间,因为同一个算法在不同的机器上运行的时间可能是不同的,用算法的运行时间表示时间复杂度是欠妥的;

3.一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

二.大O的渐进表示法

概念:

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数

2、在修改后的运行次数函数中,只保留最高阶项

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

需要注意的是算法运行时可能会存在最好情况,最坏情况,平均情况,这个时候我们取最坏情况时的大O;

最坏情况:任意输入规模的最大运行次数(上界)

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数(下界)

总结:

1.大O里的数就是函数表达式中对结果影响最大的项,或是最大的量级所在的项

2.如果这个项的系数不是1,那么将它变成1,简单来说,这个项前面的系数得是1

3.如果函数表达式是个常数,不管这个常数多大,都写成O( 1 )

光说不练假把式,让我们通过例题来更好的理解上述所说吧~


三.常见时间复杂度计算举例

例1

1. // 请计算一下Func1中++count语句总共执行了多少次?
2. void Func1(int N)
3. {
4. int count = 0;
5. for (int i = 0; i < N ; ++ i)
6.     {
7. for (int j = 0; j < N ; ++ j)
8.         {
9.             ++count;
10.         }
11.     }
12. for (int k = 0; k < 2 * N ; ++ k)
13.     {
14.         ++count;
15.     }
16. int M = 10;
17. while (M--)
18.     {
19.         ++count;
20.     }
21. printf("%d\n", count);
22. }

不难看出:

Func1 执行的基本操作次数 :

            F(N)=N^2+2^N+10

 N = 10        F(N) = 130

 N = 100      F(N) = 10210

 N = 1000    F(N) = 1002010

显然最大的量级是 N^2

所以时间复杂度为O(N^2)


例2

1. // 计算Func2的时间复杂度?
2. void Func2(int N)
3. {
4. int count = 0;
5. for (int k = 0; k < 2 * N ; ++ k)
6.     {
7.         ++count;
8.     }
9. int M = 10;
10. while (M--)
11.     {
12.         ++count;
13.     }
14. printf("%d\n", count);
15. }

F(N)=2*N+10

影响最大的项为2*N,因为它的系数不是1,所以要变成1,即

时间复杂度:O(N)


例3

1. // 计算Func3的时间复杂度?
2. void Func3(int N, int M)
3. {
4. int count = 0;
5. for (int k = 0; k < M; ++ k)
6.     {
7.         ++count;
8.     }
9. for (int k = 0; k < N ; ++ k)
10.     {
11.         ++count;
12.     }
13. printf("%d\n", count);
14. }

F(N)=M+N

由于并未明确告知M和N的关系,所以时间复杂度:O(M+N)

若M远大于N,则为O(M);

若N远大于M,则为O(N);

若亮着差不多大,则为O(N)或O(M);


例4

1. // 计算Func4的时间复杂度?
2. void Func4(int)
3. {
4. int count = 0;
5. for (int k = 0; k < 100; ++ k)
6.     {
7.         ++count;
8.     }
9. printf("%d\n", count);
10. }

F(N)=100

这是一个常数,所以时间复杂度:O(1)


例5.计算冒泡排序的时间复杂度

不了解冒泡算法请戳我

1. // 计算BubbleSort的时间复杂度?
2. void BubbleSort(int* a, int n)
3. {
4. assert(a);
5. for (size_t end = n; end > 0; --end)
6.     {
7. int exchange = 0;
8. for (size_t i = 1; i < end; ++i)
9.         {
10. if (a[i-1] > a[i])
11.             {
12. Swap(&a[i-1], &a[i]);
13.                 exchange = 1;
14.             }
15.         }
16. if (exchange == 0)
17. break;
18.     }
19. }

最好情况:

原本已排好序,所以进入第二个for循环时不进入if语句,所以exchange==0,直接跳出循环,所以时间复杂度:O(N)

最坏情况:

执行完了所有的循环,所以时间复杂度:O(N^2)

取最坏情况,所以最终的时间复杂度为:O(N^2)

如果没有exchange相关语句,那么最好情况和最坏情况都是O(N^2)


目录
相关文章
|
9月前
|
机器学习/深度学习 缓存 算法
Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【10月更文挑战第4天】在Python编程中,算法的设计与优化至关重要,尤其在数据处理、科学计算及机器学习领域。本文探讨了评估算法性能的核心指标——时间复杂度和空间复杂度。通过详细解释两者的概念,并提供快速排序和字符串反转的示例代码,帮助读者深入理解这些概念。同时,文章还讨论了如何在实际应用中平衡时间和空间复杂度,以实现最优性能。
167 6
|
9月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
9月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
285 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
9月前
|
机器学习/深度学习 存储 算法
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
105 1
|
9月前
|
存储 算法
算法的时间复杂度和空间复杂度
本文详细讨论了算法的时间复杂度和空间复杂度,包括它们的概念、计算方法和常见复杂度的对比,并通过多个实例解释了如何计算算法的时间和空间复杂度。
618 0
算法的时间复杂度和空间复杂度
|
9月前
|
算法
[数据结构] -- 时间复杂度和空间复杂度
[数据结构] -- 时间复杂度和空间复杂度
83 0
|
9月前
|
算法 C语言
深入理解算法效率:时间复杂度与空间复杂度
深入理解算法效率:时间复杂度与空间复杂度
|
1月前
|
机器学习/深度学习 算法 数据挖掘
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
|
23天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
|
28天前
|
算法 JavaScript 数据安全/隐私保护
基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容展示了基于GA(遗传算法)优化的256QAM概率星座整形(PCS)技术的研究与实现。通过Matlab仿真,分析了优化前后星座图和误码率(BER)的变化。256QAM采用非均匀概率分布(Maxwell-Boltzman分布)降低外圈星座点出现频率,减小平均功率并增加最小欧氏距离,从而提升传输性能。GA算法以BER为适应度函数,搜索最优整形参数v,显著降低误码率。核心程序实现了GA优化过程,包括种群初始化、选择、交叉、变异等步骤,并绘制了优化曲线。此研究有助于提高频谱效率和传输灵活性,适用于不同信道环境。
48 10
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问