算法时间复杂度

概述

衡量一个算法的好坏,最简单的标准就是他的时间复杂度。

算法的时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。

时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3).

一、时间频度

要理解时间复杂度,需要先理解时间频度,而时间频度简单的说,就是算法中语句的执行次数

举个例子:

要计算1+2+...+100,现在有两种算法

1
2
3
4
5
6
7
8
9
10
11
12
public int fun1(int n){
int total;
for(int i = 0; i <= n; i++){
total+=i;
}
return total;
}

public int fun2(int n){
int total = (1 + n)*n/2;
return total;
}

我们可以看见,对于fun1()这个方法,不管n多大,永远需要执行n+1次,也就是说他的时间频度是T(n)=n+1,

而对与fun2()来说,不管n多大都只需要执行1次,所以他的时间频度T(n)=1。

当n趋向无穷大时,有三个忽略

1.忽略常数项

比如T(n)=2n+1,当n趋向无穷大时,可以忽略常数项1;

参见下图:

  • 2n+20 和 2n 随着n 变大,执行曲线无限接近, 20可以忽略
  • 3n+10 和 3n 随着n 变大,执行曲线无限接近, 10可以忽略

2.忽略低次项

比如T(n)=2n+3n^8,当n趋向无穷大时,可以忽略低次项及其系数2n;

参见下图:

  • 2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
  • n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20

3.忽略系数

比如T(n)=2n^8,当n趋向无穷大时,可以忽略系数2。

参见下图:

  • 随着n值变大,5n^2+7n 和 3n^2 + 2n ,执行曲线重合, 说明 这种情况下, 5和3可以忽略。
  • 而n^3+5n 和 6n^3+4n ,执行曲线分离,说明多少次方式关键

二、时间复杂度

我们现在理解了时间频度的T(n)的含义,假设当有一个辅助函数f(n),使得当n趋近无穷大时,T(n)/f(n)的极限值为不等于0的常数,就叫f(n)为T(n)的同量级函数,记作T(n)=O(f(n)),

称O(f(n))为算法的时间渐进复杂度,也就是时间复杂度

又根据时间频度T(n)的“三个忽略”原则,我们可以知道时间复杂度是这样得到的:

  1. 忽略所有常数
  2. 只保留函数中的最高阶项
  3. 去掉最高阶项的系数

举个例子:

某算法T(n)=2n^3+4n-5,按步骤走:

  1. T(n)=2n^3+4n
  2. T(n)=2n^3
  3. T(n)=n^3

即可得该算法时间复杂度为O(n^3)

三、常见时间复杂度

这里按复杂度从低到高列举常见的时间复杂度:

  1. 常数阶O(1)

    1
    2
    3
    4
    // 无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1) 。
    public void fun(int n){
    n+=1;
    }
  2. 对数阶O(log2n)

    1
    2
    3
    4
    5
    6
    7
    // 根据公式有 n = 2^x,也就是 x = log2n,x即为循环代码执行次数,所以时间复杂度为O(log2n)
    public void fun(int n){
    int i = 1;
    while(i < n){
    i = i *2
    }
    }
  3. 线性阶O(n)

    1
    2
    3
    4
    5
    6
    // 一般来说,只要代码里只有一个循环结构,即输入规模和执行次数呈线性相关,那这个代码的时间复杂度就都是O(n) 。
    public void fun(int n){
    for(int i = 0; i < n; i++){
    n+=i;
    }
    }
  4. 线性对数阶O(nlogn)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 可以简单理解为对数阶的程序被放入了循环结构中,也就是n*O(logn),下面的代码的复杂度就是O(nlog2n)
    public void fun(int n){
    int j = 1;
    for(int i = 0; i < n; i++){
    while(i < n){
    j = j *2
    }
    }
    }
  5. 平方阶O(n²),立方阶O(n3),K次方阶O(nk)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 平方阶可以简单理解为线性阶中嵌套一个线性阶,也就是O(logn)*O(logn),下面的代码复杂度就是O(n^2)
    // 立方阶同理,就是三个线性阶的嵌套,K次方阶同理
    public void fun(int n){
    for(int i = 0; i < n; i++){
    for(int j = 0; j < n; i++){
    i=i+j;
    }
    }
    }

四、复杂度的四个概念

  1. 最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。
  2. 最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。
  3. 平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示
  4. 均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

举个例子:

长度为n的数组查找一个给定元素k

1
2
3
4
5
6
7
public void fun(int[] arr,int k){
for(int i = 0; i < arr.length; i++){
if(arr[i] == k){
//找到了
}
}
}

上面这个方法,最好的情况下元素k就在数组第一位,复杂度为O(1),但是最坏的情况下,元素k在数组最后一位,复杂度为O(n)。

同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,我们引入这4个概念,当然,在大多数时候我们是不用特意区分这四种情况的。

五、总结

总结一下如何快速判断程序的时间复杂度:

  • 只关注循环最多的那部分代码
  • 总复杂度等于量级最大的那段代码的复杂度
  • 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
0%