数据结构与算法(一):复杂度

数据结构与算法 2020-02-09 234 次浏览 本文字数:1767字

通过斐波那契数列引入复杂度

斐波那契数列的实现

算法一:

public static int fib1(int n) {         //复杂度:O(2^n)
    if (n <= 1) {
        return n;
    }else {
        return fib1(n - 2) + fib1(n - 1);
    }
}

算法二:

public static int fib2(int n) {          //复杂度:O(n)
    if (n <= 1) {
        return n;
    }
    int first = 0;
    int second = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

当n为46时,可以明显察觉到不同算法带来的性能差异:

性能差异展示

对于算法优劣的评估

1.正确性、 可读性、 健壮性(对不合理输入的反应能力)
2.时间复杂度:估算程序指令的执行次数(执行时间)
3.空间复杂度:估算所需占用的内存空间

计算一个算法的时间复杂度(简单Demo)

public static void test(int n) {       //此方法复杂度:1 + 2log2(n) + log2(n) * (1 + 3n)
    //外层循环复杂度:1 + log2(n) + log2(n)
    for (int i = 0; i < n; i += i) {   //i += i 等价为 i = i * 2 注意理解执行次数即为 1 * 2 * 2 * ... < n 求n
        //内层循环复杂度:1 + n + n + n = 1 + 3n
        for (int j = 0; j < n; j++) {
            System.out.println("Test");
        }
    }
}

大O表示法

  • 一般用大O表示法来描述复杂度,它表示的是数据规模n对应的复杂度
  • 忽略常数,系数,低阶:

    • 9 >> O(1)
    • 2n + 3 >> O(n)
    • n^2 + 2n + 3 >> O(n^2)
  • 注意:大O表示法仅仅是一种粗略的分析模型,是一种估算

常见复杂度

执行次数复杂度非正式术语
12O(1)常数阶
2n + 3O(n)线性阶
n^2 + 2n + 3O(n^2)平方阶
4log2(n) + 25O(logn)对数阶
3n + 2nlog3(n) + 15O(nlogn)nlogn阶
4n^3 + 3n^2 + 5O(n^3)立方阶
2^nO(2^n)指数阶
  1. 复杂度对比:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n ^3) < O(2^n) < O(n!) < O(n^n)
  2. 通过具体图像展示复杂度对比
    复杂度对比的图像展示

本文由 WarlockMarten 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。