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

    千次阅读 2020-09-21 20:57:09
    快速排序的时间主要耗费在划分操作上,对长度为n的区间进行划分,共需n-1次关键字的比较,时间复杂度为O(n)。 对n个元素进行快速排序的过程构成一棵递归树,在这样的递归树中,每一层最多对n个元素进行划分,所花...

            快速排序的时间主要耗费在划分操作上,对长度为n的区间进行划分,共需n-1次关键字的比较,时间复杂度为O(n)。

            对n个元素进行快速排序的过程构成一棵递归树,在这样的递归树中,每一层最多对n个元素进行划分,所花的时间为O(n)。当初始排序数据随机分布,使每次分成的两个子区间中的元素个数大致相等时,递归树高度为log2n,快速排序呈现最好情况,即最好情况下的时间复杂度为O(nlog2n)。快速排序算法的平均时间复杂度也是O(nlog2n)。所以快速排序是一种高效的算法。

    展开全文
  • 两个重要的排序算法的时间复杂度比较。所用的代码比较简陋,使用控制台。
  • 快速排序 时间复杂度计算

    千次阅读 2019-09-26 02:39:47
    https://www.cnblogs.com/fengty90/p/3768827.html 转载于:https://www.cnblogs.com/xxlm/p/11532886.html

    https://www.cnblogs.com/fengty90/p/3768827.html

     

     

    转载于:https://www.cnblogs.com/xxlm/p/11532886.html

    展开全文
  • 巧解快速排序时间复杂度

    万次阅读 2018-04-24 18:35:35
    快速排序时间复杂度递归算法的时间复杂度=递归次数*每次递归遍历的次数我们来看一下快速排序算法的时间复杂度需要怎么来算呢? 代码实现://左右指针法 不断缩放 //思路 begin 找大的 end 找小的 //还要注意 如果...

    快速排序时间复杂度

    递归算法的时间复杂度=递归次数*每次递归遍历的次数

    我们来看一下快速排序算法的时间复杂度需要怎么来算呢?
    代码实现:

    //左右指针法  不断缩放  
    //思路 begin 找大的  end 找小的  
    //还要注意  如果是选endkeybegin先走 否则end先走  
    //当选择end时候  因为当最后一次 endbegin差一个距离时候 如果先走end那会导致  
    //把实际较小的没有交换 因为换之前 大小是左边小右边大 如果end先走 等于把begin所在的较小的换到最后去  
    int PartSort1(int* a, int begin, int end)  
    {  
        int& key = a[end];  
        while (begin < end)  
        {  
    
            //begin找大  
            while (begin < end&&a[begin] <= key)//这里注意的是<=  小心有重复数字  
                begin++;  
            //end找小  
            while (begin < end&&a[end] >= key)  
                end--;  
            if(begin<end)  
                swap(a[begin], a[end]);  
        }  
    
        //最好出来begin位置 一定是大于key的  
        swap(a[begin], key);  
        return begin;  
    }  
    
    void QuickSort(int* a, int begin,int end)  
    {  
        if (begin >= end)  
            return;  
        else  
        {  
            int div = PartSort1(a, begin, end);  
            QuickSort(a, begin, div - 1);  
            QuickSort(a, div+1, end);  
        }  
    }  
    
    

    快速排序我们可以近似的想成一个完全二叉树
    这里写图片描述

    一个数组的容量是N,第一层递归遍历的次数是N,因为数组里每个数字都需要和key比较,那么接下来遍历分出来的两个区间,总的遍历次数还会是近似是N,以此类推,直到分为最后一个,也就是说树的高度是lgn,也就是递归次数,所以时间复杂度是N*lgN.

    进阶:

    问题:
    有100万个数字,找出第10万个大的,这个问题,首先不是大数据问题,内存是可以放下的,这是快速排序的变形问题,第10万个大的其实是让我们找div=10万,(快速排序返回的div,其实就是下标,也就是数字在数组的准确序号[序号指的是第几个大])下面给出实现代码

    int PartSort1(int* a, int begin, int end)  
    {  
        int& key = a[end];  
        while (begin < end)  
        {  
    
            //begin找大  
            while (begin < end&&a[begin] <= key)//这里注意的是<=  小心有重复数字  
                begin++;  
            //end找小  
            while (begin < end&&a[end] >= key)  
                end--;  
            if(begin<end)  
                swap(a[begin], a[end]);  
        }  
    
        //最好出来begin位置 一定是大于key的  
        swap(a[begin], key);  
        return begin;  
    }  
    
    void QuickSort(int* a, int begin,int end)  
    {  
        if (begin >= end)  
            return;  
        else  
        {  
            int div = PartSort1(a, begin, end);  
            if(div==100000)
            return a[div]
            else if(div>100000)
            QuickSort(a, begin, div - 1);  
            else
            QuickSort(a, div+1, end);  
        }  
    }  

    那这个代码的时间复杂度是多少呢?
    这里写图片描述
    我们可以用数形结合的方法,这个算法相当于一直走的是树的左枝,其余的都没有走,这其实就相当于变成了单链表,那遍历单链表的时间复杂度其实就是O(n),同理这个代码的时间复杂度也是O(n),

    通过这个题我们可以看出数形结合有时候非常的清晰直观

    展开全文
  • 最近研究随机算法,发现快速排序作为一种入门算法,分析其时间复杂度还是很有趣的。 首先,证明其最坏时间复杂度为 是很容易的。证明其平均时间复杂度的期望是也有很多不同方式。这里介绍两种简单的方式。 需要...

    最近研究随机算法,发现快速排序作为一种入门算法,分析其时间复杂度还是很有趣的。

    首先,证明其最坏时间复杂度为O(n^2) 是很容易的。证明其平均时间复杂度的期望是O(n\lg n)也有很多不同方式。这里介绍两种简单的方式。

    需要说明的是,这里的快排是随机化的排序算法。因此对于任意输入,其期望的时间复杂度都是相同的。

    首先是比较容易的方式。我们假设算法的输入是有序序列<a1,a2,a3,a4...,an>的一个排列。也就是说,我们将这个排好序的序列打乱顺序之后作为输入。算法的时间复杂度就是需要进行比较的次数。注意到一下结论:

    1. 任意两个元素至多只可能比较一次。因为比较操作是在partition时候进行的。每次比较,就说明其中一个数字是被选择作为pivot。所以,在之后的排序中,都不会再涉及pivot。
    2. 两个元素会被排序的可能性与两个元素之间包含的元素个数有关。为了解释这一点,我举两个例子。
      1. 首先,考虑<a1,a2>这两个最小的元素。它们之间会进行比较的概率是1。为什么呢。因为每次选取pivot的时候,如果没有选中<a1,a2>这两个元素中的某个的时候,那它们一定会被扔到pivot的同一侧。这样,这两个元素在同一个区间里面,接下来仍然有可能被比较。如果选中了<a1,a2>,那么由于它们在同一个区间里面,因此它们一定会比较。
      2. 其次,考虑a1和an。也就是最小的元素和最大的元素。它们比较的概率是2/n。因为考虑第一次选取pivot的时候。如果选中了a1和an这两个元素中的某一个,那么它们一定会比较。这样的概率是2/n。而第一次没有选取a1和an其中的某一个时,pivot一定会将这两个元素分别放在不同的递归区间里面,这样它们就不可能再被比较了。

    通过第二点,我们很容易想到这个结论:<ai、aj>这两个元素被比较的概率是2/(j-i+1)。为什么呢。因为排好序的序列中考虑这么一段数字<ai,ai+1,...,aj>。当选取pivot不在这个区间里面时,这段数字依然在同一个区间,也就是说接下来它们仍然有可能被比较。而当某次选取pivot在这段数字里面的时候。如果没有选<ai、aj>,那么接下来这两个数字就被放到不同区间了,不会被比较,概率是(j-i+1-2)/(j-i+1)。而选中其中一个元素,它们一定被比较,概率就是2/(j-i+1)。

    所以,得到这个结论之后,一切就很简单了。用基本概率论的知识就行了。定义一个随机变量Xij,为1就说明ai和aj进行了比较,否则为0。那我们要求的就是\sum X_{ij}。由Linearity of expectation,E[\sum X_{ij}]=\sum E[X_{ij}]。Xij是01变量,期望就是1/j-i+1.

     

    因此期望的时间复杂度就是 \sum_{i=1}^{n-1} \sum_{j=i+1}^n 1/(j-i+1) = \sum_{i=1}^{n-1} \sum_{h=1}^{n-i} 1/h。再根据调和级数就知道,时间复杂度为O(nlog n)。

     

    其实还有一种更简单的方法,从概率模型出发。以后再说吧。

     

    此外,还可以证明with high probabilty,时间复杂度不会超过 c*nlog n。这也是类似的方法。以后有机会再说。

    展开全文
  • 快速排序的基本思想:  通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对这两部分继续进行排序,直到整个序列有序。  先看一下这幅图: 把整个...
  • 快速排序时间复杂度

    千次阅读 2019-09-24 17:44:54
    快速排序时间复杂度是如何计算的快速排序简单回顾时间复杂度 快速排序简单回顾 首先选定一个元素为“轴”,轴元素与其他元素依次比较并根据比较的结果交换位置,最后处于一个合适的位置时称为一次划分。划分后的...
  • 快速排序时间复杂度分析

    千次阅读 多人点赞 2021-04-03 21:39:33
    快速排序时间复杂度分析 先说结论: 最坏情况:O(N2)O(N^{2})O(N2) 最好情况和平均情况:$ O(NlogN)$ 下面开始分析。 假设一个序列共有 N 个元素,基本的快速排序的关系式是: T(N)=T(i)+T(N−i−1)+cNT(N) = T(i)...
  • C/C++中快速排序的时间空间复杂度分析 1.什么是快速排序 我理解的是,快速排序用的是分治法,运用的递归的算法,先挑选一个基准值,小于...每种排序方式都会有最优的时间复杂度以及最差的时间复杂度,就像快速排序,你
  • 快速排序时间复杂度

    2013-10-14 17:44:38
    快排是我们比较熟悉的一种排序方式,以前我们知道,快排时间复杂度最佳时0(nlogn),最差是O(n2),那么究竟是为什么呢?  这里我们并不做多严格的数学验证,我们知道,对于划分成子问题求解的问题,我们可以用下面的...
  • 快速排序思想: 快排的核心是递归。以从小到大排序为例,把第一个值作为基准值,先从最右边进行比较,若比基准值大,那么右边的指针左移一位,如果比基准值大,那么交换基准值和当前位置的值,改变比较方向,开始从...
  • 排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
  • 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,...
  • 快速排序时间性能取决于快速排序递归的深度, 可以用递归树来描述递归算法的执行情况。 如图9‐9‐7所示,它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50,正好是待...
  • 快速排序时间复杂度数学证明

    千次阅读 2014-07-06 16:09:17
    算法针对到的是递归的快速排序算法
  • https://blog.csdn.net/c1sdn19/article/details/88408418 https://blog.csdn.net/wenfei11471/article/details/80711882排序——选择排序、冒泡排序和快速排序比较
  • 快速排序时间复杂度为O(n×log(n))的证明 2014年05月22日 11:17:52 oohaha_123 阅读数:2789 标签: 快速排序算法导论复杂度证明 更多 个人分类: 资料收集整理数据结构/算法 快速排序时间复杂度为O(n...
  • #include <iostream> #include <vector> using namespace std; void show(vector<int>& a) { for (int i = 0; i <= a.size() - 1; i ++) { cout <...int quick_sort.
  • 八大排序算法一、直接插入1.基本思路在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。2.代码...
  • 快速排序 及其时间复杂度和空间复杂度

    万次阅读 多人点赞 2018-07-16 14:33:00
    快速排序是排序算法中效率相对较高的,但使用的人却是比较少,大家一般信手拈来的排序算法就是冒泡排序。因为冒泡排序主观,容易理解,而快速排序使用到了递归,大家可能就有点不知所措了。算法分析 快速排序由C. A...
  • 快速排序的思想是在数组[p,r]中选择一个分区点q,将数组一分为2,同时将小于分区点的数值的放到分区点左侧[p,q-1],大于分区点的数值的放到分区点右侧[q+1,r],重复这个过程。 快速排序也是用到了分治思想和递归实现...
  • 排序算法之 冒泡排序及性能优化(时间复杂度+空间复杂度分析) 排序算法之 简单选择排序及时间复杂度分析 排序算法之 直接插入排序及时间复杂度分析 排序算法之 希尔排序及时间复杂度分析 快速排序 科普: 快速排序...
  •  快速排序是排序算法中效率相对较高的,但使用的人却是比较少,大家一般信手拈来的排序算法就是冒泡排序。因为冒泡排序主观,容易理解,而快速排序使用到了递归,大家可能就有点不知所措了。 算法分析  快速...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 120,043
精华内容 48,017
关键字:

快速排序时间复杂度