精华内容
下载资源
问答
  • 时间复杂度的计算规则: 基本操作,即只有常数项,认为其事件复杂度为O(1) 顺序结构,事件复杂度按 加法 计算 循环结构,事件复杂度按 乘法 进行计算 分支结构, 事件复杂度 取最大值 判断一个算法的效率时,往往只...

    时间复杂度的计算规则:

    1. 基本操作,即只有常数项,认为其事件复杂度为O(1)
    2. 顺序结构,事件复杂度按 加法 计算
    3. 循环结构,事件复杂度按 乘法 进行计算
    4. 分支结构, 事件复杂度 取最大值
    5. 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其他次要项和常数项可以忽略。
    6. 在没有特殊说明时,一般都分析的是最坏事件复杂度。

    时间复杂度从小到大排序:
    O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

    展开全文
  • 线性时间复杂度排序

    千次阅读 2017-04-05 06:47:12
    前言 我的博客之所以叫做“总理同学的暴力编程尝试…”说来话长。在我无数次的暴力编程尝试中,其中有一次就是给500万个整数进行排序,快排还有归并排序显然是卡爆了...因此怀着对“线性时间发杂度排序”的敬仰之情,

    前言

    我的博客之所以叫做“总理同学的暴力编程尝试…”说来话长。在我无数次的暴力编程尝试中,其中有一次就是给500万个整数进行排序,快排还有归并排序显然是卡爆了。快排一直在运转没有头,而归并排序直接就RE程序崩溃了。后来我听说了一种叫做“计数排序”的排序方式,得到了令我十分惊讶的成果,我用了4秒钟生成了500万个随机数,而给这些随机数排序却只用了3秒钟。因此怀着对“线性时间发杂度排序”的敬仰之情,写了这篇文章。


    1.计数排序

    计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。——360百科

    计数排序不同于“快排”和“归并排序”等其他许多排序,其他的排序都是基于“数字之间的比较”而计数排序是基于“对数字的统计”。举一个最显著的例子:“冒泡排序”。冒泡排序的一生都致力于对两个数的比较,然后根据比较的结果对两个数进行交换。

    在计数排序中,我们定义了一个数组“cnt”用来统计要排序的序列中每一个数字出现的次数,cnt[i]表示数字“i”出现的次数,我们先让s数组中的所有元素都初始化成“0”,然后把序列中的每一个数在数组中对应的位置加一,这样就统计出了每个数字在序列中出现的次数。然后从小到大看cnt,cnt[i]=0就说明“i”在原序列中没有出现过;cnt[i]!=0则说明“i”在原序列中出现过,把“cnt[i]”个“i”入队。因为我们令“i”从小到大变化,这就保证了先入队的数一定比后入队的数字要小,这样就实现了对原序列的排序。

    代码如下:

    int cnt[MaxM]={};//统计数组
    void Csort(int* a,int n)//a为原数组,n为原数组的长度(给区间[1,n]进行排序)
    {
        memset(cnt,0,sizeof(cnt));//初始化数组
        for(int i=1;i<=n;i++)
            cnt[a[i]]++;//把a[i]的统计数加一
        int aPos=1;//记录当前的"对尾"
        for(int i=1;i<=1048575;i++)//对每一个可能出现的数字i
            for(int k=1;k<=cnt[i];k++)//向队列中加入cnt[i]个数字i
                a[aPos++]=i;//i入队
    }

    但是上面的那段代码只能实现数字范围为0~MaxM-1的排序,因为cnt数组的大小为MaxM。如果我要实现对数字范围为-100~100的一组数进行排序呢?我们可以在统计时给每个数的身上都加上100,这样原序列的数字范围就变成了0~200,然后用上文同样的方法进行统计。在把cnt数组中数据存回原数组时再把我加上去的“100”减掉,之后再存回数组就可以了。

    int cnt[201]={};//统计-100~100的所有数
    void Csort(int* a,int n)
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)
            cnt[a[i]+100]++;//用cnt[a[i]+100]表示数字a[i]出现的次数
        int aPos=1;
        for(int i=1;i<=1048575;i++)
            for(int k=1;k<=cnt[i];k++)//所以cnt[i]表示的就是数字"i-100"出现的次数
                a[aPos++]=i-100;
    }

    因为计数排序是依靠cnt数组统计每一个数字出现的次数,所以cnt数组的大小要通过数据范围决定。如果数字的范围非常大,那么cnt就需要定义地很大,这样就会浪费很多空间。假设一种极端情况这个顺序列为a[]={0,1,10000000},用“冒泡排序”能够瞬间完成,但用“计数排序”则必须把cnt[0]~cnt[100000000]中的所有位置都看一遍。这也就说明:计数排序更适用于“小范围”的“大量数据”排序。


    2.基数排序

    基数排序(radix sort)属于”分配式排序”(distribution sort),又称”桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些”桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。——360百科

    我保留对上述定义的看法。

    “基数排序”是一种在卡片排序机上实现的算法,在计算机上我们可以把它看做是对计数排序的一种改进算法。相比于计数排序,“计数排序”在时间上稍有逊色,但是在空间上却省了不少。“基数排序”的排序原理就是把所有的数拆成一个一个的十进制位,先把这些数按照个位上的数从小到大排序,再按照十位拍,再按照百位…直到每个数字的位置不再发生改变,排序就完成了。就像这样:

    基数排序的实现

    (请打开脑洞,然后再看下面一段话。)

    简单地证明一下:我们先按照个位对所有数排序,然后再按十位对所有数排序。这时,对于十位相同的数,它们一定是按照个位从下到大排序的。然后我们再取排序它们的百位,一直排序到最大数的最高十进制位,这时所有的数就都得到正确的排序了。

    这样讲可能不是很好理解,那就想象一个情景:假设你在给你的电脑中的一大堆DOC文件进行排序,你可以按照“文件建立时间”,“文件修改时间”,“文件大小”以及“文件名字典序”进行排序。如果我想按照“文件建立时间”,如果“文件建立时间”相同的按照“文件修改时间”排序。但是电脑上只有按照单一一项属性进行排序的功能,我想要实现多项属性进行排序,就得“一个一个”属性进行排序。先按照“文件修改时间”排序,然后再按照“文件建立时间”排序,这样就实现了我想要的功能。这其实就是一个“属性优先级”的问题,优先级低的先排,优先级高的后排,就可以实现。

    而对于一个(带前导零的)整数来说,如果最高位上的数字大的数一定比最高位上小的数要大,而最高位相同的数我们又要通过次高位进行排序…最高位的优先级是最高的,最低位也就是个位的优先级是最低的。所以我们可以把每一个数的每一个十进制位上的数字当成是一种属性,然后先按照低位排序,再按照高位排序,这样就能到我想要的序列了。

    代码如下:

    long long ten[11]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL};
    //表示10的n次方
    #define getNum(base,time) (base/ten[time])%10//得到一个数的当前十进制位
    #define divTime(base,time) (base/ten[time])//求一个数除以10的time次方的结果(用来判断最高十进制位)
    
    int s[10][MaxLen]={};//s[i][k]表示当前十进制位为i的第k个数
    int Rsort(int* a,int n)//a为原数组,n为序列长度
    {
        int maxN=a[1];
        for(int i=2;i<=n;i++)
            maxN=max(maxN,a[i]);//找到最大的数
        int cnt[10]={};//cnt[i]表示当前位为i的数的个数
        for(int i=0;divTime(maxN,i)!=0;i++)//divTime(maxN,i)!=0表示最大的数在当前十进制位以上还有数
        {
            memset(cnt,0,sizeof(cnt));//初始化cnt数组
            for(int j=1;j<=n;j++)
            {
                int numNow=getNum(a[j],i);//numNow当前数的当前数位
                cnt[numNow]++;
                s[numNow][cnt[numNow]]=a[j];//当前数字入放进"桶"中
            }
            int aPos=1;
            for(int j=0;j<10;j++)
                for(int k=1;k<=cnt[j];k++)
                    a[aPos++]=s[j][k];//再把桶中的数取出放回原数组
        }
    }

    [2018.2.2]写了另一个版本的基数排序,这个版本貌似更好一些。后缀数组的倍增算法就是利用了这种排序思想。

    我们用count[i]表示权值小于等于i的所有元素的个数,按当前权值排序后,权值i最后一次出现的位置一定是count[i],同理权值i倒数第二次出现的位置一定是count[i]-1。这样我们可以从后向前扫一遍数组,每次把当前元素(假设它的权值是i)放到count[i]里,然后让count[i]–。得到的结果就是按权值排序后的结果(权值相同的按照原序排序)。

    #include <cstdio>
    #include <cstring>
    #define maxn (1000000+10)
    
    const int tenp[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
    int count[10],tmp[maxn];
    
    int getbit(int x,int bit){
        return x/tenp[bit]%10;
    }
    
    int rsort(int* A,int n){
        for(int bit=0;bit<=9;bit++){
            memset(count,0x00,sizeof(count));
            for(int i=1;i<=n;i++) count[getbit(A[i],bit)]++;
            for(int i=1;i<=9;i++) count[i]+=count[i-1];
            for(int i=n;i>=1;i--) tmp[count[getbit(A[i],bit)]--]=A[i];
            for(int i=1;i<=n;i++) A[i]=tmp[i];
        }
    }
    
    int a[maxn];
    
    int main(){
        int n; scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        rsort(a,n);
        for(int i=1;i<=n;i++) printf("%d ",a[i]);
        return 0;
    }

    [2018.2.2]补记结束。

    这就是基数排序的实现。


    3.后记

    计数排序是我见过最快的算法,当然也是一个拿空间换时间的“模范”,但是用的时候一定要谨慎。而基数排序对空间的要求就没有那么大了,只需要10*MaxLen的空间就可以保证不会“非法调用”。基数排序的思想还被应用到了后缀数组的计算中,非常的抽象。对基数排序没有深刻理解的同学可能在学习后缀数组是就会面临非常大的困难。

    展开全文
  • 一些常用的时间复杂度排序: O(lgn) √n) 这里,我们默认lg始终是以2为底,符号“^”表示乘方的意思

    一些常用的时间复杂度排序:

    O(lgn) < O(√n) < O(n) < O(nlgn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

    这里,我们默认lg始终是以2为底,符号“^”表示乘方的意思

    展开全文
  • python 常见时间复杂度

    2020-04-27 16:55:47
    所谓的时间复杂度就是基本运算数量的总和,在分析算法时,存在三种可能:1.最优时间复杂度:算法完成工作最少需要多少基本操作; 2.最坏时间复杂度:算法完成工作最多需要多少基本操作; 3.平均时间复杂度:算法完成...

    所谓的时间复杂度就是基本运算数量的总和,在分析算法时,存在三种可能:1.最优时间复杂度:算法完成工作最少需要多少基本操作;
    2.最坏时间复杂度:算法完成工作最多需要多少基本操作;
    3.平均时间复杂度:算法完成工作平均需要多少基本操作;
    我们主要关注的是最坏时间复杂度

    时间复杂度的几条基本计算规则:

    基本操作 赋值,打印等此类操作,时间复杂度为O(1)
    顺序结构 时间复杂度相加
    循环结构 时间复杂度相乘
    分支结构 选择分支中最大的时间复杂度

    注意:判断一个算法的效率时,往往关注操作数量的最高次项,其它次要项和常数项可忽略,此外,在没有特殊说明时,往往研究最坏时间复杂度。

    常见时间复杂度:

    执行次数 时间复杂度 名称 举例
    21 O(1) 常数阶 赋值、打印等
    2*n+10 O(n) 线性阶 顺序查找
    n^2+2*n+10 O(n^2) 平方阶 两重循环
    n^3+2*n+1 O(n^3) 立方阶 三重循环
    5*log(n)+n^2 O(log(n)) 对数阶 二分查找
    n*log(n)+n^2 O(n*log(n)) 对数线性阶 堆排序法
    2^n O(2^n) 指数阶 斐波那契数列
    3*n^n+1 O(n^n) n次方阶 n重循环
    n! O(n!) 阶乘 旅行商

    常见时间复杂度按所消耗的时间从小到大排序:
    当n>=65时,O(n!)>O(n^n)
    在这里插入图片描述

    import numpy as np
    import math
    import matplotlib.pyplot as plt
    
    fig = plt.figure()
    ax = fig.add_subplot()
    ax.set(xlim=[0,65], ylim=[0,100], title='Figure',
           ylabel='O(n)', xlabel='n')
    x,x1=[],[]
    y,y1,y2,y3,y4,y5,y6,y7,y8=[],[],[],[],[],[],[],[],[]
    a=np.linspace(0.1,65,650)
    def f(x):
        y=1
        return y
    def f1(x):
        y=x
        return y
    def f2(x):
        y=x**2
        return y
    def f3(x):
        y=x**3
        return y
    def f4(x):
        y=math.log(x)
        return y
    def f5(x):
        y=x*math.log(x)
        return y
    def f6(x):
        y=2**x
        return y
    def f7(x):
        y=math.factorial(x)
        return y
    def f8(x):
        y=x**x
        return y
    for i in a:
        x.append(i)
        y.append(f(i))
        y1.append(f1(i))
        y2.append(f2(i))
        y3.append(f3(i))
        y4.append(f4(i))
        y5.append(f5(i))
        y6.append(f6(i))
        y8.append(f8(i))
        if i%1==0:
            x1.append(i)
            y7.append(f7(i))
            
    ax.plot(x,y, label='1')
    ax.plot(x,y1, label='n')
    ax.plot(x,y2, label='n^2')
    ax.plot(x,y3, label='n^3')
    ax.plot(x,y4, label='log(n)')
    ax.plot(x,y5, label='nlog(n)')
    ax.plot(x,y6, label='2^n')
    ax.plot(x1,y7, label='n!')
    ax.plot(x,y8, label='n^n')
    ax.legend()
    plt.show()
    

    在这里插入图片描述
    当n<65时,O(n!)<O(n^n)
    在这里插入图片描述
    在这里插入图片描述
    注意:画函数曲线的时候,一定要注意函数返回的值的格式,比如n 的阶乘是对整数的计算,log(n) 则是对大于0的数据进行计算,否则会出错。本篇文章已经避开这些问题。
    感兴趣的小伙伴可以测试一下。

    展开全文
  • 常用时间复杂度排序

    2015-01-27 09:04:40
    耗费的时间从小到大依次是: O(1)
  • 线性时间复杂度排序算法

    千次阅读 2010-07-20 11:22:00
    采用比较的排序算法至少具有O(nlgn)的时间复杂度。而对于整数序列来说,在满足一定的条件下,可以达到O(n)的时间复杂度主要有计数排序和基数排序,下面分别介绍这两种算法。一、计数排序(Counting Sort)问题:对于一...
  • 常见时间复杂度一览表

    千次阅读 2019-05-14 07:41:06
    常见函数的增长率: 排序算法的时间复杂性: 选择排序 O(n^2) O(n^2) O(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 归并...
  • 排序算法 最佳时间复杂度 平均时间复杂度 最坏时间复杂度
  • 排序算法分类 排序算法比较表格 ... 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定 冒泡排序 O(n2) O(n2) O(1) 是 选择排序 O(n2) O(n2) O(1) ...
  • 算法时间复杂度大小排序
  • 常见排序算法时间复杂度

    千次阅读 2020-08-25 22:26:53
    冒泡排序:最差,平均都是O(n^2),最好是O(n) 插入排序:最差,平均都是O(n^2),最好是O(n) 归并排序:最差,平均,最好都是O(nlogn) 选择排序:最差,平均都是O(n^2) 希尔排序:O(nlogn) 堆排序 :最差,平均...
  • 插入排序时间复杂度: 最好: 所有元素已经排好序,只需遍历一遍,无需交换位置; 最坏: 所有元素逆序排列,遍历一次需要比较的元素个数每次+1,所以时间复杂度是O(n^2); 平均时间复杂度就是O(n^2)喽。 2、 ...
  • 图解常见排序方法的时间复杂度

    千次阅读 2018-10-08 22:09:12
    O(n2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。比如冒泡排序、递归算法,就是典型的O(n2)的算法,对n个数排序,需要扫描n×n次。 O( login)当数据增大n倍时,耗时增大logn倍(这里...
  • 常见时间复杂度 执行次数函数举例 阶 非正式术语 12 O(1) 常数阶 2n+3 O(n) 线性阶 3n2+2n+1 O(n2) 平方阶 5log2n+20 O(logn) 对数阶 2n+3nlog2n+19 O(nlogn) nlogn...
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 2018-12-31 14:09:13
    排序算法分类  排序大的分类可以分为两种:内排序和外排序。  放在内存的称为内排序,...排序算法的时间复杂度和空间复杂度 排序算法 平均时间复杂度 最坏时间复杂度 ...
  • 1、归并排序可以通过手摇算法将空间复杂度降到O(1),但是时间复杂度会提高。 2、 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数 二、 辅助记忆 1、时间复杂度记忆 冒泡、选择、直接 排序需要两个...
  • 归并排序空间复杂度为O(n) 快速排序空间复杂度为O(logn~n):因为快速排序是递归的,需要一个栈存放相应的数据,最大递归调用次数与递归树的深度有关 堆排序空间复杂度在非递归情况下是O(1),递归情况下就是O(logn)
  • 快速排序时间复杂度

    千次阅读 2019-09-24 17:44:54
    快速排序时间复杂度是如何计算的快速排序简单回顾时间复杂度 快速排序简单回顾 首先选定一个元素为“轴”,轴元素与其他元素依次比较并根据比较的结果交换位置,最后处于一个合适的位置时称为一次划分。划分后的...
  • 理解时间复杂度,插入排序,冒泡排序,选择排序 什么是时间复杂度 就是近似于约等于算法总的执行的次数; 说白了时间复杂度就是近似约等于算法中常数操作的次数; 时间复杂度使用O(n)(可以读big O n)来表示 在一个...
  • 时间复杂度为o(n)的排序算法:不是基于比较的排序算法;思想来自于桶排序!比如:计数排序和基数排序。其中基数排序中是分别基于个位、十位以及等等更高的位将数据放入桶中,然后再将数据倒出来! 八个经典排序...
  • 归并排序时间复杂度分析

    万次阅读 多人点赞 2019-03-19 18:04:57
    归并排序时间复杂度分析归并排序工作原理时间复杂度计算如何插入一段漂亮的代码片KaTeX数学公式 归并排序 归并排序也叫(Merge sort)。 工作原理 将给定的数组一份为二 对两部分数组再使用归并排序使其有序 最后再...
  • 排序算法经过长时间演变,大体可以分为两类:内排序和外排序。在排序过程中,全部记录存放在内存,则成为内排序;如果排序过程中需要使用外存,则... 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) ...
  • 1.时间复杂度分为最优时间复杂度、最坏时间复杂度、平均时间复杂度。 2.由于最优时间复杂度和平均复杂度只能解决部分的情况,因此通常以最坏时间复杂度为评判标准。 3.时间复杂度的基本计算原则: 常数项视为常数 ...
  • 各种排序算法时间复杂度 各种排序算法比较 各种常用排序算法 类别 排序方法 时间复杂度 空间复杂度 稳定性 复杂性 特点 ...
  • 不多说,先给图: 接触的排序算法有冒泡,选择,冒泡和选择差不多,不过冒泡是稳定的,而选择是不稳定的。...4.堆排序是一种继续完全二叉树制造大顶堆或小顶堆进行的排序算法,见堆排序算法 关于...
  • 《忆排序 面试我最强》 作者:马士兵 选炮插, 快归堆希统计姬, n 方 n老 n一三, ...下列排序算法中,最坏时间复杂度是 O(n log(n)) 的是? 快速排序 插入排序 归并排序(*) 堆排序(*) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 283,806
精华内容 113,522
关键字:

常见的时间复杂度排序