时间复杂度的通俗讲法

时间频度：

一个算法花费的时间与算法中语句的执行次数成正比，我们将算法中的语句执行次数称为语句频度或时间频度，记为T(n)，n称为问题的规模.

在时间频度中，当n不断变化时，时间频度T(n)也会不断变化，但有时我们想知道随着问题的规模n的不断增加，运行时间呈现怎样的变化规律，为此，引入了时间复杂度.

时间复杂度：

• 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的时间复杂度.
• 数学上定义：存在大于0的常数C和非负整数n'，使得对于任意的n >= n'来说，T(n) <= C * f(n)，表示为T(n) = O(f(n));
• 简单来说：
  O(n²)表示当n很大的时候，复杂度约等于C * n²，C是某个常数;
  O(n)是说n很大的时候复杂度约等于C * n，C是某个常数.
• 例如，O(2n² + n + 1) = O (3n² + n + 3) = O (7n² + n) = O(n²)，一般都只用O(n²)表示就可以了.

时间复杂度n²比对

图中4条曲线分别表示4种不同的执行次数表达式，从图中可以看出，只要最高项的阶数相同，4种表达式值受其他项的影响很小，随着n增大，几乎可以忽略不计，甚至可以忽略与最高项相乘的常数

更通俗的讲：时间复杂度是T(n)中受n的变化影响最大的那一项(不包含系数)

最坏时间复杂度和平均时间复杂度

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会超过此时间.

常见时间复杂度

常数阶O(1)、对数阶O(log₂n)、线性阶O(n)、线性对数阶O(nlog₂n)、平方阶O(n²)、立方阶O(n³)、k次方阶(n)、指数阶O(2ⁿ)

常见时间复杂度比对图

从图中不难看出，选择算法时候应该尽量选择对数阶而非指数阶时间复杂度的算法.

常数阶O(1)

void func(int n) {
    printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
}

对数阶O(log₂n)

void func(int n) {
    for(int i = 1; i < n; i *= 2) { // 循环次数为 log₂n
        printf("Hello, World!\n"); // 循环体时间复杂度为 O(log₂n)
    }
}

线性阶O(n)

void func(int n) {
    for(int i = 0; i < n; i++) { // 循环次数为 n
        printf("Hello, World!\n"); // 循环体时间复杂度为 O(n)
    }
}

线性对数阶O(nlog₂n)

void func(int n) {
    for(int i = 0; i < n; i++) { // 循环次数为 n
        for(int j = 1; j < n; j *= 2) { // 循环次数为 log₂n
            printf("Hello, World!\n"); // 循环体时间复杂度为 O(nlog₂n)
        }
    }
}

平方阶O(n²)

void func(int n) {
    for(int i = 0; i < n; i++) { // 循环次数为 n
        for(int j = 0; j < n; j++) { // 循环次数为 n
            printf("Hello, World!\n"); // 循环体时间复杂度为 O(n²)
        }
    }
}