為什么要學習數據結構與算法

1. 提到數據結構與算法大多數人的第一印象一定是復雜犀填、難學舵稠、工作用不到超升、面試還老問
2. 既然工作用不到為什么面試還總是問呢入宦，難道是為了故意刁難人？當然不是室琢，他是考察一個人是否具有長期發(fā)展?jié)摿Φ闹匾笜?就如同武俠秘籍里邊的內功心法一樣)
3. 在哪里有用到乾闰？操作系統(tǒng)內核，一些框架源碼盈滴，人工智能....
4. 是否應該學涯肩？ 如果想在計算機行業(yè)長久待下去 可以說是畢竟之路

如何評價一個算法的好壞

1. 事后統(tǒng)計法

• 即對于同一組輸入比較其最終的執(zhí)行時間

public static void main(String[] args) {
   Executors.execute(() -> sum(1000));
}
private static int sum(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}
 public static void execute(Executor execute) {
    if (Objects.isNull(execute)) { return; }
    long start = System.currentTimeMillis();
    execute.execute();
    long end = System.currentTimeMillis();
    long seconds = (start - end) / 1000;
    System.out.println("該算法行時長為：【 " + seconds + " 】秒");
 } 
 public interface Executor {
    /**
     * execute
     */
    void execute();
 }

此方法最大的特點就是簡單直觀，但卻存在以下弊端

1. 代碼的執(zhí)行時間嚴重依賴于硬件設備
2. 需要編寫一定量的代碼才能測算出其好壞
3. 難以保障測算公平性

2. 大O表示法(漸近分析)

• 特點
  1.他是在數據規(guī)模為n時的一種估算方法 如：O(n)等巢钓。
  2.大o表示法是一種粗略的估算模型病苗，能幫助我們快速了解一個算法的執(zhí)行效率
  2.忽略常數 系數
• 示例

1. O(n)

public static void print1(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(i);
    }
}

1. int i = 0; 復雜度 +1
2. i < n; 每執(zhí)行一次 +1 共需要+n次
3. i++; 每執(zhí)行一次 +1 共需要+n次
4. System.out.println(i); +n次
5. 1 + 3n 去掉常數以及系數
6. 復雜度： O(n)

2. O(n^2)

public static void print2(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(i);
        }
    }
}

1. 外層執(zhí)行次數 1 + 2n
2. 內層執(zhí)行次數 n * (1 + 3n)
3. 總工 1 + 2n + n * (1 + 3n) = 1 + 2n + n + 3n^2 = 1 + 3n + 3n^2
4. 復雜度: O(n^2)

3. O(logn)

 public static void print3(int n) {
    while ((n = n / 2) > 0) {
        System.out.println(n);
    }
}

1. 如果n 為 8 執(zhí)行次數為 3 即 2^3 = 8
2. 執(zhí)行次數為：log2(n)
3. 復雜度 logn

4. O(2^n)

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

1. 如果n為4
2. 需要調用 16次 函數
3. 復雜度為 2^n

5. O(nlogn)

  public static void print4(int n) {
    for (int i = 0; i < n; i *= 2) {
        for (int j = 0; j < 0; j ++) {
            System.out.println(j);
        }
    }
}

1. 1 + logn + logn + logn * (1 + 3n)
2. 1 + 3logn + 3n * logn
3. 復雜度為：O(nlogn)

6. O(1)

public static int add(int a, int b) {
    return a + b;
}

7. 斐波那契數 O(n)級別寫法

public static int fib1(int 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;
}
public static int fib2(int n) {
    if (n <= 1) { return n; }
    int first = 0;
    int second = 1;
    while (n-- > 1) {
        second += first;
        first = second - first;
    }
    return second;
}