三界第一法则——时间复杂度

喜欢ヅ旅行 2022-09-12 08:59 172阅读 0赞

**目录**

目标

概念

常见的几种时间复杂度及效率对比

分析程序的时间复杂度

时间复杂度是O(1)的程序

时间复杂度是O(logn)的程序

时间复杂度是O(n)的程序

时间复杂度是O(nlogn)的程序

时间复杂度是O (![n^\{2\}][n_2])的程序

总结

--------------------

# 目标 #

*  明确时间复杂度的概念；
 *  了解常见的几种时间复杂度，能根据效率排列出这几种常见的时间复杂度；
 *  掌握时间复杂度的计算方法，并能分析相关程序的时间复杂度。

--------------------

# 概念 #

在计算机科学中，时间复杂性，又称时间复杂度，它定性描述该算法的运行时间。时间复杂度常用大写o符号表述，不包括这个函数的**低阶项**和**首项系数**。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

--------------------

# 常见的几种时间复杂度及效率对比 #

效率从高到低排序如下：

**O(1)>O(logn)>O(n)>O(nlogn)>O(![n^\{2\}][n_2])>O(![n^\{x\}][n_x])**

也可以说：

*  **O(1)**的时间复杂度是**常数**；
 *  **O(logn)**的时间复杂度是**对数；**
 *  **O(nlogn)**的时间复杂度是**线性对数；**
 *  **O(n)**的时间复杂度是**线性；**
 *  **O(![n^\{2\}][n_2])**的时间复杂度是**平方；**
 *  **O(![n^\{x\}][n_x])**的时间复杂度是**x次方。**

即效率从高到低排序也可以是：

**常数>对数>线性>线性对数>平方>次方**

--------------------

# 分析程序的时间复杂度 #

## **时间复杂度是O(1)的程序** ##

public static void constant(){
        //时间复杂度是O(1)
        int num=100;
        //这里会运行101次，最后一次判断不符合条件退出循环。运行次数是一个确定的常数。所以时间复杂度是常数，即O(1)。
        for(int i = 0 ;i < num;i++){
            //这里会运行100次，运行次数是一个确定的常数。所以时间复杂度是常数，即O(1)。
            num = num + i;
        }
    }

--------------------

## **时间复杂度是O(logn)的程序** ##

public static void log(int n) {
            int i=1;
            while (i > n) {
                //求这里的时间复杂度。
                i = i * 2;
            }
    }

**分析**

1.  第1次循环：i=i\*2
2.  第2次循环：i=i\*2\*2
3.  第x次循环：i=i\*![2^\{x\}][2_x]

要求i>n才退出循环，即i\*![2^\{x\}][2_x]>n，题目可以转化为求循环次数x。    
根据对数函数和指数函数的关系：y=log**![a^\{x\}][a_x]** **![\\Leftrightarrow][Leftrightarrow]**   x=** ![a^\{y\}][a_y]**。 推出：log![2^\{n\}][2_n]<x，忽略**常数项2**，则得出时间复杂度为O(logn)。

--------------------

## **时间复杂度是O(n)的程序** ##

public static void linear(int n) {
            for(int i=0;i<n;i++){
                System.out.println(i);
            }
        }

**分析**

循环的次数取决于输入参数，所以时间复杂度是**O(n)。**

--------------------

## **时间复杂度是O(nlogn)的程序** ##

public static void nlog(int n) {
            int i=1;
            for (int j=0;j<n;j++){
                while (i > n) {
                    //求这里的时间复杂度。
                    i = i * 2;
                }
            }
        }

**分析**

内层循环在上面的实例中计算得出时间复杂度是O(logn)，外层循环n次，所以时间复杂度是O(nlogn)。

--------------------

## **时间复杂度是O (![n^\{2\}][n_2])的程序** ##

public static void sort(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {//循环arr.length - 1次
                for (int j = 0; j < arr.length - 1 - i; j++) {//循环arr.length - 1 - i次
                    if (arr[j] > arr[j + 1]) {
                        //临时变量接收大的值；
                        int temp = arr[j];
                        //把小的值放到前面；
                        arr[j] = arr[j + 1];
                        //把大的值放到后面。
                        arr[j + 1] = temp;
                    }
                }
            }
    }

**分析**

这是一个冒泡排序，很明显：

1.  外层循环次数是循环arr.length-1次；
2.  内层循环次数是循环arr.length-1-i次；
3.  如果设n=arr.length-1，则总循环次数是n(n-i)。

根据时间复杂度的概念，不包括低阶项和首项系数，则时间复杂度为**O(![n^\{2\}][n_2])**。

--------------------

# 总结 #

*  日常开发中要尽量避免循环嵌套，程序的优化目标要向O(1)接近；
 *  时间复杂度不只是计算运行次数，还要考虑网络请求（RPC，数据库连接等）的部分，网络请求的时间复杂度需要多次测试求平均响应时间。

[n_2]: https://latex.codecogs.com/gif.latex?n%5E%7B2%7D
[n_x]: https://latex.codecogs.com/gif.latex?n%5E%7Bx%7D
[2_x]: https://latex.codecogs.com/gif.latex?2%5E%7Bx%7D
[a_x]: https://private.codecogs.com/gif.latex?a%5E%7Bx%7D
[Leftrightarrow]: https://private.codecogs.com/gif.latex?%5CLeftrightarrow
[a_y]: https://private.codecogs.com/gif.latex?a%5E%7By%7D
[2_n]: https://latex.codecogs.com/gif.latex?2%5E%7Bn%7D