精华内容
下载资源
问答
  • 根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 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(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)

    1、时间复杂度 
    (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 
    (2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。 
    在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 2、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。 
    (3)渐进时间复杂度评价算法时间性能   主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

    2、类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 
    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地/"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

    当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

    7
    展开全文
  • 各种排序算法时间复杂度和空间复杂度表: 比较时间复杂度函数的情况如下图: 对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法: 接下来博主抽时间要整理一下各经典算法思想和心得,敬请期待
  • 排序算法时间复杂度的研究 期刊网站可是要现金的哦。
  • 各种排序算法时间复杂度比较

    千次阅读 2012-10-27 09:46:49
    各种排序算法时间复杂度比较
  • 排序算法比较 主要内容 1利用随机函数产生10000个...3 给出该排序算法统计每一种排序方法的性能 以运行程序所花 费的时间为准进行对比找出其中两种较快的方法 程序的主要功能 1?随机数在排序函数作用下进行排序 2.程序
  • PAGE PAGE 1 PAGE 2 PAGE 2 1 排序算法比较 主要内容 1)利用随机函数产生10000个随机整数对这些数...3给出该排序算法统计每一种排序方法的性能以运行程序所花费的时间为准进行对比找出其中两种较快的方法 程序的主要功
  • 算法设计的好坏直接影响计算机的运行时间,计算机排序方法较多,时间复杂度差别较大. 本文从理论 上研究了线性排序(选择法、冒泡法、计数法) 、比较排序、堆排序和快速排序等几种常用的排序算法时间复杂度.
  • 排序算法分类 排序算法比较表格 排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定 冒泡排序 O(n2) O(n2) O(1) 是 选择排序 O(n2) O(n2) O(1) ....
  • 自然归并排序算法时间复杂度分析

    千次阅读 2016-11-24 22:21:13
    最近在看一部美剧《breaking bad》,从中领会了不少东西。回头再看过去写的博客,感觉真是很糟糕。...这篇对自然归并排序算法时间复杂度的分析便是第一篇。   对于普通归并排序算法,我就不
  • 算法时间复杂度
  • 常见排序算法时间复杂度

    千次阅读 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) 原则: 常数1代替所有加法中的常数 只保留最高阶数项(且不要前面的系数) ...2.空间复杂度 ...常用空间换时间 ...时间复杂度 ...时间复杂度:算法性能指标(本质常数时间...常用排序算法及...
  • from:... 各种排序算法时间复杂度比较 以上图片来维基百科,http://en.wikipedia.org/wiki/Algorithms  维基百科真是个好东东!
  • 各种排序算法比较 各种常用排序算法类别排序方法时间复杂度空间复杂度稳定性复杂性特点最好平均最坏辅助存储 简单 插入排序直接插入O(N)O(N2)O(N2)O(1)稳定简单 希尔排序O(N)O(N1.3)O(N2)O(1)不稳定复杂 选择...
  • 插入排序时间复杂度: 最好: 所有元素已经排好序,只需遍历一遍,无需交换位置; 最坏: 所有元素逆序排列,遍历一次需要比较的元素个数每次+1,所以时间复杂度是O(n^2); 平均时间复杂度就是O(n^2)喽。 2、 ...
  • 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 选择排序 Selection n2 n2 n2 ...
  • 选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
  • 常用的排序算法时间复杂度和空间复杂度 常用的查找算法的时间复杂度和空间复杂度 应用场景 (1)若n较小(如n≤50),可采用直接插入或直接选择排序。  当记录规模较小时,直接插入排序较好;否则因为直接选择...
  • 一、排序算法时间复杂度及空间复杂度 冒泡: 平均O(N2) ,最坏O(N2) ,最好O(N) ,辅助内存O(1),稳定排序 最好情况是加了改进方法的最好:即冒泡的过程中检查是否发生了交换,如果没有发生交换,说明都排好序了...
  • 排序方法 最好时间 最坏时间 平均时间 辅助空间 稳定性 直接插入 O(n) O(n2) O(n2) O(1) ...
  • 1方案设计 我这次实验通过随机生成3000个随机数把随机数存到数组中,用这同一组随机数据分别进行四种排序直接插入排序直接选择排序冒泡排序和快速排序还通过了调用txt文件把运算所需时间导出分别输出各个算法所需用时...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 240,510
精华内容 96,204
关键字:

排序算法的时间复杂度