时间复杂度与常见排列算法

Changing Lin

关注

发布于: 2021 年 01 月 24 日

一、时间复杂度概念

1、时间复杂度概念

提到时间复杂度，第一时间想到的是算法，简单说，算法就是你解决问题的方法，而你用这个方法解决这个问题所执行的语句次数，称为语句频度或者时间频度，记为 T(n)。

什么是时间复杂度，算法中某个函数有 n 次基本操作重复执行，用 T(n)表示。

现在有某个辅助函数 f(n),使得当 n 趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。

记作 T(n)=O(f(n)),称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

通俗一点讲，其实所谓的时间复杂度，就是找了一个同样曲线类型的函数 f(n)来表示这个算法的在 n 不断变大时的趋势。

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

2、计算时间复杂度的方法：

推导大 O 阶，我们可以按照如下的规则来进行推导，得到的结果就是大 O 表示法：

a.用常数 1 来取代运行时间中所有加法常数。

b.修改后的运行次数函数中，只保留最高阶项

c.如果最高阶项存在且不是 1，则去除与这个项相乘的常数。

二、理解

1、常数阶：O(1)的算法是一些运算次数为常数的算法。例如：

    temp=a;    a=b;    b=temp;

复制代码

上面语句共三条操作，单条操作的频度为 1，即使他有成千上万条操作，也只是个较大常数，这一类的时间复杂度为 O(1)。

int sum = 0,n = 100; //执行一次  sum = (1+n)*n/2; //执行一次  System.out.println (sum); //执行一次

复制代码

上面算法的运行的次数的函数为 f(n)=3，根据推导大 O 阶的规则 1，我们需要将常数 3 改为 1，则这个算法的时间复杂度为 O(1)。

2、线性阶：O(n)的算法是一些线性算法。例如：

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

复制代码

上面代码中第一行频度 1，第二行频度为 n，第三行频度为 n，所以 f(n)=n+n+1=2n+1。所以时间复杂度 O(n)。这一类算法中操作次数和 n 正比线性增长。

3、对数阶：O(logn) 一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。例如：

    int i=1;     while (i<=n)         i=i*2;

复制代码

上面代码设第三行的频度是 f(n), 则：2^f(n)<=n;f(n)<=log₂n，取最大值 f(n)= log₂n，所以 T(n)=O(log₂n ) 。

4、平方阶：O(n²)（n 的 k 次方的情况）最常见的就是平时的对数组进行排序的各种简单算法都是 O(n²)，例如直接插入排序的算法。

    sum=0；                    for(i=0;i<n;i++)          for(j=0;j<n;j++)           sum++；

复制代码

第一行频度 1，第二行 n，第三行 n²，第四行 n²，T(n)=2n²+n+1 =O(n²)

5、平方阶：O(n²)

for(int i = 0; i < n; i++){    for(int j = i; j < n; j++){        printf("%d ",i);    }}  //运行次数为(1+n)*n/2//时间复杂度O(n^2)

复制代码

6、时间复杂度按 n 越大算法越复杂来排的话：

常数阶 O(1)、对数阶 O(logn)、线性阶 O(n)、线性对数阶 O(nlogn)、平方阶 O(n²)、立方阶 O(n³)、……k 次方阶 O(n 的 k 次方)、指数阶 O(2 的 n 次方)。

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

复制代码

三、其他

1、冒泡程序---平方阶

public void sort(int[] args){    //第一层循环从数组的最后往前遍历    for (int i = args.length - 1; i > 0 ; --i) {        for (int j = 0; j < i; j++) {            //保证在相邻的两个数中比较选出最大的并且进行交换(冒泡过程)            if (args[j] > args[j+1]) {                int temp = args[j];                args[j] = args[j+1];                args[j+1] = temp;            }        }    }}

复制代码

上面算法的运行的次数函数为 f(n)= (n-1)+(n-2)+(n-3)+(n-4)+...===>等差数列求和===> (n*(n-1))/2 ===>n^2/2-n/2===> f(n)=O(n^2)

2、选择排序

public void sort(int[] args){    int len = args.length;    for (int i = 0,k = 0; i < len; i++,k = i) {    n        // 在这一层循环中找最小        for (int j = i + 1; j < len; j++) {    n-1            // 如果后面的元素比前面的小，那么就交换下标，每一趟都会选择出来一个最小值的下标            if (args[k] > args[j]) k = j;        }
        if (i != k) {            int tmp = args[i];            args[i] = args[k];            args[k] = tmp;        }    }}

复制代码

上面算法的运行的次数函数为 f(n)= (n-1)+(n-2)+(n-3)+(n-4)+...===>等差数列求和===> (n*(n-1))/2 ===>n^2/2-n/2===> f(n)=O(n^2)

3、插入排序

public static void insertSort(int a[]){    int fn = 0;    int n = a.length;    int temp = 0;    printfArray(a);    for(int i = 1; i < n; i++){        for(int j = i; j >0; j--){            fn++;            if(a[j] < a[j-1]){ // 交换                temp = a[j];                a[j] = a[j-1];                a[j-1] = temp;            }else{                break;            }        }        printfArray(a);    }    printfArray(a);    System.out.println("语句频度："+fn);}

复制代码

上面算法的运行的次数函数为 f(n)= (n-1)+(n-2)+(n-3)+(n-4)+...===>等差数列求和===> (n*(n-1))/2 ===>n^2/2-n/2===> f(n)=O(n^2)

发布于: 2021 年 01 月 24 日阅读数: 30

原文链接:【http://xie.infoq.cn/article/8ba65bf3e6486213d684d6c28】。文章转载请联系作者。

Changing Lin

关注

获得机遇的手段远超于固有常规之上~ 2020.04.29 加入

我能做的，就是调整好自己的精神状态，以最佳的面貌去面对那些未曾经历过得事情，对生活充满热情和希望。

发布

暂无评论

创作场景

时间复杂度与常见排列算法

一、时间复杂度概念

1、时间复杂度概念

2、计算时间复杂度的方法：

二、理解

1、常数阶：O(1)的算法是一些运算次数为常数的算法。例如：

2、线性阶：O(n)的算法是一些线性算法。例如：

3、对数阶：O(logn) 一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。例如：

4、平方阶：O(n²)（n 的 k 次方的情况）最常见的就是平时的对数组进行排序的各种简单算法都是 O(n²)，例如直接插入排序的算法。

5、平方阶：O(n²)

6、时间复杂度按 n 越大算法越复杂来排的话：

三、其他

1、冒泡程序---平方阶

2、选择排序

3、插入排序

Changing Lin

评论