时间复杂度

  1. 定义: 写O()来体现算法时间复杂度的记法，我们称之为大0记法。

  2. 推导大O阶方法:

    • 用常数1取代运行时间中的所有加法常数。
    • 在修改后的运行次数函数中，只保留最高阶项。
    • 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

  3. 各种阶:
    a: 常数阶O(1)
    O(3) = O(1)

    1
    2
    3
    int sum = 0, n = 100; /*执行一次*/
    sum = (1 + n) * n / 2; /*执行一次*/
    printf("%d",sum); /*执行一次*/

    b: 线性阶
    O(4 * n) = O(n)

    1
    2
    3
    4
    5
    int i; 
    for (int k= 0; k < 4; k++)
    for(i = 0; i < n; i++){
    /*时间复杂度为O(1)的程序步骤序列*/
    }

    c: 对数阶
    执行次数: 2^k = n; k = logn, 所以:O(logn)

    1
    2
    3
    4
    5
    int count = 1; 
    while (count < n){
      count = count * 2;
      /*时间复杂度为O(1)的程序步骤序列*/
    }

    d: 平方阶 O(n * n) = O(n^2)

    1
    2
    3
    4
    5
    6
    int i, j; 
    for(i = 0; i < n; i++){
    　　for(j = 0; j < n; j++){
        /*时间复杂度为O(1)的程序步骤序列*/
      　}
    }

    (n + (n - 1) + … + 1) = 1/2 * n^2 + n/2 = O(n^2)

    1
    2
    3
    4
    5
    6
    int i, j; 
    for(i = 0; i < n; i++){
    　　for(j = i; j < n; j++){ /*注意j = i而不是0*/
    　　/*时间复杂度为O(1)的程序步骤序列*/
    　　}
    }

    e: 立方阶
    (n-1) * 3 = O((n-1)^3) = O(n^3)

    1
    2
    3
    4
    5
    6
    int i, j; 
    for(i = 1; i < n; i++)
    for(j = 1; j < n; j++)
    for(k = 1; k < n; j++){
    /*时间复杂度为O(1)的程序步骤序列*/
    }
    1
    2
    3
    4
    5
    6
    int i, j; 
    for(i = 1; i < n; i++)
    for(j = 1; j < n; j++)
    for(k = 1; k < n; j++){
    /*时间复杂度为O(1)的程序步骤序列*/
    }
    1. 常见的时间复杂度:
      O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n!) < O(n^n)