恋上数据结构与算法一（复杂度）

斐波那契数列

0 1 2 3 4 5 6 7 ... n
0 1 1 2 3 5 8 13 ... 求第n项值
除第一项和第二项，所有的数列的值都是前两数的和
f(n) = f(n-1) + f(n-2)

1. 递归方式 O(2^n)

public static int fib1(int n) {
   if (n <= 1) return n;
   return fib1(n - 1) + fib1(n - 2);
}

2. 可以从左到右顺序的求出每一项的值 O(n)

public static int fib2(int n) {
   if (n <= 1) return n;
   int first = 0;
   int second = 1;
   //第n项需要求n-1次
   for (int i = 0; i < n - 1; i++) {
      int sum = first + second;
      first = second;
      second = sum;
   }
   return second;
}

public static void main(String[] args) {
    System.out.println(fib1(0));
    System.out.println(fib1(1));
    System.out.println(fib1(2));
    System.out.println(fib2(64));
}

复杂度

时间复杂度：估算程序指令的执行次数（执行时间）
空间复杂度：估算所需占用的存储空间

• 大O表示法

一般用大O表示法来描述复杂度，表示数据规模n对应的复杂度，大O表示法仅仅是一种粗略的分析模型，是一种估算，帮助我们短时间内了解一个算法的执行效率

忽略常数、系数、低阶
复杂度比较 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)

屏幕快照 2020-07-07 下午5.17.16.png

工具对比复杂度大小 函数图像绘制工具

• 几个例子

public static void test2(int n) {
    // O(n)
    // 1 + 3n i=0执行一次 i++执行n次，i<n执行n次，println执行n次
    for (int i = 0; i < n; i++) {
        System.out.println("test");
    }
}

public static void test3(int n) {
    // 1 + 2n + n * (1 + 3n)
    // 1 + 2n + n + 3n^2
    // 3n^2 + 3n + 1
    // O(n^2)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println("test");
        }
    }
}

public static void test4(int n) {
    // 1 + 2n + n * (1 + 45)
    // 1 + 2n + 46n
    // 48n + 1
    // O(n)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 15; j++) {
            System.out.println("test");
        }
    }
}

public static void test5(int n) {
    // 8 = 2^3
    // 16 = 2^4
    // 3 = log2(8)
    // 4 = log2(16)
    // 执行次数 = log2(n)
    // O(logn)
    while ((n = n / 2) > 0) {
        System.out.println("test");
    }
}

//多个数据规模情况 O(n+k)
public static void test(int n, int k) {
    for (int i = 0; i < n; i++) {
        System.out.println("test");
    }
    for (int i = 0; i < k; i++) {
        System.out.println("test");
    }
}