精华内容
下载资源
问答
  • 算法效率度量 1.时间复杂度O(n) 原则: 常数1代替所有加法中的常数 只保留最高阶数项(且不要前面的系数) ...2.空间复杂度 ...常用空间换时间 ...时间复杂度 ...时间复杂度:算法性能指标(本质常数时间...常用排序算法及...

    算法效率度量

    1.时间复杂度O(n)
    原则:

    1. 常数1代替所有加法中的常数
    2. 只保留最高阶数项(且不要前面的系数)
    3. O(1)<O(log n)<O(n)<O(n logn)<O(n^2)

    2.空间复杂度
    常用空间换时间

    时间复杂度

    时间复杂度:算法性能指标(本质常数时间操作的个数);先看指标再看系数;先看高阶项再看低阶项
    常数时间操作:例如位操作、算术运算等。

    master公式

    T ( N ) = a T ( N / b ) + O ( N d ) T(N)=aT(N/b)+O(N^{d}) T(N)=aT(N/b)+O(Nd)
    其中a表示子过程发生次数,b表示子过程样本量,
    l o g b a &gt; d → log^{a}_{b}&gt;d \rightarrow logba>d复杂度为 O ( N l o g b a ) O(N^{log^{a}_{b}}) O(Nlogba)
    l o g b a = d → log^{a}_{b}=d \rightarrow logba=d复杂度为 O ( N d l o g N ) O(N^{dlog^{N}}) O(NdlogN)
    l o g b a &gt; d → log^{a}_{b}&gt;d \rightarrow logba>d复杂度为 O ( N d ) O(N^{d}) O(Nd)

    常用排序算法及其时间复杂度

    冒泡排序(bubblesort): O ( N 2 ) O(N^{2}) O(N2)

    选择排序: O ( N 2 ) O(N^{2}) O(N2)

    插入排序: O ( N 2 ) O(N^{2}) O(N2)

    时间复杂度与数据状况有关,最好 O ( N ) O(N) O(N)最差 O ( N 2 ) O(N^{2}) O(N2)。但算法性能一律按最差考虑,即插入排序时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)

    归并排序: O ( N l o g N ) O(Nlog{N}) O(NlogN)

    分治思想

    总结

    常用排序算法时间复杂度空间复杂度稳定性
    平均情况最好情况最坏情况辅助存储
    交换排序冒泡排序 O(n*n) O(n) O(n*n) O(1) 稳定
    快速排序 O(n*logn) O(n*logn) O(n*n) O(n*logn) 不稳定
    插入排序直接插入 O(n*n) O(n) O(n*n) O(1) 稳定
    shell排序 O(n*n) O(n) O(n*n) O(1) 不稳定
    选择排序直接选择 O(n*n) O(n*n) O(n*n) O(1) 不稳定
    堆排序 O(n*logn) O(n*logn) O(n*logn) O(1) 不稳定
    归并排序 O(n*logn) O(n*logn) O(n*logn) O(n) 稳定
    展开全文
  • 均按从小到大排列 k代表数值中的"数位"个数 n代表数据规模 m代表数据的最大值减最小值

    在这里插入图片描述

    均按从小到大排列
    k代表数值中的"数位"个数
    n代表数据规模
    m代表数据的最大值减最小值
    
    展开全文
  • 一、常用排序算法时间复杂度和空间复杂度表格 二、特点 1.归并排序: (1)n大时好,归并比较占用内存,内存随n的增大而增大,但却是效率高且稳定的排序算法。 (2)归并排序每次递归都要用到一个辅助表,...

    一、常用排序算法的时间复杂度和空间复杂度表格

    二、特点


    1.归并排序:


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

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

    (3)虽然插入排序的时间复杂度为O(n2),归并排序的时间复杂度为O(nlog2n),但插入排序中的常数因子使得它在n较小时,运行更快一些。因此,在归并排序算法中,当子问题足够小时,采用插入排序算法就比较合适

    (4)以时间换空间:网上很多blog分享空间复杂度只有O(1)的归并排序法;因为传统的归并排序所消耗的空间主要是在归并函数(把两个有序的函数合并成一个有序的函数),所以如果要让时间复杂度为O(1),那么也只能在归并函数中做文章了。其主要思想就是借助于快速排序(其实就是相当于归并函数被快速排序函数替换了),这样的方法虽然可以减少内存的消耗,但是却会在时间上带来损失,因为这样时间复杂度却变成了O(n2)了;所以这种方法并不是一个两全其美的idea。


    2.冒泡排序

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

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

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

    3.快速排序

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

    (2)划分之后一边是一个,一边是n-1个,这种极端情况的时间复杂度就是O(n2)

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

    (4)快速排序空间复杂度只是在通常情况下才为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)         

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

    原文:https://blog.csdn.net/jiajing_guo/article/details/69388331 
     

    展开全文
  • 常用排序算法时间复杂度 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n) 选择排序 O(n2) O(n2) 稳定 O(1) 二叉树排序 O(...
  • 最近在准备秋招的期间遇到了很多排序算法时间复杂度、空间复杂度、稳定性相关的题目,那就做个大致的总结吧。 排序算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定...
  • 排序算法分类 排序算法比较表格 排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定 冒泡排序 O(n2) O(n2) O(1) 是 选择排序 O(n2) O(n2) O(1) ....
  • 归并排序的基本思想 归并排序法是将两个或以上的有序表合并成一个新的有序表,即把待排序序列分成若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。注意:一定要是有序序列!  归并排序...
  • 插入排序时间复杂度: 最好: 所有元素已经排好序,只需遍历一遍,无需交换位置; 最坏: 所有元素逆序排列,遍历一次需要比较的元素个数每次+1,所以时间复杂度是O(n^2); 平均时间复杂度就是O(n^2)喽。 2、 ...
  • 本篇文章是对php中的常用算法以及时间复杂度进行了详细的分析介绍,需要的朋友参考下
  • 各种常用排序算法时间复杂度

    千次阅读 2018-11-24 23:25:11
    时间复杂度 空间复杂度 稳定性 复杂性 平均情况 最好情况 最坏情况 辅助空间 直接插入排序 O(n^2) O(n) O(n^2) O(1) 稳定 简单 希尔排序 O(n^1....
  • 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。  各种内部排序按所采用的基本思想(策略)可...
  • 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 各种内部排序按所采用的基本思想(策略)可分为...
  • 一、时间复杂度 二、空间复杂度   冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引) 快速排序空间...
  • java各种排序算法的稳定性和时间复杂度小结
  • 包含排序类型有以下几种:插入排序,交换排序,选择排序,归并排序,基数排序
  • 排序算法时间复杂度比较

    千次阅读 2019-01-27 08:53:46
    各种排序算法比较 一、基本排序算法 冒泡排序 假如我们现在按身高升序排队,一种排队的方法是:从第一名开始,让两人相互比身高,若前者高则交换位置,更高的那个在与剩下的人比,这样一趟下来之后最高的人就站到...
  • 各种常用排序算法时间复杂度

    千次阅读 2013-04-10 11:06:36
  • 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 冒泡法:  这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的...
  • 周末无事,带娃之余看到娃娃在算数...选择排序算法通常会根据以下几个纬度来考虑:时间复杂度空间复杂度算法的稳定性(待排序序列中有值相等的元素,经过排序之后相等元素之间原有的顺序不变)时间复杂度和空间复杂度...
  • 这是使用desmos画出来的图形。...)低于xlog(x)高于x,但通常我们的排序算法快排和归并的最优是xlog(x)最坏是n^2, 通过二分查找改进的排序算法最坏是log(n!),最好是n。 虽然nlog(n)和log(n!)相差不...
  • 一、常用排序算法时间复杂度和空间复杂度表格     二、特点   1.归并排序:   (1)n大时好,归并比较占用内存,内存随n的增大而增大,但却是效率高且稳定的排序算法。 (2)归并排序每次递归都要...
  • 各种常用排序算法 类别 排序方法 时间复杂度 空间复杂度 稳定性 复杂性 特点 最好 平均 最坏 ...
  • 排序算法: 查找算法:
  • 常见排序算法及其时间复杂度

    万次阅读 多人点赞 2019-06-20 18:00:18
    常见排序算法及其时间复杂度 一、内部排序:1.稳定的排序算法1.1 冒泡排序1.1.1 冒泡排序流程1.1.2 冒泡排序的实现1.2 插入排序1.2.1 插入排序流程1.2.2 插入排序的实现1.3 归并排序1.3.1 归并排序流程1.3.2 归并...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,484
精华内容 24,993
关键字:

常用排序算法时间复杂度