算法复杂度分析

大O #

大O代表的是量级，表示的是随输入数据规模增大的变化趋势，T(n)表示程序的执行次数，当n规模足够大时，低阶、常量和系数引起的变化幅度很小，可以忽略不计

\( \begin{align*} & n = 10， 2n+2 = 22 \\ & n = 100，2n+2 = 202 \\ & n = 1000，2n+2 = 2002 \\ \end{align*} \)

如代码执行次数为T(2n+2)，时间复杂度可以直接表示为O(n)

当代码为串行代码时，复杂度相加；嵌套代码时，复杂度相乘。

常见复杂度 #

\( O(1) \lt O(log_2{n}) \lt O(n) \lt O(nlog_2{n}) \lt O(n^2) \lt O(2^n) \lt O(n!) \)

复杂度分析 #

分为最好、最坏、平均情况下的复杂度，考虑以下代码：

// n表示a数组的长度
int find(int[]a, int n, int x) {
    int pos = -1;
    for(int i=0;i<n;i++) {
        if a[i] == x {
            pos = i;
            break;
        }
    }
    return pos;
}

最好，第一个元素就找到，O(1)；最差，最后一个元素找到O(n)

平均，假设 x 一定存在于 a 中，每个位置出现的概率为1/n，平均比较次数：

\[ T(n) = \frac{1}{n} \cdot (1 + 2 + ... + n) = \sum_{i=1}^{n} \frac{1}{n}\cdot i = \frac{n+1}{2} \]

平均时间复杂度O(n)

如果 x 不一定存在于数组中，且存在概率为p，不存在概率为1−p，则分析需要乘以命中和未命中的概率加权求期望。 \( p \cdot \frac{n+1}{2} + (1-p) \cdot n = n - \frac{pn-p}{2}\)

递归 #

以下为求斐波那契数列的递归实现，非递归实现的版本可以在一个for循环遍历求得fib(n)，所以时间复杂度为O(n)

int fib(int n) {
    if n == 0 {
        return 0;
    }
    else if n == 1 {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

那递归版本的时间复杂度呢？可以借用递归树进行分析，将递归过程一层一层进行分解

Edit Edit this page