精华内容
下载资源
问答
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。 目录 时间复杂度 1.时间频度 2.计算方法 3.分类 空间复杂度 算法的时间...

    文章地址:http://lzw.me/a/algorithm-complexity.html

    算法复杂度分为时间复杂度和空间复杂度。
    时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。

    目录

    时间复杂度 

    1.时间频度 

    2.计算方法

    3.分类

    空间复杂度

    算法的时间复杂度(计算实例) 

    算法复杂度的渐近表示法

    一  大O记号

    二  Ω记号

    三  Θ记号

    四  小o记号

    五  例子

    常见排序算法时空复杂度


    时间复杂度 

    1.时间频度 

      一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

    2.计算方法

      1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))
      分析:随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。

      2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))

      例:算法:

      for(i=1;i<=n;++i)
      {
      for(j=1;j<=n;++j)
      {
      c[ i ][ j ]=0; //该步骤属于基本操作执行次数:n的平方 次
      for(k=1;k<=n;++k)
      c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n的三次方 次
      }
      }

      则有 T(n)= n的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
      则有f(n)= n的三次方,然后根据T(n)/f(n)求极限可得到常数c
      则该算法的 时间复杂度:T(n)=O(n的三次方)

    3.分类

      按数量级递增排列,常见的时间复杂度有:
      常数阶O(1),对数阶O(log2n),线性阶O(n),
      线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),…,
      k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

    空间复杂度

      与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:
      S(n)=O(f(n))
      我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。
     

    算法的时间复杂度(计算实例) 

    算法的时间复杂度
    定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

    当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。

    我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。

    此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。

    “大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。

    这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。

    O(1)

    Temp=i;i=j;j=temp;

    以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

    O(n^2)

    2.1. 交换i和j的内容

    sum=0; (一次)
    for(i=1;i<=n;i++) (n次)
    for(j=1;j<=n;j++) (n^2次)
    sum++; (n^2次)

    解:T(n)=2n^2+n+1 =O(n^2)

    2.2.

    for (i=1;i<n;i++)
    {
    y=y+1; ① 
    for (j=0;j<=(2*n);j++) 
    x++; ② 
    }

    解:语句1的频度是n-1
    语句2的频度是(n-1)*(2n+1)=2n^2-n-1
    f(n)=2n^2-n-1+(n-1)=2n^2-2
    该程序的时间复杂度T(n)=O(n^2).

    O(n) 

    2.3.
    a=0;
    b=1; ①
    for (i=1;i<=n;i++) ②

    s=a+b;    ③
    b=a;     ④ 
    a=s;     ⑤
    }

    解:语句1的频度:2, 
    语句2的频度: n, 
    语句3的频度: n-1, 
    语句4的频度:n-1, 
    语句5的频度:n-1, 
    T(n)=2+n+3(n-1)=4n-1=O(n).

    O(log2n )

    2.4.

    i=1; ①
    while (i<=n)
    i=i*2; ②

    解: 语句1的频度是1, 
    设语句2的频度是f(n), 则:2^f(n)<=n;f(n)<=log2n 
    取最大值f(n)= log2n,
    T(n)=O(log2n )

    O(n^3)

    2.5.

    for(i=0;i<n;i++)

    for(j=0;j<i;j++) 
    {
    for(k=0;k<j;k++)
    x=x+2; 
    }
    }

    解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,…,m-1 , 所以这里最内循环共进行了0+1+…+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+…+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).
     

    我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n^2),但期望时间是 O(nlogn)。通过每次都仔细地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。

    下面是一些常用的记法:

    访问数组中的元素是常数时间操作,或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。

    指数时间算法通常来源于需要求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。

    算法复杂度的渐近表示法

    一个算法的时间复杂度,指算法运行的时间。

    假设数据输入规模是n,算法的复杂度可以表示为f(n)的函数

    一  大O记号

    假设f(n)和g(n)的定义域是非负整数,存在两个正整数c和n0,使得n>n0的时候,f(n)≤c*g(n),则f(n)=O(g(n))。可见O(g(n))可以表示算法运行时间的上界。O(g(n))表示的函数集合的函数是阶数不超过g(n)的函数。

    例如:f(n)=2*n+2=O(n)

    证明:当n>3的时候,2*n +2<3n,所以可选n0=3,c=3,则n>n0的时候,f(n)<c*(n),所以f(n)=O(n)。

    现在再证明f(n)=2*n+2=O(n^2)

    证明:当n>2的时候,2*n+2<2*n^2,所以可选n0=2,c=2,则n>n0的时候,f(n)<c*(n^2),所以f(n)=O(n^2)。

    同理可证f(n)=O(n^a),a>1

    二  Ω记号

    Ω记号与大O记号相反,他可以表示算法运行时间的下界。Ω(g(n))表示的函数集合的函数是所有阶数超过g(n)的函数。

    例如:f(n)=2*n^2+3*n+2=Ω(n^2)

    证明:当n>4的时候,2*n^2+3*n+2>n^2,所以可选n0=4,c=1,则n>n0的时候,f(n)>c*(n^2),所以f(n)=Ω(n^2)。

    同理可证f(n)=Ω(n),f(n)=Ω(1)

    三  Θ记号

    Θ记号介于大O记号和Ω记号之间。他表示,存在正常数c1,c2,n0,当n>n0的时候,c1*g(n)≤f(n)≤c2*g(n),则f(n)=Θ(g(n))。他表示所有阶数与g(n)相同的函数集合。

    四  小o记号

    f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)≠Ω(g(n))。也就是说小o记号可以表示时间复杂度的上界,但是一定不等于下界。

    五  例子

    假设f(n)=2n^2+3n+5,

    则f(n)=O(n^2)或者f(n) = O(n^3)或者f(n)=O(n^4)或者……

    f(n)=Ω(n^2)或者f(n)=Ω(n)或者f(n)=Ω(1)

    f(n)=Θ(n^2)

    f(n) = o(n^3)或者f(n)=o(n^4)或者f(n)=o(n^5)或者……

    注:n^2表示n的平方,以此类推。

    常见排序算法时空复杂度

     

     

    排序法

    最差时间分析平均时间复杂度稳定度空间复杂度
    冒泡排序O(n2)O(n2)稳定O(1)
    快速排序O(n2)O(n*log2n)不稳定O(log2n)~O(n)
    选择排序O(n2)O(n2)稳定O(1)
    二叉树排序O(n2)O(n*log2n)不一顶O(n)

    插入排序

    O(n2)O(n2)稳定O(1)
    堆排序O(n*log2n)O(n*log2n)不稳定O(1)
    希尔排序OO不稳定O(1)
    展开全文
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 2017-07-30 21:33:22
    空间复杂度 是否稳定 冒泡排序 :————-: :—–: :—–: :—–: 选择排序 :————-: :—–: :—–: :—–: 直接插入排序 :————-: :—–: :—–: :—–: 归并排序 :————-: :—–: :

    排序算法分类

    这里写图片描述

    排序算法比较表格填空

    排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定
    冒泡排序:————-::—–::—–::—–:
    选择排序:————-::—–::—–::—–:
    直接插入排序:————-::—–::—–::—–:
    归并排序:————-::—–::—–::—–:
    快速排序:————-::—–::—–::—–:
    堆排序:————-::—–::—–::—–:
    希尔排序:————-::—–::—–::—–:
    计数排序:————-::—–::—–::—–:
    基数排序:————-::—–::—–::—–:

    排序算法比较表格

    排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定
    冒泡排序 On2 On2 O1
    选择排序 On2 On2 O1 不是
    直接插入排序 On2 On2 O1
    归并排序 O(nlogn) O(nlogn) On
    快速排序 O(nlogn) On2 Ologn 不是
    堆排序 O(nlogn) O(nlogn) O1 不是
    希尔排序 O(nlogn) Ons O1 不是
    计数排序 O(n+k) O(n+k) O(n+k)
    基数排序 O(NM) O(NM) O(M)

    注:

    1 归并排序可以通过手摇算法将空间复杂度降到O(1),但是时间复杂度会提高。

    2 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数。

    辅助记忆

    • 时间复杂度记忆-
      • 冒泡、选择、直接 排序需要两个for循环,每次只关注一个元素,平均时间复杂度为 On2 (一遍找元素 O(n) ,一遍找位置 O(n)
      • 快速、归并、希尔、堆基于二分思想,log以2为底,平均时间复杂度为 O(nlogn) (一遍找元素 O(n) ,一遍找位置 O(logn)
    • 稳定性记忆-“快希选堆”(快牺牲稳定性)
      • 排序算法的稳定性:排序前后相同元素的相对位置不变,则称排序算法是稳定的;否则排序算法是不稳定的。

    原理理解

    1 冒泡排序

    1.1 过程

    冒泡排序从小到大排序:一开始交换的区间为0~N-1,将第1个数和第2个数进行比较,前面大于后面,交换两个数,否则不交换。再比较第2个数和第三个数,前面大于后面,交换两个数否则不交换。依次进行,最大的数会放在数组最后的位置。然后将范围变为0~N-2,数组第二大的数会放在数组倒数第二的位置。依次进行整个交换过程,最后范围只剩一个数时数组即为有序。

    1.2 动图

    1.3 核心代码(函数)

    //array[]为待排序数组,n为数组长度
    void BubbleSort(int array[], int n)
    {
        int i, j, k;
        for(i=0; i<n-1; i++)
            for(j=0; j<n-1-i; j++)
            {
                if(array[j]>array[j+1])
                {
                    k=array[j];
                    array[j]=array[j+1];
                    array[j+1]=k;
                }
            }
    }

    2 选择排序

    2.1 过程

    选择排序从小到大排序:一开始从0~n-1区间上选择一个最小值,将其放在位置0上,然后在1~n-1范围上选取最小值放在位置1上。重复过程直到剩下最后一个元素,数组即为有序。

    2.2 动图


    2.3 核心代码(函数)

    //array[]为待排序数组,n为数组长度
    void selectSort(int array[], int n)
    {
        int i, j ,min ,k;
        for( i=0; i<n-1; i++)
        {
            min=i; //每趟排序最小值先等于第一个数,遍历剩下的数
            for( j=i+1; j<n; j++) //从i下一个数开始检查
            {
                if(array[min]>array[j])
                {
                    min=j;
                }
            }
            if(min!=i)
            {
                k=array[min];
                array[min]=array[i];
                array[i]=k;
            }
        }
    }

    3 插入排序

    3.1 过程

    插入排序从小到大排序:首先位置1上的数和位置0上的数进行比较,如果位置1上的数大于位置0上的数,将位置0上的数向后移一位,将1插入到0位置,否则不处理。位置k上的数和之前的数依次进行比较,如果位置K上的数更大,将之前的数向后移位,最后将位置k上的数插入不满足条件点,反之不处理。

    3.2 动图


    3.3 核心代码(函数)

    //array[]为待排序数组,n为数组长度
    void insertSort(int array[], int n)
    {
        int i,j,temp;
        for( i=1;i<n;i++)
        {
            if(array[i]<array[i-1])
            {
                temp=array[i];
                for( j=i;array[j-1]>temp;j--)
                {
                    array[j]=array[j-1];
                }
                array[j]=temp;
            }
        }
    }

    4 归并排序

    4.1 过程

    归并排序从小到大排序:首先让数组中的每一个数单独成为长度为1的区间,然后两两一组有序合并,得到长度为2的有序区间,依次进行,直到合成整个区间。

    4.2 动图


    4.3 核心代码(函数)

    • 递归实现
    实现归并,并把数据都放在list1里面 
    void merging(int *list1, int list1_size, int *list2,  int list2_size)
    {
        int i=0, j=0, k=0, m=0;
        int temp[MAXSIZE];
    
        while(i < list1_size && j < list2_size)
        {
            if(list1[i]<list2[j])
            {
                temp[k++] = list1[i++];
            }
            else
            {
                temp[k++] = list2[j++];
            }
        }
        while(i<list1_size)
        {
            temp[k++] = list1[i++];
        }
        while(j<list2_size)
        {
            temp[k++] = list2[j++];
        }
    
        for(m=0; m < (list1_size+list2_size); m++)
        {
            list1[m]=temp[m];
        }
    }
    //如果有剩下的,那么说明就是它是比前面的数组都大的,直接加入就可以了 
    void mergeSort(int array[], int n)
    {
        if(n>1)
        {
            int *list1 = array;
            int list1_size = n/2;
            int *list2 = array + n/2;
            int list2_size = n-list1_size;
    
            mergeSort(list1, list1_size);
            mergeSort(list2, list2_size);
    
            merging(list1, list1_size, list2, list2_size);
        }
    }
    //归并排序复杂度分析:一趟归并需要将待排序列中的所有记录  
    //扫描一遍,因此耗费时间为O(n),而由完全二叉树的深度可知,  
    //整个归并排序需要进行[log2n],因此,总的时间复杂度为  
    //O(nlogn),而且这是归并排序算法中平均的时间性能  
    //空间复杂度:由于归并过程中需要与原始记录序列同样数量级的  
    //存储空间去存放归并结果及递归深度为log2N的栈空间,因此空间  
    //复杂度为O(n+logN)  
    //也就是说,归并排序是一种比较占内存,但却效率高且稳定的算法 
    • 迭代实现
    void MergeSort(int k[],int n)  
    {  
        int i,next,left_min,left_max,right_min,right_max;  
        //动态申请一个与原来数组一样大小的空间用来存储
        int *temp = (int *)malloc(n * sizeof(int));  
        //逐级上升,第一次比较2个,第二次比较4个,第三次比较8个。。。  
        for(i=1; i<n; i*=2)  
        {  
            //每次都从0开始,数组的头元素开始  
            for(left_min=0; left_min<n-i; left_min = right_max)  
            {  
                right_min = left_max = left_min + i;  
                right_max = left_max + i;  
                //右边的下标最大值只能为n  
                if(right_max>n)  
                {  
                    right_max = n;  
                }  
                //next是用来标志temp数组下标的,由于每次数据都有返回到K,  
                //故每次开始得重新置零  
                next = 0;  
                //如果左边的数据还没达到分割线且右边的数组没到达分割线,开始循环  
                while(left_min<left_max&&right_min<right_max)  
                {  
                    if(k[left_min] < k[right_min])  
                    {  
                        temp[next++] = k[left_min++];  
                    }  
                    else  
                    {  
                        temp[next++] = k[right_min++];  
                    }  
                }  
                //上面循环结束的条件有两个,如果是左边的游标尚未到达,那么需要把  
                //数组接回去,可能会有疑问,那如果右边的没到达呢,其实模拟一下就可以  
                //知道,如果右边没到达,那么说明右边的数据比较大,这时也就不用移动位置了  
    
                while(left_min < left_max)  
                {  
                    //如果left_min小于left_max,说明现在左边的数据比较大  
                    //直接把它们接到数组的min之前就行  
                    k[--right_min] = k[--left_max];   
                }  
                while(next>0)  
                {  
                    //把排好序的那部分数组返回该k  
                    k[--right_min] = temp[--next];        
                }  
            }  
        }  
    }  
    //非递归的方法,避免了递归时深度为log2N的栈空间,
    //空间只是用到归并临时申请的跟原来数组一样大小的空间,并且在时间性能上也有一定的提升,
    //因此,使用归并排序是,尽量考虑用非递归的方法。

    5 快速排序

    5.1 过程

    快速排序从小到大排序:在数组中随机选一个数(默认数组首个元素),数组中小于等于此数的放在左边,大于此数的放在右边,再对数组两边递归调用快速排序,重复这个过程。

    5.2 动图


    5.3 核心代码(函数)

    推荐程序(好理解)

    //接口调整
    void adjust_quicksort(int k[],int n)  
    {  
       quicksort(k,0,n-1);  
    }  
    void quicksort(int a[], int left, int right)  
    {  
        int i,j,t,temp;  
        if(left>right)   //(递归过程先写结束条件)
           return;  
    
        temp=a[left]; //temp中存的就是基准数  
        i=left;  
        j=right;  
        while(i!=j)  
        {  
                       //顺序很重要,要先从右边开始找(最后交换基准时换过去的数要保证比基准小,因为基准                               
                       //选取数组第一个数,在小数堆中) 
                       while(a[j]>=temp && i<j)  
                                j--;  
                       //再找右边的  
                       while(a[i]<=temp && i<j)  
                                i++;  
                       //交换两个数在数组中的位置  
                       if(i<j)  
                       {  
                                t=a[i];  
                                a[i]=a[j];  
                                a[j]=t;  
                       }  
        }  
        //最终将基准数归位 (之前已经temp=a[left]过了,交换只需要再进行两步)
        a[left]=a[i];  
        a[i]=temp;  
    
        quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程  
        quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程  
    }  

    6 堆排序

    6.1 过程

    堆排序从小到大排序:首先将数组元素建成大小为n的大顶堆,堆顶(数组第一个元素)是所有元素中的最大值,将堆顶元素和数组最后一个元素进行交换,再将除了最后一个数的n-1个元素建立成大顶堆,再将最大元素和数组倒数第二个元素进行交换,重复直至堆大小减为1。

    • 注:完全二叉树
      假设二叉树深度为n,除了第n层外,n-1层节点都有两个孩子,第n层节点连续从左到右。如下图
      这里写图片描述

    • 注:大顶堆
      大顶堆是具有以下性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值。
      即,根节点是堆中最大的值,按照层序遍历给节点从1开始编号,则节点之间满足如下关系:
      这里写图片描述 (1<=i<=n/2)

    6.2 动图



    6.3 核心代码(函数)

    这里写图片描述
    注意!!!数组从1开始,1~n

    void heapSort(int array[], int n)
    {
        int i;
        for (i=n/2;i>0;i--)
        {
            HeapAdjust(array,i,n);//从下向上,从右向左调整
        }
        for( i=n;i>1;i--)
        {
            swap(array, 1, i);
            HeapAdjust(array, 1, i-1);//从上到下,从左向右调整
        }
    }
    void HeapAdjust(int array[], int s, int n )
    {
        int i,temp;
        temp = array[s];
        for(i=2*s;i<=n;i*=2)
        {
            if(i<n&&array[i]<array[i+1])
            {
                i++;
            }
            if(temp>=array[i])
            {
                break;
            }
            array[s]=array[i];
            s=i;
        }
        array[s]=temp;
    }
    void swap(int array[], int i, int j)
    {
        int temp;
    
        temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

    7 希尔排序

    7.1 过程

    希尔排序是插入排序改良的算法,希尔排序步长从大到小调整,第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换,直至步长为1,步长选择是关键。

    7.2 动图

    这里写图片描述

    7.3 核心程序(函数)

    //下面是插入排序
    void InsertSort( int array[], int n)
    {
        int i,j,temp;
        for( i=0;i<n;i++ )
        {
            if(array[i]<array[i-1])
            {
                temp=array[i];
                for( j=i-1;array[j]>temp;j--)
                {
                    array[j+1]=array[j];
                }
                array[j+1]=temp;
            }
        }
    }
    //在插入排序基础上修改得到希尔排序
    void SheelSort( int array[], int n)
    {
        int i,j,temp;
        int gap=n; //~~~~~~~~~~~~~~~~~~~~~
        do{
            gap=gap/3+1;  //~~~~~~~~~~~~~~~~~~
            for( i=gap;i<n;i++ )
            {
                if(array[i]<array[i-gap])
                {
                    temp=array[i];
                    for( j=i-gap;array[j]>temp;j-=gap)
                    {
                        array[j+gap]=array[j];
                    }
                    array[j+gap]=temp;
                }
            }
        }while(gap>1);  //~~~~~~~~~~~~~~~~~~~~~~
    
    }

    8 桶排序(基数排序和基数排序的思想)

    8.1 过程

    桶排序是计数排序的变种,把计数排序中相邻的m个”小桶”放到一个”大桶”中,在分完桶后,对每个桶进行排序(一般用快排),然后合并成最后的结果。

    8.2 图解

    8.3 核心程序

    #include <stdio.h>
    int main()
    {
        int a[11],i,j,t;
        for(i=0;i<=10;i++)
            a[i]=0;  //初始化为0
    
        for(i=1;i<=5;i++)  //循环读入5个数
        {
            scanf("%d",&t);  //把每一个数读到变量t中
            a[t]++;  //进行计数(核心行)
        }
    
        for(i=0;i<=10;i++)  //依次判断a[0]~a[10]
            for(j=1;j<=a[i];j++)  //出现了几次就打印几次
                printf("%d ",i);
    
        getchar();getchar(); 
        //这里的getchar();用来暂停程序,以便查看程序输出的内容
        //也可以用system("pause");等来代替
        return 0;
    }

    9 计数排序

    9.1 过程

    算法的步骤如下:
    - 找出待排序的数组中最大和最小的元素
    - 统计数组中每个值为i的元素出现的次数,存入数组C的第i项
    - 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
    - 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

    9.2 图解

    这里写图片描述

    9.3 核心程序(函数)

    程序1#define NUM_RANGE (100)    //预定义数据范围上限,即K的值
    
    void counting_sort(int *ini_arr, int *sorted_arr, int n)  //所需空间为 2*n+k
    {  
           int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE);  
           int i, j, k;  
    
           //初始化统计数组元素为值为零 
           for(k=0; k<NUM_RANGE; k++){  
                   count_arr[k] = 0;  
           }  
           //统计数组中,每个元素出现的次数    
           for(i=0; i<n; i++){  
                   count_arr[ini_arr[i]]++;  
           }  
    
           //统计数组计数,每项存前N项和,这实质为排序过程
           for(k=1; k<NUM_RANGE; k++){  
                   count_arr[k] += count_arr[k-1];  
           }  
    
           //将计数排序结果转化为数组元素的真实排序结果
           for(j=n-1 ; j>=0; j--){  
               int elem = ini_arr[j];          //取待排序元素
               int index = count_arr[elem]-1;  //待排序元素在有序数组中的序号
               sorted_arr[index] = elem;       //将待排序元素存入结果数组中
               count_arr[elem]--;              //修正排序结果,其实是针对算得元素的修正
           }  
           free(count_arr);  
    }  
    
    程序2:C++(最大最小压缩桶数)
    public static void countSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            int min = arr[0];
            int max = arr[0];
            for (int i = 1; i < arr.length; i++) {
                min = Math.min(arr[i], min);
                max = Math.max(arr[i], max);
            }
            int[] countArr = new int[max - min + 1];
            for (int i = 0; i < arr.length; i++) {
                countArr[arr[i] - min]++;
            }
            int index = 0;
            for (int i = 0; i < countArr.length; i++) {
                while (countArr[i]-- > 0) {
                    arr[index++] = i + min;
            }
    }

    10 基数排序

    10.1 过程

    基数排序是基于数据位数的一种排序算法。
    它有两种算法
    ①LSD–Least Significant Digit first 从低位(个位)向高位排。
    ②MSD– Most Significant Digit first 从高位向低位(个位)排。
    时间复杂度O(N*最大位数)。
    空间复杂度O(N)。

    10.2 图解

    这里写图片描述
    对a[n]按照个位0~9进行桶排序:
    这里写图片描述
    对b[n]进行累加得到c[n],用于b[n]中重复元素计数
    !!!b[n]中的元素为temp中的位置!!!跳跃的用++补上:
    这里写图片描述
    temp数组为排序后的数组,写回a[n]。temp为按顺序倒出桶中的数据(联合b[n],c[n],a[n]得到),重复元素按顺序输出:
    这里写图片描述

    10.3 核心程序

    //基数排序  
    //LSD  先以低位排,再以高位排  
    //MSD  先以高位排,再以低位排  
    void LSDSort(int *a, int n)  
    {  
        assert(a);  //判断a是否为空,也可以a为空||n<2返回
        int digit = 0;   //最大位数初始化
        for (int i = 0; i < n; ++i)  
        {   //求最大位数
            while (a[i] > (pow(10,digit)))  //pow函数要包含头文件math.h,pow(10,digit)=10^digit
            {  
                digit++;  
            }  
        }  
        int flag = 1;   //位数
        for (int j = 1; j <= digit; ++j)  
        {  
            //建立数组统计每个位出现数据次数(Digit[n]为桶排序b[n])  
            int Digit[10] = { 0 };  
            for (int i = 0; i < n; ++i)  
            {  
                Digit[(a[i] / flag)%10]++;  //flag=1时为按个位桶排序
            }  
             //建立数组统计起始下标(BeginIndex[n]为个数累加c[n],用于记录重复元素位置
             //flag=1时,下标代表个位数值,数值代表位置,跳跃代表重复)
            int BeginIndex[10] = { 0 };  
            for (int i = 1; i < 10; ++i)  
            {  
                //累加个数
                BeginIndex[i] = BeginIndex[i - 1] + Digit[i - 1];  
            }  
            //建立辅助空间进行排序 
            //下面两条可以用calloc函数实现
            int *tmp = new int[n];  
            memset(tmp, 0, sizeof(int)*n);//初始化  
            //联合各数组求排序后的位置存在temp中
            for (int i = 0; i < n; ++i)  
            {  
                int index = (a[i] / flag)%10;  //桶排序和位置数组中的下标
                //计算temp相应位置对应a[i]中的元素,++为BeginIndex数组数值加1
                //跳跃间隔用++来补,先用再++
                tmp[BeginIndex[index]++] = a[i];  
            }  
            //将数据重新写回原空间  
            for (int i = 0; i < n; ++i)  
            {  
                a[i] = tmp[i];  
            }  
            flag = flag * 10;  
            delete[] tmp;  
        }  
    }  

    附:

    1 完整程序框架(冒泡排序举例)

    1.1 VS2010程序
    #include "stdafx.h"
    #include "stdio.h"
    #include <stdlib.h>
    
    void BubbleSort(int array[], int n){
        int i,j,k,count1=0, count2=0;
        for(i=0; i<n-1; i++)
            for(j=n-1; j>i; j--)
            {
                count1++;
                if(array[j-1]>array[j])
                {
                    count2++;
                    k=array[j-1];
                    array[j-1]=array[j];
                    array[j]=k;
                }
            }
        printf("总共的循环次序为:%d,  总共的交换次序为:%d\n\n", count1, count2);
    }
    
    
    int main(int argc, _TCHAR* argv[])
    {
        int as[]={0,1,2,3,4,6,8,5,9,7};
        BubbleSort(as, 10);
        for(int i=0; i<10; i++)
        {
            printf("%d", as[i]);
        }
        printf("\n\n");
        system("pause");
        return 0;
    }
    1.2 执行程序(OJ)
    #include <stdio.h>
    
    void BubbleSort(int array[], int n){
        int i,j,k,count1=0, count2=0;
        for(i=0; i<n-1; i++)
            for(j=n-1; j>i; j--)
            {
                count1++;
                if(array[j-1]>array[j])
                {
                    count2++;
                    k=array[j-1];
                    array[j-1]=array[j];
                    array[j]=k;
                }
            }
        printf("总共的循环次序为:%d,  总共的交换次序为:%d\n\n", count1, count2);
    }
    
    int main()
    {
        int as[]={0,1,2,3,4,6,8,5,9,7};
        BubbleSort(as, 10);
        int i=0;
        for(i=0; i<10; i++)
        {
            printf("%d", as[i]);
        }
        return 0;
    }

    2 关于交换的优化

    不用中间变量进行交换

    if(A[j] <= A[i]){
        A[j] = A[j] + A[i];
        A[i] = A[j] - A[i];
        A[j] = A[j] - A[i];
    }

    3 C语言实现数组动态输入

    #include <stdio.h>  
    #include <assert.h>  //断言头文件
    #include <stdlib.h>  
    
    int main(int argc, char const *argv[])  
    {  
        int size = 0;  
        scanf("%d", &size);   //首先输入数组个数
        assert(size > 0);     //判断数组个数是否非法
    
        int *array = (int *)calloc(size, sizeof(int));  //动态分配数组
        if(!R1)  
        {  
            return;           //申请空间失败  
        }  
    
        int i = 0;  
        for (i = 0; i < size; ++i) {  
            scanf("%d", &array[i]);  
        }  
    
        mergeSort(array, size);  
        printArray(array, size);  
    
        free(array);  
        return 0;  
    } 

    注:
    1.colloc与malloc类似,但是主要的区别是存储在已分配的内存空间中的值默认为0,使用malloc时,已分配的内存中可以是任意的值.
    2.colloc需要两个参数,第一个是需要分配内存的变量的个数,第二个是每个变量的大小.

    展开全文
  • 空间复杂度 时间复杂度(平均/最坏) 稳定性 冒泡排序 O(1) O(n2)/O(n2) 稳定 选择排序 O(1) O(n2)/O(n2) 不稳定 插入排序 O(1) O(n2)/O(n2) 稳定 希尔排序 O(1) O(nlogn)/O(ns) (s为步长) 不稳定 ...
    算法空间复杂度时间复杂度(平均/最坏)稳定性
    冒泡排序O(1)O(n2)/O(n2)稳定
    选择排序O(1)O(n2)/O(n2)不稳定
    插入排序O(1)O(n2)/O(n2)稳定
    希尔排序O(1)O(nlogn)/O(ns) (s为步长)不稳定
    快速排序O(logn)O(n*logn)/O(n2)不稳定
    归并排序O(n)O(nlogn)/O(nlogn)稳定
    堆排序O(1)O(nlogn)/O(nlogn)不稳定

    时间复杂度:是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
    计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

    空间复杂度:是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

    稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

    展开全文
  • 排序算法时间复杂度、空间复杂度、稳定性列表

    排序算法时间复杂度、空间复杂度、稳定性列表
    在这里插入图片描述

    展开全文
  • 各种排序算法时间复杂度和空间复杂度
  • 最近在准备秋招的期间遇到了很多排序算法时间复杂度、空间复杂度、稳定性相关的题目,那就做个大致的总结吧。 排序算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定...
  • 目录 1.什么是复杂度 2.什么是时间/空间复杂度 ...在做算法相关的东西时,又常提到两个概念叫 时间复杂度、空间复杂度。 那这些复杂度都是什么呢? 1.什么是复杂度 计算机在处理大量数据的时候,我们查...
  • 专栏原创出处:github-源笔记文件 ,github-源码 ,欢迎 Star,转载请附上原文出处链接和本声明。...空间复杂度参考 1.算法 算法是解决特定问题求解步骤的描述,在计算机中表现为指定的有限序列...
  • 算法时间复杂度和空间复杂度

    千次阅读 2013-08-29 17:10:36
    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为...
  • 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是...
  • 排序算法分类 排序算法比较表格 排序算法 平均时间复杂度 ... 空间复杂度 是否稳定 冒泡排序 O(n2) O(n2) O(1) 是 选择排序 O(n2) O(n2) O(1) ...
  • 算法时间复杂度
  • 常用的排序算法的时间复杂度和空间复杂度 常用的查找算法的时间复杂度和空间复杂度 应用场景 (1)若n较小(如n≤50),可采用直接插入或直接选择排序。  当记录规模较小时,直接插入排序较好;否则因为直接选择...
  • 算法时间复杂度 和 空间复杂度

    千次阅读 2016-06-30 11:24:23
     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。  随着计算机硬件和软件的提升,一个算法的执行时间是算不太精确的。只能依据统计方法对算法进行估算。我们抛开硬件...
  • 文章转载自: http://blog.chinaunix.net/uid-21457204-id-3060260.html 常用排序算法的时间复杂度和空间复杂度表格,如下:
  • 常用的排序算法的时间复杂度和空间复杂度: 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n) 选择排序 O(n2) ...
  • 八大排序算法时间复杂度和空间复杂度对比 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 八大排序就是...
  • 算法的复杂度分为:时间复杂度和空间复杂度1、时间复杂度实际就是一个函数,该函数计算的是执行基本操作的次数;本质就是在计算基本操作重复执行的次数 ,并且大多数情况下分析的是最坏情况的例如: voidTest(int n...
  • 空间复杂度 稳定性 选择排序 Selection n2 n2 n2 1 不稳 冒泡排序 Bubble ...
  • 1.空间复杂度 算法中包含原操作次数的多少叫做算法的时间复杂度,用它来衡量一个算法的运行时间性能。  如果存在两个正常数c和n0,对于所有的 n>=n0,有| f(n) | f(n) 是 T(n) 的同数量级函数。把 ...
  • 一、排序算法的时间复杂度及空间复杂度 冒泡: 平均O(N2) ,最坏O(N2) ,最好O(N) ,辅助内存O(1),稳定排序 最好情况是加了改进方法的最好:即冒泡的过程中检查是否发生了交换,如果没有发生交换,说明都排好序了...
  • 时间复杂度 ...利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作
  • 常用排序算法时间复杂度和空间复杂度

    万次阅读 多人点赞 2015-05-17 20:50:08
    摘自维基百科: http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95#.E7.A8.B3.E5.AE.9A.E6.80.A7 ...空间复杂度 描述 平均 最坏 冒泡排序 数组 (无序区,有序区
  • 平均时间复杂度:简单排序为,其他为,希尔排序略有区别。 稳定性:洗牌快洗对,不稳定。快速排序、希尔排序、堆排序。 最好情况:冒泡和直接插入最佳,简单选择最差。简单排序涵盖了最佳和最差。 最...
  • 常用的算法的时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,690
精华内容 15,076
热门标签
关键字:

冒泡算法空间复杂度