O()表示法是处理近似计算的一种数学途径,当我们写下某个特定的排序算法对n个记录进行排序所需时间是O(n2)时,我们的意思是,最坏情况下,所需时间随着n的平方变化。O()表示法对我们在度量时间,内存等的值设置了上限。
有时我们会遇到复杂的O()函数,随着n的增大, 最高阶的项会主宰函数的值,习惯做法是去掉所有低阶项,对任何常数项不予考虑。如O(n2+3n)和O(n2)一样等价,这实际上是O()表示法的弱点。某个O(n2)算法可能比O(n2)算法快1000倍,但是从表示法中看不出来。
下面是一些常见的各种算法运行时间
附表一:
O(1) |
常量访问(访问数组元素,简单语句) |
O(lg(n)) |
对数型(二分查找)lg(n)是
log2n缩写
|
O(n) |
线性型(顺序查找) |
O(nlg(n)) |
比线性差,但不会差很多(快排,堆排序平均运行时间) |
O(n2)
|
平方律型(冒泡,选择,插入排序) |
O(n3)
|
立方型(2n
× n矩阵相乘) |
O(Cn)
|
指数型(旅行家问题,集合划分) |
附表二:
排序法
|
最差时间分析 |
平均时间复杂度 |
稳定度 |
空间复杂度 |
冒泡排序 |
O(n2) |
O(n2) |
稳定 |
O(1) |
快速排序 |
O(n2) |
O(n*log2n) |
不稳定 |
O(log2n)~O(n) |
选择排序 |
O(n2) |
O(n2) |
稳定 |
O(1) |
二叉树排序 |
O(n2) |
O(n*log2n) |
不一顶 |
O(n) |
插入排序
|
O(n2) |
O(n2) |
稳定 |
O(1) |
堆排序 |
O(n*log2n) |
O(n*log2n) |
不稳定 |
O(1) |
希尔排序 |
O |
O |
不稳定 |
O(1) |
分享到:
相关推荐
数据结构与算法是计算机科学的基础,它涉及到如何高效地存储和处理数据,以及设计和分析用于解决问题的步骤——算法。算法分析基础课程是专业必修课,对于开发系统软件和大型应用软件至关重要。课程目标是培养学生的...
《数据结构与算法分析——C++语言描述》是Mark Allen Weiss的经典著作,这本书深入浅出地介绍了数据结构和算法分析的基础知识,对于学习计算机科学的学生和专业人士来说是必不可少的参考书。第四版在前几版的基础上...
本案例"基于Kohonen网络的聚类算法——网络入侵聚类"探讨的就是如何利用Kohonen自组织映射网络(Self-Organizing Map, SOM)来识别和分类网络入侵行为。 Kohonen网络,也称为自组织映射或竞争学习网络,是由芬兰...
这些习题涵盖了算法设计的各种主题,如排序算法、数据结构、图算法等,旨在帮助读者加深对算法原理的理解,并提高解决实际问题的能力。 ### 章节概览 #### 第2章:开始 - **主要内容**:介绍算法的基础知识,包括...
【哈工程——算法实验代码&报告(最新版)】是一个针对哈尔滨工程大学(简称哈工程)学生算法实验的资源集合,包含代码实现和相应的实验报告。这个压缩包旨在帮助学生理解和掌握各种算法的设计、实现与分析,提升...
在计算机科学领域中,数据结构与算法是两个核心概念,它们对于解决复杂问题至关重要。本章节旨在介绍数据结构的基础知识及其在Python中的应用,帮助读者理解为什么学习这些内容对于编程至关重要。 ##### 1.1 目标 ...
总结来说,Atheros网卡驱动的速率调整算法是通过深入分析网络环境并利用struct ieee80211_tx_info这样的数据结构来实现的。这些算法不仅影响着无线网络的性能,还直接影响到用户体验,因此它们的优化和改进是无线...
5. 减小硬盘读写速率会降低Apriori算法的效率,因为算法需要频繁地读取和写入数据。 6. Apriori算法使用格结构和哈希树来组织和查找频繁项集。 7. 非频繁模式是指其支持度低于阈值的模式。 8. 频繁闭项集可以无损...
种新的集群优化方法——粒子群优化算法 粒子群优化算法(Particle Swarm Optimization,PSO)是一种基于群体智能的全局优化算法,由Eberhart和Kennedy于1995年提出。该算法受到自然界中鸟群或鱼群群体行为的启发,...
加速比是衡量并行计算相对于串行计算速度提升的一个指标,它受到机器规模、时钟速率、工作负载等因素的影响。可扩展性则关注随着硬件资源增加,系统性能的提升程度。 在并行计算的实现中,有三种主要的操作类型:...
在当今数据驱动的科技浪潮中,将智能算法应用于解决实际问题已成为科研与工业界的重要课题。在众多优化算法中,蚁群算法因其独特的仿生学原理和出色的全局搜索能力而受到广泛关注。本文将深入探讨一种基于Java实现的...
它描述了算法在执行过程中额外需要的内存空间,包括临时变量、数据结构等。空间复杂度同样使用O记号表示,比如S(n) = O(f(n))。与时间复杂度相似,我们希望找到空间效率高的算法,以减少内存消耗,特别是在资源有限...
#### 三、具体算法与数据结构 ##### 3.1 算法分析方法 - **级数和**:通过数学级数求和来分析算法的复杂度。 - **循环与级数和**:分析循环结构的复杂度,并将其转化为级数求和的形式。 - **数组求和**:介绍迭代和...
论文标签中的“数据结构”可能指的是在建立地下水模型时需要处理的数据组织方式,如网格数据结构或时间序列数据,这些数据用于描述地下水位、流速、流向等参数。而“参考文献”表明该研究基于前人的研究成果,并且...
这些知识点涵盖了数据结构的基础概念、算法分析、以及特定数据结构(如线性表)的相关理论与实践应用。 ### 数据结构概论 #### 1. 数据结构的研究内容 - **逻辑结构与存储结构**:数据结构的研究主要包括数据的...
这种情况下,网络吞吐量——即在网络中无数据丢失时设备能接收的最大速率——会与通信子网的负荷成正比。当负荷达到一定阈值后,继续增加会导致网络吞吐量下降,这时就表明网络已出现拥塞。 拥塞控制与流量控制虽然...
G.729算法采用的是代数共轭结构码激励线性预测(CS-ACELP)技术,其核心在于结合了波形编码和参数编码的优点。具体步骤包括: - **话带滤波**:对输入的模拟语音信号进行预处理,滤除不必要的噪声。 - **采样**:以8...
RFC中定义了两种令牌桶算法——单速率三色标记算法和双速率三色标记算法,其评估结果都是为报文打上红、黄、绿三色标记。QoS会根据报文的颜色,设置报文的丢弃优先级,其中单速率三色标记比较关心报文尺寸的突发,而...