精华内容
下载资源
问答
  • 快速排序空间复杂度
    2021-12-23 17:35:37

    算法分析课,我感觉我分析不明白时间复杂度。所以就记录一下子怎么进行空间复杂度。在这之前需要了解时间复杂度如何计算,以及知道 O ( n ) Ω ( n ) Θ ( n ) 0 O(n) \quad \Omega(n) \quad \Theta(n)0 O(n)Ω(n)Θ(n)0


    计算原则

    1. 有数组就看数组长度
    2. 有递归就看递归深度(栈的容量)
    3. 二者都有取最大值

    一般情况下,一个程序在机器上执行时,除了需要寄存本身所用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的辅助存储空间。其中,对于输入数据所占的具体存储量取决于问题本身,与算法无关,这样只需分析该算法在实现时所需要的辅助空间就可以了。若算法执行时所需要的辅助空间相对于输入数据量而言是个常数,则称这个算法为原地工作,辅助空间为O(1)。


    那看一下快排的空间复杂度
    假设从小到大排,选第一个为轴值:

    1 2 3 4 5 6 7 ... n
    选轴值怎么选:
    1 2 3…
    这样递归的深度就是n,空间复杂度 O ( n ) O(n) O(n)

    n n-1 ... 6 5 4 3 2 1
    这样轴值是:
    n n-1 n-2 …
    递归深度依旧是n,空间复杂度依旧是 O ( n ) O(n) O(n)

    当序列恰好平衡的时候,就是每次轴值都恰好能把序列分两半的时候,
    这样轴值就是:
    在这里插入图片描述
    这样递归深度就是 O ( log ⁡ 2 n ) O(\log_2^n) O(log2n)

    更多相关内容
  • 每次递归所需要的空间大小都是一样的而且就算是第N次递归,每次递归所需的栈空间也是一样的,所以每次递归中需要的空间是一个常量,并不会随着n的变化而变化...),所以快速排序空间复杂度就是。2.快排的空间复杂度

    1.不理解快速排序,看这篇博客 

    http://t.csdn.cn/Sgzmc 

    2.快排的空间复杂度

    1. 快排并没有开辟空间,但是使用了递归,递归会开辟栈帧
    2. 递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度
    3. 每次递归所需要的空间大小都是一样的而且就算是第N次递归,每次递归所需的栈空间也是一样的,所以每次递归中需要的空间是一个常量,并不会随着n的变化而变化,每次递归的空间复杂度就是O(1)

    4. 每次递归所需的空间都被压到调用栈里(压栈),所以快速排序的空间复杂度就是递归算法的空间复杂度 = 每次递归的空间复杂度O(1) * 递归深度

    如图:

    非顺序:空间复杂度=深度:O(lonN)

     

     顺序:空间复杂度=深度:O(N)

     

    展开全文
  • C/C++中快速排序的时间空间复杂度分析 1.什么是快速排序 我理解的是,快速排序用的是分治法,运用的递归的算法,先挑选一个基准值,小于基准值的数放在左边, 大于基准值的数放在基准值的右边,这样就泾渭分明的三块...

    C/C++中快速排序的时间空间复杂度分析

    1.什么是快速排序

    我理解的是,快速排序用的是分治法,运用的递归的算法,先挑选一个基准值,小于基准值的数放在左边,
    大于基准值的数放在基准值的右边,这样就泾渭分明的三块;但是这三块是有序的,基准值左边右边的内
    部数是无序的,所以,将基准值左右两端继续进行快速排序,直到区间长度为1,排序就完成了。
    

    2.快速排序代码实现

    下面使用vs2013实现快速排序:
    主逻辑函数

    在这里插入图片描述
    输出为:在这里插入图片描述

    3.快速排序的时间复杂度

    每种排序方式都会有最优的时间复杂度以及最差的时间复杂度,就像快速排序,你每次取出都取出整个数组
    中最小/最大的那个元素,那就是冒泡排序了,他的时间复杂度为T[n] = n * (n-1) = n^2 + n;也就是O( n^2 )
    

    那么最优情况下,时间复杂度如何计算呢

    快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(上方代码并不是最优情况);此时的时间复杂度公式则为:T[n] = 2T[n/2] + f(n);f[n] 就是第一次平分这个数组时所花的时间;T[n/2]是平分后的两边数组的时间复杂度,
    下面来推算下,在最优的情况下快速排序时间复杂度的计算(用迭代法):

    T[n] =  2T[n/2] + n              			 ----第一次递归
    
    令:n = n/2  =  2 { 2 T[n/4] + (n/2) }  + n   ----第二次递归
                =  2^2 T[ n/ (2^2) ] + 2n
                  
    令:n = n/(2^2)   =  2^2  {  2 T[n/ (2^3) ]  + n/(2^2)}  +  2n-----第三次递归
    =  2^3 T[  n/ (2^3) ]  + 3n
    
    令:n = n/(  2^(m-1) )    =  2^m T[1]  + mn                   ----第m次递归(m次后结束)
    

    当最后平分的不能再平分时,也就是说把公式一直往下跌倒,到最后得到T[1]时,说明这个公式已经迭代完了(T[1]是常量了)。
    得到:T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = lgn;
    T[n] = 2^m T[1] + mn ;其中m = lgn;
    T[n] = 2^(lgn) T[1] + nlgn = n T[1] + nlgn = n + nlgn ;其中n为元素个数
    又因为当n >= 2时:nlgn >= n (也就是lgn > 1),所以取后面的 nlgn;
    综上所述:快速排序最优的情况下时间复杂度为:O( nlgn )

    4.快速排序空间复杂度

    快速排序的使用空间是O(1);其主要的空间复杂都在递归上了
    

    最优的情况下空间复杂度为:O(logn) ;每一次都平分数组的情况
    最差的情况下空间复杂度为:O( n ) ;退化为冒泡排序的情况

    问一个问题:怎么才能避免变成冒泡排序提高效率呢?

    展开全文
  • 我们来分析一下快速排序法的性能。 快速排序的时间性能取决于快速排序递归的深度, 可以用递归树来描述递归算法的执行情况。 如图9‐9‐7所示,它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。...

    我们来分析一下快速排序法的性能。

    快速排序的时间性能取决于快速排序递归的深度,

    可以用递归树来描述递归算法的执行情况。

    如图9‐9‐7所示,它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50,正好是待排序的序列的中间值,因此递归树是平衡的,此时性能也比较好。

    在这里插入图片描述

    image-20210207223931143

    image-20210207224022570
    空间复杂度

    主要是递归造成的栈空间的使用,最好情况,递归树的深度为logn

    其空间复杂度也就为 O(logn),

    最坏情况

    需要进行n‐1递归调用,其空间复杂度为O(n),

    平均情况,

    空间复杂度也为O(logn)。

    可惜的是,由于关键字的比较和交换是跳跃进行的,因此,

    快速排序是一种不稳定的排序方法。

    参考文章https://blog.csdn.net/nsjlive/article/details/102531375

    展开全文
  • 快速排序思想: 快排的核心是递归。以从小到大排序为例,把第一个值作为基准值,先从最右边进行比较,若比基准值大,那么右边的指针左移一位,如果比基准值大,那么交换基准值和当前位置的值,改变比较方向,开始从...
  • 快速排序空间复杂度|数据结构

    千次阅读 2019-12-10 19:54:15
    空间复杂度 最优的情况下空间复杂度为:O(logn) ;每一次都平分数组的情况 最差的情况下空间复杂度为:O( n ) ;退化为冒泡排序的情况 首先就地快速排序使用的空间是O(1)的,也就是个常数级; **而真正消耗空间...
  • 4中常见排序方式的时间,空间复杂度(冒泡排序,插入排序,选择排序,快速排序) 时间复杂度的定义: 如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数T(n)称为这一算法的“时间复杂...
  • 快速排序 及其时间复杂度和空间复杂度

    万次阅读 多人点赞 2018-07-16 14:33:00
    快速排序是排序算法中效率相对较高的,但使用的人却是比较少,大家一般信手拈来的排序算法就是冒泡排序。因为冒泡排序主观,容易理解,而快速排序使用到了递归,大家可能就有点不知所措了。算法分析 快速排序由C. A...
  • 排序算法及实现
  • 三种排序算法时间复杂度均为nlgn,空间复杂度不同 快速排序 不需要额外内存 消耗lgn到n的栈空间 public class QuickSort { static void quickSort(int[] array){ quickSortofRange(array, 0, array.length-1); ...
  • 四种排序:选择,插入,冒泡,快速排序原理及其对应的时间空间复杂度 首先,在了解四种排序之前,让我们来了解一下什么是时间复杂度和空间复杂度。 时间复杂度:算法的时间复杂度是一个函数,它定性描述该算法的运行...
  • 时间复杂度 在算法的分析中,语句的执行次数T(n)是一个关于n(问题规模)的一个函数。分析n的变化引起T(n)的改变,进而得到T(n)的数量级,也就是时间频率。如果存在某一个辅助函数f(n),当n趋于无穷大时,T(n)...
  •  快速排序是排序算法中效率相对较高的,但使用的人却是比较少,大家一般信手拈来的排序算法就是冒泡排序。因为冒泡排序主观,容易理解,而快速排序使用到了递归,大家可能就有点不知所措了。 算法分析  快速...
  • 本人用入栈出栈来模拟递归的过程,下面是栈的结构和递归代码和非递归:typedefstruct{int*base;...L,intlow,inthigh)//非递归的快速排序{if(low>=high)return;intleft;intright;intpivot;StackS;S.b...
  • i{this[i] = n}) } const arr = [ 5,4,3,2,1,6,9,8,7] arr.quickSort() console.log(arr) 快速排序空间复杂度是多少? 主要是递归造成的栈空间的使用,最好情况,递归树的深度为 log2​n 空间复杂度也就为 O(logn...
  • 选择一个关键字(一般是第一个),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 代码: ```java class ...
  • 快速排序的基本思想:  通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对这两部分继续进行排序,直到整个序列有序。  先看一下这幅图: 把整个...
  • 四大排序的时间复杂度和空间复杂度时间复杂度时间复杂度的表示方法时间复杂度的分析和计算方法常见的几种时间复杂度常见的时间复杂度排序空间复杂度 时间复杂度 (1)时间频率 一个算法执行所耗费的时间,从理论上是不...
  • 算法-空间复杂度大O1的快速排序 不考虑占用空间的大小 比较简单 $arr = [1,3,2,6,7,8,6,5,4,2,2,2,2,2,0,0,0,0,0,0,0,0,0]; function q( $arr ){ //排除极限情况 $len = count($arr); if($len <= 1){ ...
  • 文章目录1 冒泡排序2 选择排序3 插入排序4 归并排序5 快速排序6 堆排序7 桶排序8 基数排序9 外部排序 1 冒泡排序 时间复杂度:O(n*n) 稳定性:稳定 空间复杂度:O(1) 2 选择排序 时间复杂度:O(n*n) 稳定性:不稳定 ...
  • 一、快速排序 思想:对一组数据进行排序,找到一个位置放置这组数据的第一个数,该位置左边的数比该数小,右边比该数大。然后分别对左边和右边的数据再次使用同样的方法,最后直到左右两边只有一个数据,结束。 ...
  • 归并排序空间复杂度

    千次阅读 2021-05-29 09:32:03
    (待会儿你会发现,即便是快速排序,最坏情况下,时间复杂度也是 O(n^2)。)但是,归并排序并没有像快排那样,应用广泛,这是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法。 这是因为归并...
  • 一、常用排序算法的时间复杂度和空间复杂度表格     二、特点   1.归并排序:   (1)n大时好,归并比较占用内存,内存随n的增大而增大,但却是效率高且稳定的排序算法。 (2)归并排序每次递归都要...
  • 关于几种排序的时间/空间复杂度和说明 1.选择排序:不稳定,时间复杂度 O(n^2) 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,...
  • 排序-快速排序以及其复杂度的计算

    千次阅读 2020-08-11 00:21:14
    log2(n) 空间复杂度为 O(logn) 而最坏的情况下:需要n-1次调用,每2个数都需要交换,此时退化为冒泡排序 空间复杂度为 O(n) 平均时间复杂度为:O(logn) 时间复杂度:O(nlogn) 由于快速排序用到了递归调用,因此计算其...
  • 归并排序和快排的空间复杂度对比

    千次阅读 2019-04-15 10:17:33
    归并排序和快排都用到了递归调用,但是因为递归函数所处的位置不一样,所以,导致需要的空间复杂度不一样。 其实递归调用占用的空间就是因为一个函数还没有进行完,那么去执行下一个递归的函数,那么上一个还没有...
  • 最烦面试官问,“为什么XX算法的时间复杂度是OO”,今后,不再惧怕这类问题。快速排序分为这么几步:第一步,先做一次partition;partition使用第一个元素t=arr[low]为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 97,249
精华内容 38,899
关键字:

快速排序空间复杂度