精华内容
下载资源
问答
  • 快排时间复杂度

    2020-09-04 09:47:20
  • 转载:快排时间复杂度分析

    千次阅读 2017-09-23 09:44:40
    快排时间复杂度分析转自:http://blog.csdn.net/hn_gsf/article/details/52249621我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。最好情况如...

    快排时间复杂度分析

    转自:http://blog.csdn.net/hn_gsf/article/details/52249621

    我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。

    最好情况

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

    这里写图片描述

    在最优情况下,Partition每次都划分得很均匀,如果排序n个关键字,其递归树的深度就为.log2n.+1(.x.表示不大于x的最大整数),即仅需递归log2n次,需要时间为T(n)。第一次Partiation需要对整个数组扫描一遍,做n次比较。然后,获得的枢轴将数组一分为二,那么各自还需要T(n/2)的时间(注意是最好情况,所以平分两半)。于是不断地划分下去,我们就有了下面的不等式推断。

    T(n)≤2T(n/2) +n,T1)=0  
    T(n)≤2(2T(n/4)+n/2) +n=4T(n/4)+2n  
    T(n)≤4(2T(n/8)+n/4) +2n=8T(n/8)+3n  
    ……  
    T(n)≤nT(1)+(log2n)×n= O(nlogn) 

    也就是说,在最优的情况下,快速排序算法的时间复杂度为O(nlogn)。


    最坏情况

    在最坏的情况下,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树。此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为
    这里写图片描述
    最终其时间复杂度为O(n2)。


    平均情况

    平均的情况,设枢轴的关键字应该在第k的位置(1≤k≤n),那么:
    这里写图片描述
    由数学归纳法可证明,其数量级为O(nlogn)。


    空间复杂度

    就空间复杂度来说,主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2n,其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归调用,其空间复杂度为O(n),平均情况,空间复杂度也为O(logn)。

    可惜的是,由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。

    参考:http://book.51cto.com/art/201108/287089.htm

    展开全文
  • https://www.cnblogs.com/HDK2016/p/6876313.html

    https://www.cnblogs.com/HDK2016/p/6876313.html

    展开全文
  • 快排时间复杂度详细解释

    万次阅读 2018-11-09 23:56:16
    2 快排在最糟糕得情况下时间复杂度是O(n²),平均的复杂度是O(nlogn), 这里的n和logn, 分别代表了调用栈的高度,和完成每层的时间,在a取 数组的第一项时候,是最糟的情况,完成每层需要的时间是n,栈的高 读是n...

    快速排序和大O表示法

    1 快速排序递归版
    def quick_sort(arr):
    if len(arr)<2:
    return arr ------------------这是基线条件
    else:
    a = arr[0]
    smaller = [i for i in arr[1:] if i < a]
    bigger = [i for i in arr[1:] if i > a]
    return quick_sort(smalller) + [a] + quick_sort(bigger)

    2 快排在最糟糕得情况下时间复杂度是O(n²),平均的复杂度是O(nlogn),
    这里的n和logn, 分别代表了调用栈的高度,和完成每层的时间,在a取
    数组的第一项时候,是最糟的情况,完成每层需要的时间是n,栈的高
    读是n,时间复杂度就是n²,当取中间的值得时候,完成每层的时间是
    n,但是调用栈的高度变成了logn,所以这个时候时间复杂度是nlogn

    3 选择排序的时间复杂度是O(n²)

    展开全文
  • 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 复杂性 插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单 冒泡排序 O(n2) O(n2) O(n) O(1) 不稳定 较复杂 归并排序 O(nlog2n) O...
  • 快排时间复杂度简单证明

    万次阅读 2018-03-29 09:44:49
    快排这里不再赘述 主要是时间复杂度 先写一下快排代码void quick_sort(int a[], int start, int end) { int val = a[start]; int s = start; int e = end; while(s &lt; e) { while(s &lt; e &amp;...
  • 快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。如图9‐9‐7所示,它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50,正好是待排序...
  • 直观证明 1.划分点按照1:9划分时,用递归树分析时间复杂度: ...2.在平均情况下,好的划分(常数比例划分)和坏的划分(1:n-1)是平均出现在划分树上的,当好、差划分交替在各层时,快排的运行时间就如...
  • 在用快排求解逆序数前,我先考虑了这个问题,1:归并和快排时间复杂度都是nlog(n),为什么不用归并? 我认为应该是由于快排在每次合并时都有用到临时数组,然后每次还需要把临时数组重新copy到原数组中 ,增加了...
  • 一般常用的方法是,对每一个数列都取一次中位数(O(n)),这样总体的快排时间复杂度仍为O(nlogn)。 更为简化的方法是,取头、中、尾的中位数(O(1))作为pivot 另一个问题: 如果有元素等于pivot,是换还是不换...
  • 快排最坏时间复杂度

    千次阅读 2019-08-27 09:52:25
    最好的情况:每次选的pivot几乎能把数据均分成两半,这样递归树的深度就是logN,这样快排时间复杂度为O(NlogN) 最坏的情况:每次找的pivot将数组分成两部分,其中有一部分是空,这样递归树就变成了一棵倾斜的树。...
  • 前端时间去面试,碰到问题,快排的链表实现和时间复杂度分析,非常基础,但是当时完全没想到社招面试会涉及到这么基础的东西,回答的非常不完美,现在总结,以致后人: 节点定义: struct Node {  int value; //...
  • 时间复杂度及空间复杂度直白理解/快排/冒泡 常常在算法类的文章里看到时间复杂度,空间复杂度的名词,但是对其中的意思不是很清楚,但是大概是知道,复杂度代表了一个算法的运行效率,复杂度越大说明这个算法运行效率越...
  • 本文以快速排序为例,推导了快排时间复杂度nlogn是如何得来的,其它算法与其类似。 对数据Data = { x1, x2... xn }: T(n)是QuickSort(n)消耗的时间; P(n)是Partition(n)消耗的时间; (注:Partition...
  • 快排的三个步骤 1 找到序列中用于划分序列的元素 2. 用元素划分序列 3. 对划分后的两个序列重复1,2两个步骤指导序列无法再划分 T(n) = 2*T(n/2) + n (表示将长度为n的序列划分为两个子序列,每个子序列需要T(n/...
  • 快排和归并时间复杂度为何是O(nlogn)

    千次阅读 2019-06-02 23:25:15
    快排是从所给的要排序的数中先随机抽出一个数(一般选择第一个数作为基数)。然后遍历输入的数(将每个数和抽出的数比较,比它小的放左边,...最终快排时间复杂度是nlogn(它是不稳定算法) 归并排序:从递归的角度来...
  • 二、希尔排序 先将整个待元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次...
  • ...接下来通过这种方法来计算快排时间复杂度: 递推公式: 主定理: 所以a=2,b=2, ,对应第二种情况,所以 是不是很简单…… 后面再写平均和最差吧,或者可以看这篇博文 ...
  • title: TopK问题用快排和堆排的复杂度分别是多少? categories: 算法 tags: TopK 关于TopK问题 TopK问题就是在一堆数据里面找到前 K 大(当然也可以是前 K 小)的数 常规方法,完全排序 先完全排序后取topK,这种...
  • 快排代码实现和时间复杂度计算

    千次阅读 2020-05-24 15:12:04
    } 时间复杂度问题: 在这里,我们为T(N)设置一个递归式,也就是排序大小为n的时间复杂度。 T(n)=O(n)+2T(n2)T(n)=O(n)+2T(\frac{n}{2})T(n)=O(n)+2T(2n​) O(n)是一个单独的排序调用牵涉了O(n)的工作量。 2T(n2)...
  • 快速排序(Quicksort)是对冒泡排序的一种改进。...所以随机快排时间复杂度就是一个概率事件了,它的数学期望是N logN,算法上比普通快排更优。 理解原理后动手多敲几遍,多跟几遍debug才能彻底搞懂哦!
  • 快排是一种最常用的排序算法,因为其平均的时间复杂度是nlgn,并且其中的常数因子比较小。一.快速排序 快排和合并排序一样都是基于分治的排序算法;快排的分治如下: 分解:对区间A[p,r]进行分解,返回q,使得A[p–q-...
  • 实现一个快排 function quickSort(arr) { if (arr.length < 2) { return arr; } const cur = arr[arr.length - 1]; const left = arr.filter((v, i) => v <= p && i !== arr.length - 1); ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 68,676
精华内容 27,470
关键字:

快排时间复杂度