精华内容
下载资源
问答
  • 排序算法的时间复杂度
    2020-12-23 17:16:12

    各种排序算法比较

    各种常用排序算法

    类别

    排序方法

    时间复杂度

    空间复杂度

    稳定性

    复杂性

    特点

    最好

    平均

    最坏

    辅助存储

    简单

    插入

    排序

    直接插入

    O(N)

    O(N2)

    O(N2)

    O(1)

    稳定

    简单

    希尔排序

    O(N)

    O(N1.3)

    O(N2)

    O(1)

    不稳定

    复杂

    选择

    排序

    直接选择

    O(N)

    O(N2)

    O(N2)

    O(1)

    不稳定

    堆排序

    O(N*log2N)

    O(N*log2N)

    O(N*log2N)

    O(1)

    不稳定

    复杂

    交换

    排序

    冒泡排序

    O(N)

    O(N2)

    O(N2)

    O(1)

    稳定

    简单

    1、冒泡排序是一种用时间换空间的排序方法,n小时好

    2、最坏情况是把顺序的排列变成逆序,或者把逆序的数列变成顺序,最差时间复杂度O(N^2)只是表示其操作次数的数量级

    3、最好的情况是数据本来就有序,复杂度为O(n)

    快速排序

    O(N*log2N)

    O(N*log2N)

    O(N2)

    O(log2n)~O(n)

    不稳定

    复杂

    1、n大时好,快速排序比较占用内存,内存随n的增大而增大,但却是效率高不稳定的排序算法。

    2、划分之后一边是一个,一边是n-1个,

    这种极端情况的时间复杂度就是O(N^2)

    3、最好的情况是每次都能均匀的划分序列,O(N*log2N)

    归并排序

    O(N*log2N)

    O(N*log2N)

    O(N*log2N)

    O(n)

    稳定

    复杂

    1、n大时好,归并比较占用内存,内存随n的增大而增大,但却是效率高且稳定的排序算法。

    基数排序

    O(d(r+n))

    O(d(r+n))

    O(d(r+n))

    O(rd+n)

    稳定

    复杂

    注:r代表关键字基数,d代表长度,n代表关键字个数

    注:

    1、归并排序每次递归都要用到一个辅助表,长度与待排序的表长度相同,虽然递归次数是O(log2n),但每次递归都会释放掉所占的辅助空间,

    2、快速排序空间复杂度只是在通常情况下才为O(log2n),如果是最坏情况的话,很显然就要O(n)的空间了。当然,可以通过随机化选择pivot来将空间复杂度降低到O(log2n)。

    相关概念:

    1、时间复杂度

    时间复杂度可以认为是对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。

    常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)

    时间复杂度O(1):算法中语句执行次数为一个常数,则时间复杂度为O(1),

    2、空间复杂度

    空间复杂度是指算法在计算机内执行时所需存储空间的度量,它也是问题规模n的函数

    空间复杂度O(1):当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1)

    空间复杂度O(log2N):当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n)

    ax=N,则x=logaN,

    空间复杂度O(n):当一个算法的空间复杂度与n成线性比例关系时,可表示为0(n).

    更多相关内容
  • 根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
  • 快速排序时间复杂度: N个数据 第1次分成2组=2^1 第2次分成4组=2^2 第3次分成8组=2^3 … 第t次分成 2^t 组,完成所有数据的排序 所以2^t = N 所以 t = log2N 也就是logN ,也就是空间复杂度为 logN 在每一次排序里,...

    在这里插入图片描述

    快速排序时间复杂度:

    可以看这个视频视频
    https://www.bilibili.com/video/BV1xb411T7dN?spm_id_from=333.337.search-card.all.click

    N个数据
    第1次分成2组=2^1
    第2次分成4组=2^2
    第3次分成8组=2^3

    第t次分成 2^t 组,完成所有数据的排序
    所以2^t = N
    所以 t = log2N 也就是logN ,也就是空间复杂度为 logN
    在每一次排序里,又遍历了所有数据,所以每一次的时间复杂度是 N
    所以,快速排序总的平均时间复杂度是 o(NlogN)
    在这里插入图片描述
    最坏的情况:
    已经正序或者逆序排好了顺序,那么第一次要排N 个数,第二次 N-1 个,第三次 N-2 个,构成一个等差数列,所以时间复杂度为 (a1+an)*N/2=(N+1)*N/2 ≈ N^2
    所以时间复杂的最差为 o(N^2)
    在这里插入图片描述

    展开全文
  • 文章目录一、排序算法的介绍二、排序的分类三、算法的时间复杂度3.1 度量一个程序(算法)执行时间的两种方法3.2 时间频度3.3 时间复杂度3.4 常见时间复杂度3.5 平均时间复杂度和最坏时间复杂度四、算法的空间复杂度 ...

    一、排序算法的介绍

    排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排列的过程。

    二、排序的分类

    1)内部排序:
    指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。
    2) 外部排序法:
    数据量过大,无法全部加载到内存中,需要借助外部存储(文件等)等进行排序。
    3) 常见的排序算法分类(见右图):
    在这里插入图片描述

    三、算法的时间复杂度

    3.1 度量一个程序(算法)执行时间的两种方法

    1. 事后统计的方法
      这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式,要在同一台计算机的相同状态下运行,才能比较那个算法速度更快。
    2. 事前估算的方法
      通过分析某个算法的时间复杂度来判断哪个算法更优.

    3.2 时间频度

    1)基本介绍
    时间频度:一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。[举例说明]
    2)举例说明-基本案例
    比如计算 1-100 所有数字之和, 我们设计两种算法:
    在这里插入图片描述
    3)举例说明-忽略常数项
    在这里插入图片描述
    结论:

    1. 2n+20 和 2n 随着 n 变大,执行曲线无限接近, 20 可以忽略
    2. 3n+10 和 3n 随着 n 变大,执行曲线无限接近, 10 可以忽略

    4)举例说明-忽略低次项
    在这里插入图片描述
    结论:

    1. 2n^2+3n+10 和 2n^2 随着 n 变大, 执行曲线无限接近, 可以忽略 3n+10
    2. n^2+5n+20 和 n^2 随着 n 变大,执行曲线无限接近, 可以忽略 5n+2

    5)举例说明-忽略系数
    在这里插入图片描述
    结论:

    1. 随着 n 值变大,5n^2+7n 和 3n^2 + 2n ,执行曲线重合, 说明 这种情况下, 5 和 3 可以忽略。
    2. 而 n^3+5n 和 6n^3+4n ,执行曲线分离,说明多少次方式关键

    3.3 时间复杂度

    1. 一般情况下,算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数,用 T(n)表示,若有某个辅助函数 f(n),使得当 n 趋近于无穷大时,T(n) / f(n) 的极限值为不等于零的常数,则称 f(n)是 T(n)的同数量级函数。记作 T(n)=O( f(n) ),称O( f(n) ) 为算法的渐进时间复杂度,简称时间复杂度。
    2. T(n) 不同,但时间复杂度可能相同。 如:T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的 T(n) 不同,但时间复杂度相同,都为 O(n²)。
    3. 计算时间复杂度的方法:
      • 用常数 1 代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1
      • 修改后的运行次数函数中,只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²
      • 去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

    3.4 常见时间复杂度

    1. 常数阶 O(1)
      在这里插入图片描述

    2. 对数阶 O(log2n)
      在这里插入图片描述

    3. 线性阶 O(n)
      在这里插入图片描述

    4. 线性对数阶 O(nlog2n)
      在这里插入图片描述

    5. 平方阶 O(n^2)
      在这里插入图片描述

    6. 立方阶 O(n^3)
      说明:参考上面的 O(n²) 去理解就好了,O(n³)相当于三层 n

    7. k 次方阶 O(n^k)

    8. 指数阶 O(2^n)
      在这里插入图片描述
      说明:

      1. 常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)< Ο(nk) <Ο(2n) ,随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低
      2. 从图中可见,我们应该尽可能避免使用指数阶的算法

    3.5 平均时间复杂度和最坏时间复杂度

    1. 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,该算法的运行时间。
    2. 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的
      原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会
      比最坏情况更长。
    3. 平均时间复杂度和最坏时间复杂度是否一致,和算法有关(如图:)
      在这里插入图片描述

    四、算法的空间复杂度

    1. 类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模 n 的函数。
    2. 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 n 有关,它随着 n 的增大而增大,当 n 较大时,将占用较多的存储单元,例如快速排序和归并排序算法, 基数排序就属于这种情况
    3. 在做算法分析时,主要讨论的是时间复杂度。从用户使用体验上看,更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.
    展开全文
  • 排序算法中比较次数与初始元素序列排序无关的只有选择排序和基数排序,其他的都有关。 元素的移动次数与关键字的初始排列次序无关的是:基数排序 元素的比较次数与初始序列无关是:选择排序、折半插入排序 算法的...
    排序算法中比较次数与初始元素序列排序无关的只有选择排序和基数排序,其他的都有关。
    
    元素的移动次数与关键字的初始排列次序无关的是:基数排序
    元素的比较次数与初始序列无关是:选择排序、折半插入排序
    算法的时间复杂度与初始序列无关的是:选择排序、堆排序、归并排序、基数排序
    算法的排序趟数与初始序列无关的是:插入排序、选择排序、基数排序
    
    堆排序
    (1)堆是一颗完全二叉树;
    (2)()顶堆中的每一个节点都不小于(不大于)它的父节点;
    (3)堆的插入、删除元素的时间复杂度都是O(log n)(4)建堆的时间复杂度是O(n)(5)堆排序的时间复杂度是O(nlog n)(6)堆排序的空间复杂度是O(1)​;
    

    在这里插入图片描述

    展开全文
  • 选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
  • 几种常见排序算法时间复杂度

    万次阅读 2020-07-15 15:36:47
    插入排序时间复杂度: 最好: 所有元素已经排好序,只需遍历一遍,无需交换位置; 最坏: 所有元素逆序排列,遍历一次需要比较的元素个数每次+1,所以时间复杂度是O(n^2); 平均时间复杂度就是O(n^2)喽。 2、 ...
  • 排序算法时间复杂度总结表

    千次阅读 2019-12-20 03:15:02
    排序方法 最好时间 最坏时间 平均时间 辅助空间 稳定性 直接插入 O(n) O(n2) O(n2) O(1) ...
  • PAGE PAGE 1 PAGE 2 PAGE 2 1 排序算法比较 主要内容 1)利用随机函数产生10000个随机整数对这些数...3给出该排序算法统计每一种排序方法的性能以运行程序所花费的时间为准进行对比找出其中两种较快的方法 程序的主要功
  • 排序算法时间复杂度的记忆方法

    千次阅读 2020-03-05 18:15:30
    选泡插, 快归堆希桶计基, n方n老n一三, 对n加kn乘k, 不稳稳稳不稳稳, 不稳不稳稳稳稳。 冒泡:基本不用,太慢 选择:基本不用,慢、不稳 ...马士兵说:30秒让你记住所有排序算法-宋词记忆法 ...
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 2017-07-30 21:33:22
    排序算法分类排序算法比较表格填空 排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定 冒泡排序 :————-: :—–: :—–: :—–: 选择排序 :————-: :—–: :—–: :—–: 直接插入...
  • 各种排序算法时间复杂度总结

    千次阅读 2019-05-19 18:44:14
    https://blog.csdn.net/weiwenhp/article/details/8622728
  • 常见数据结构排序算法时间复杂度

    千次阅读 2021-01-21 00:35:04
  • 排序算法-算法时间复杂度和空间复杂度概念 详细讲解 排序算法的介绍 排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排列的过程。 排序的分类: 1)内部排序: 指将需要处理的所有数据都加载...
  • C语言四种排序算法时间复杂度比较.doc
  • 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。  各种内部排序按所采用的基本思想(策略)可...
  • 各种排序算法时间复杂度和空间复杂度表: 比较时间复杂度函数的情况如下图: 对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法: 接下来博主抽时间要整理一下各经典算法思想和心得,敬请期待
  • 排序算法及其时间复杂度

    万次阅读 多人点赞 2021-03-16 21:35:16
    1. 排序算法时间复杂度 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面; 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面; 内排序:所有排序操作都在内存中完成; 外排序:由于数据太...
  • 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 选择排序 Selection n2 n2 n2 ...
  • 提示:冒泡排序算法是非常重要的算法,一定要熟练掌握。思路可以参考一位大佬博主的博客:帅地。介绍的十分详细,理解了之后,可以参考我的代码 ,是入门级别的,比较好懂。关于时间复杂度是数据结构的内容,没学过...
  • 排序算法时间复杂度

    千次阅读 2022-04-19 15:06:04
    链接:直接插入排序的平均时间复杂度为( )。__牛客网 来源:牛客网 一、时间复杂度: (1)定义: 时间复杂度是用来定性描述算法执行所需要的时间。现假设问题规模为n,解决该问题的算法中基本操作重复执行的...
  • 算法效率度量 1.时间复杂度O(n) 原则: 常数1代替所有加法中的常数 只保留最高阶数项(且不要前面的系数) ...2.空间复杂度 ...常用空间换时间 ...时间复杂度 ...时间复杂度:算法性能指标(本质常数时间...常用排序算法及...
  • 常见的几种排序算法时间复杂度

    千次阅读 2021-12-08 18:31:47
    排序算法的介绍 概述:排序也称排序算法,排序是将一组数据,依指定的顺序进行排列的过程。 排序的分类 (1) 内部排序:指将需要处理的所有数据都加载到内部存储器中进行排序。 (2) 外部排序:数据量过大,无法全部...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 284,788
精华内容 113,915
关键字:

排序算法的时间复杂度