精华内容
下载资源
问答
  • 常用的排序算法和时间复杂度

    千次阅读 2016-05-31 17:53:42
    1. 数据结构部分 数据结构中常用的操作的效率表 通用数据结构 查找  插入   删除 遍历  数组 O(N) O(1) O(N) — 有序数组 O(logN)

    1. 数据结构部分

    数据结构中常用的操作的效率表

    通用数据结构

    查找 

    插入 

     删除

    遍历 

    数组

    O(N)

    O(1)

    O(N)

    有序数组

    O(logN)

    O(N)

    O(N)

    O(N)

    链表

    O(N)

    O(1)

    O(N)

    有序链表

    O(N)

    O(N)

    O(N)

    O(N)

    二叉树

    O(logN)

    O(logN)

    O(logN)

    O(N)

    二叉树(最坏)

    O(N)

    O(N)

    O(N)

    O(N)

    红黑树

    O(logN)

    O(logN)

    O(logN)

    O(N)

    2-3-4树

    O(logN)

    O(logN)

    O(logN)

    O(N)

    哈希表

    O(1)

    O(1)

    O(1)

    专用数据结构

     

     

     

     

    O(1)

    O(1)

    队列

    O(1)

    O(1)

    优先级队列

    O(N)

    O(1)

    优先级队列(堆)

    O(logN)

    O(logN)

     


    2. 排序算法

    常见的排序算法比较表

    排序

    平均情况

    最好情况

    最坏情况

    稳定与否

    空间复杂度

    冒泡排序

    O(N2)

    O(N)

    O(N2)

    稳定

    1

    选择排序

    O(N2)

    O(N2)

    O(N2)

    不稳定

    1

    插入排序

    O(N2)

    O(N)

    O(N2)

    稳定

    1

    希尔排序

    O(NlogN)

    (依赖于增量序列)

    不稳定

    1

    快速排序

    O(NlogN)

    O(NlogN)

    O(N2)

    不稳定

    O(logN)

    归并排序

    O(NlogN)

    O(NlogN)

    O(NlogN)

    稳定

    O(N)

    二叉树排序

    O(NlogN)

    O(NlogN)

    O(N2)

    稳定

    O(N)

    堆排序

    O(NlogN)

    O(NlogN)

    O(NlogN)

    不稳定

    1

    拓扑排序

    O(N+E)

    O(N)

    首先先给出我们常用的算法的时间复杂度,后面会具体讲解每一个算法,以及在不同的场合下哪种时间复杂度很高效
    展开全文
  • 常用的排序算法时间复杂度和空间复杂度 常用的排序算法时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) ...

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

     

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

     

    排序法

    最差时间分析 平均时间复杂度 稳定度 空间复杂度
    冒泡排序 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).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

     

     

    转载于:https://www.cnblogs.com/unity3d-Yang/p/4788522.html

    展开全文
  • 常用的排序算法时间复杂度和空间复杂度
    http://blog.csdn.net/wuxinyicomeon/article/details/5996675
    

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

    排序法

    最差时间分析 平均时间复杂度 稳定度 空间复杂度
    冒泡排序 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).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 976
精华内容 390
关键字:

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