[数据结构与算法] 算法与算法分析 - IV.算法效率指标
4.1算法时间
算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量,算法时间的度量有事后统计和事前统计两种方法,事后度量先实现算法再测试时间,要花费较多的时间和精力,所以优先选择事前分析法。
事前分析法
- 对算法所消耗资源的一种估算方法。
- 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作(如赋值,比较,移动等)所需的时间与算法中进行简单操作次数乘积。
算法运行时间=一个简单操作所需时间×简单操作次数
- 也即算法中每条语句的执行时间之和
算法运行时间=∑语句频度(每条语句的执行次数)×该语句执行一次所需时间
- 每条语句执行一次所需的时间,一般是随机器而异的。取决于机器的指令性能,速度以及编译的代码质量。是由机器本身软硬件环境决定的,它与算法无关。既然在一个机器中所有算法执行一条语句的单位时间都是一样的,所以我们可以假设执行每条语句所需时间均为单位时间。此时对算法的运行时间的讨论就可以转化为讨论该算法中所有语句的执行次数,即上述式子就可以约去“该语句执行一次所需时间”,直接比较语句频度之和了。
- 这就可以独立于不同机器的软硬件环境来分析算法的时间性能了。
实例:用循环变量控制执行次数
//两个n×n矩阵相乘的算法可以描述为:
for(i=1;i<=n;i++) //执行n+1次(条件不执行,跳出循环)
for(j=1;j<=n;j++){ //作为最外层for的循环体执行n次,同时这个for循环体本身执行n+1次,共执行n(n+1)次
c[i][j]=0; //第二层for循环的循环体,执行n×n次
for(k=0;k<n;k++) //第三层for循环同理,执行n*n*(n+1)次
c[i][j]=c[i][j]+a[i][k]*b[i][j];//n*n*n次
}
最后对每条语句的执行次数进行求和运算,即求出该算法中每条语句的频度之和,则上述算法的时间消耗
T(n)=2n3+3n2+2n+1(这是一个关于n的函数)
那么,对于所有程序都要这样一步步算岂不是很麻烦吗?
算法时间复杂度的渐进表示法
- 为了便于比较不同算法的时间效率,我们仅比较他们的数量级(找到对时间贡献最大的语句,在计算数量级时忽略所有的低次幂项和最高次幂系数,只计算最高次项的数量级)
- 若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同量级函数。记作
T(n)=O(f(n))
,称O(f(n))为算法的渐进时间复杂度(O是数量级的符号),简称时间复杂度。它表示随着n的增大,算法执行的时间的增长率和f(n)的增长率相同,称渐进时间复杂度。
例如,对于求解矩阵相乘问题,算法耗费时间:T(n)=2n3+3n2+2n+1
n→∞
时,T(n)/n3->2,这表示n充分大时,T(n)与n3是同阶或数量级,引入大“O”记号,则T(n)可以记作:T(n)=O(n^3)
,意思是说这里所求的渐进时间复杂度和n^3同阶,这就是求解矩阵相乘问题的渐进时间复杂度。
一般情况下,不必计算所有操作的执行次数,而只考虑算法中基本操作执行的次数,它是问题规模n的某个函数,用T(n)表示。定义:算法中基本语句重复执行的次数是问题规模n的某个函数f(n)
-
基本语句是指:算法中,重复执行次数和算法的执行时间成正比的语句,对算法运行时间的贡献最大的语句,执行次数最多的语句,由此可见,时间复杂度是由嵌套最深层语句的频度决定的。
-
语句频度:一个算法中基本语句的执行次数称为语句频度或时间频度,记为
T(n)
。 -
问题规模n:是描述数据量的一个变量,n越大,算法的执行时间越长
f(n) n越大算法的执行时间越长
- 排序:n为记录数
- 矩阵:n为矩阵的阶数
- 多项式:n为多项式的项数
- 集合:n为元素个数
- 树:n为树的结点个数
- 图:n为图的顶点数或边数
-
常见的时间复杂度量级
- 常数阶:O(1)
- 对数阶:O(logN)
- 线性阶:O(n)
- 线性对数阶:O(nlogN)
- 平方阶:O()
- 立方阶:O()
- k次方阶:O()
- 指数阶:O()
从上至下依次的时间复杂度越来越大,执行的效率越来越低
-
其他:
- 多项式复杂度:O()
- 阶乘复杂度:O(n!) O()<O(n!)<O()
- 在无序数列中查找某个数(顺序查找):O(n)
- 平面上有n个点,求出任意两点间的距离:O()
- 插入排序、选择排序、冒泡排序:O()
- 快速排序:O(n*log(n))
- 二分查找:O(log(n))
分析算法时间复杂度的基本方法
1.找出语句频度最大的那条语句作为基本语句
2.计算基本语句的频度得到问题规模n的某个函数f(n)
3.取其数量级用符号“O"表示
4.2算法空间
一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模n的函数。用S(n)来定义。计算公式S(n)=O(f(n))
.其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。
- 算法要占据的空间
- 算法本身要占据的空间,输入/输出,指令,常数,变量等。
- 算法要使用的辅助空间
上一篇: 记录 gRpc 流操作
推荐阅读
-
[数据结构与算法] 算法与算法分析 - IV.算法效率指标
-
大顶堆与小顶堆:数据结构与算法中的重要概念
-
数据结构与算法--排序算法:堆排序 最大堆(大顶堆)和 最小堆(小顶堆)详解
-
探索二叉树、红黑树、递归树、堆和堆排序的数据结构与算法(第四部分),以及堆的实际应用
-
数据结构与算法笔试题彻底整理
-
玩转数据结构与算法:探索种花难题
-
玩转24点:算法设计与分析技巧探讨(第5-23讲)
-
【摩尔线程+Colossal-AI强强联手】MusaBert登上CLUE榜单TOP10:技术细节揭秘 - 技术实力:摩尔线程凭借"软硬兼备"的技术底蕴,让MusaBert得以从底层优化到顶层。其内置多功能GPU配备AI加速和并行计算模块,提供了全面的AI与科学计算支持,为AI推理和低资源条件下的大模型训练等场景带来了高效、经济且环保的算力。 - 算法层面亮点:依托Colossal-AI AI大模型开发系统,MusaBert在训练过程中展现出了卓越的并行性能与易用性,特别在预处理阶段对DataLoader进行了优化,适应低资源环境高效处理海量数据。同时,通过精细的建模优化、领域内数据增强以及Adan优化器等手段,挖掘和展示了预训练语言模型出色的语义理解潜力。基于MusaBert,摩尔线程自主研发的MusaSim通过对比学习方法微调,结合百万对标注数据,MusaSim在多个任务如语义相似度、意图识别和情绪分析中均表现出色。 - 数据资源丰富:MusaBert除了自家高质量语义相似数据外,还融合了悟道开源200GB数据、CLUE社区80GB数据,以及浪潮公司提供的1TB高质量数据,保证模型即便在较小规模下仍具备良好性能。 当前,MusaBert已成功应用于摩尔线程的智能客服与数字人项目,并广泛服务于语义相似度、情绪识别、阅读理解与声韵识别等领域。为了降低大模型开发和应用难度,MusaBert及其相关高质量模型代码已在Colossal-AI仓库开源,可快速训练优质中文BERT模型。同时,通过摩尔线程与潞晨科技的深度合作,仅需一张多功能GPU单卡便能高效训练MusaBert或更大规模的GPT2模型,显著降低预训练成本,进一步推动双方在低资源大模型训练领域的共享目标。 MusaBert荣登CLUE榜单TOP10,象征着摩尔线程与潞晨科技联合研发团队在中文预训练研究领域的领先地位。展望未来,双方将携手探索更大规模的自然语言模型研究,充分运用上游数据资源,产出更为强大的模型并开源。持续强化在摩尔线程多功能GPU上的大模型训练能力,特别是在消费级显卡等低资源环境下,致力于降低使用大模型训练的门槛与成本,推动人工智能更加普惠。而潞晨科技作为重要合作伙伴,将继续发挥关键作用。
-
用R语言探究交通网络流量拥挤:通过最大流最小割理论与最短路径算法分析——来自拓端数据部落的深入解读
-
李春葆编写的《算法设计与分析》第二章详细解答与解析