`
endual
  • 浏览: 3566334 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

常用的排序算法的时间复杂度和空间复杂度

 
阅读更多

常用的排序算法的时间复杂度和空间复杂度

分类: 笔试面试题
2010-11-09 07:52 470人阅读 评论(2) 收藏 举报

常用的排序算法的时间复杂度和空间复杂度

排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度
冒泡排序 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)



1、时间复杂度
(1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
(2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 2、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。
(3)渐进时间复杂度评价算法时间性能   主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

2、类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地/"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

 

 

 

http://blog.csdn.net/wuxinyicomeon/article/details/5996675

分享到:
评论

相关推荐

    排序算法时间复杂度的研究.pdf

    ### 排序算法时间复杂度的研究 #### 引言 排序是计算机科学中的基础操作之一,主要用于对数据集中的元素按照特定的顺序进行排列。排序算法的效率直接关系到计算机程序的整体性能。根据数据是否完全加载到内存中,...

    学习电脑信息常用的排序算法的时间复杂度和空间复杂度

    "学习电脑信息常用的排序算法的时间复杂度和空间复杂度" 时间复杂度是指算法执行所耗费的时间,它是算法中语句执行次数的函数,用 T(n) 表示。时间复杂度是评价算法时间性能的重要指标。常见的时间复杂度有:常数阶...

    排序算法时间复杂度的分析java语言描述

    以下是对选择排序、冒泡排序、归并排序、快速排序和插入排序这五种常见排序算法的详细介绍,以及如何分析它们的时间复杂度。 1. **选择排序(Selection Sort)** - 原理:选择排序是一种简单直观的排序算法,它...

    常用排序算法复杂度

    常用排序算法时间复杂度、空间复杂度总结。包括:冒泡排序、快速排序、选择排序、堆排序、插入排序、Shell排序、归并排序、基数排序。

    算法的时间复杂度和空间复杂度

    算法的时间复杂度和空间复杂度 算法的时间复杂度和空间复杂度是衡量算法性能的两个重要指标。...算法的时间复杂度和空间复杂度是衡量算法性能的重要指标,选择合适的排序算法可以提高算法的效率和性能。

    算法时间复杂度的实验测试.zip_堆排序;算法时间复杂度_时间复杂度_胡书晗

    尽管在构建堆的过程中可能需要更多的交换和下沉操作,但由于堆排序算法的性质,每次操作仍然保证了时间复杂度不超过log n,因此总操作次数不会超过n log n。 平均情况下,堆排序的时间复杂度同样为O(n log n)。这是...

    排序算法时间复杂度的研究

    ### 排序算法时间复杂度的研究 #### 引言 排序是计算机科学中的基础操作之一,在数据处理与分析中占据着重要地位。排序算法的好坏直接影响到计算机程序的执行效率,尤其是在处理大规模数据集时更为明显。根据数据...

    关于算法时间复杂度的计算

    时间复杂度的计算是为了比较算法的运行时间和空间要求,并使这种比较能与程序设计语言、编译系统、机器结构、处理器的速度及系统的负载等复杂因素无关。 在实际中,算法的时间复杂度可以分为常数阶、对数阶、线性阶...

    快速排序与归并排序的时间复杂度分析

    总的来说,快速排序和归并排序是排序算法中的重要成员,它们在时间和空间复杂度上的分析对于理解排序算法的效率至关重要。深入理解和掌握这些算法有助于优化代码性能,提高软件系统的整体运行效率。

    信息学奥赛算法时间复杂度和空间复杂度计算

    例如,一个快速排序算法的时间复杂度是O(n log n),但可能会使用额外的空间来辅助排序,因此它的空间复杂度可能是O(log n)。而插入排序虽然在最坏情况下时间复杂度是O(n^2),但它是一个原地排序算法,空间复杂度为O...

    各种排序算法时间复杂度1

    【排序算法时间复杂度】 排序算法是计算机科学中不可或缺的一部分,它们用于组织和优化数据,使其按照特定顺序排列。不同的排序算法有不同的...理解这些算法的时间和空间复杂度,有助于我们在编程时做出明智的选择。

    排序算法在不同数组状态下时间复杂度的比较

    在实际应用中,通常会结合具体情况和性能需求选择合适的排序算法。 通过分析`main.cpp`等源代码文件,我们可以模拟不同初始状态的数组,运行这些排序算法,并记录执行时间,从而直观地比较它们在不同情况下的性能。...

    排序算法的时间复杂度

    使用插入、冒泡、选择、快排、归并、堆排共6种排序算法对同一序列进行排序,统计排序所需的平均时间并比较算法在时间上的优劣。供学习使用。

    各种排序算法的稳定性和时间复杂度小结

    稳定性和时间复杂度是评估排序算法性能的两个关键指标。 【稳定排序算法】指的是在排序过程中,相等元素的相对顺序不会改变。例如,冒泡排序、插入排序、归并排序和基数排序都是稳定的。冒泡排序通过相邻元素的比较...

    算法的设计与分析——时间复杂度.docx

    * 算法的时间和空间复杂度 * 算法的正确性和可靠性 * 算法的优化和改进 二、时间复杂度的定义和计算 时间复杂度是指算法执行所需的时间成本,是算法设计与分析的核心概念之一。时间复杂度通常用大O符号表示,例如O...

    排序算法比较 时间复杂度 稳定性描述

    本文将对几种常见的排序算法进行对比分析,包括它们的时间复杂度和稳定性特点,以便读者能够更好地理解每种算法的适用场景。 #### 1. 插入排序 **时间复杂度**: - 最好情况:当输入数组已经是有序的,时间复杂度...

    排序算法与时间复杂度得测量

    在计算机科学领域,排序算法是数据结构和算法分析的重要组成部分,它涉及到如何高效地重新排列一个数据序列。本文将深入探讨几种常见的...理解这些排序算法的工作原理和时间复杂度,可以帮助我们编写出更加优化的代码。

    12种排序及时间复杂度稳定性

    以下是标题和描述中提到的12种排序算法及其时间复杂度和稳定性特点的详细解释: 1. 计数排序(Counting Sort): 这是一种非基于比较的排序算法,适用于整数排序。它通过统计每个数字出现的次数,直接确定每个元素...

    数据机构综合课设内部排序算法比较.docx

    **内部排序算法详解** 内部排序是指数据记录在内存中...在比较排序算法时,不仅要关注时间复杂度,还要考虑实际运行环境和特定数据集下的性能。通过生成随机数据并进行多次实验,可以更好地评估和理解这些算法的性能。

Global site tag (gtag.js) - Google Analytics