“算法復(fù)雜度”——其實并沒有那么復(fù)雜

算法是用于解決特定問題的一系列的執(zhí)行步驟。使用不同算法，解決同一個問題，效率可能相差非常大。為了對算法的好壞進行評價，我們引入 “算法復(fù)雜度” 的概念。

package com.atangbiji;
public class Main {
  public static void main(String[] args) {    // 輸出通項F(n)    System.out.println(fib1(1));    System.out.println(fib1(2));    System.out.println(fib1(3));    System.out.println(fib1(4));    System.out.println(fib1(5));    System.out.println(fib2(70));  }  /*   * 求斐波那契數(shù)列（Fibonacci sequence）   * F(1)=1，F(xiàn)(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）的通項F(n).   */
  /*   *  方法一：遞歸法   *  最高支持 n = 92 ，否則超出 Long.MAX_VALUE   * @param n    * @return f(n)    * */  public static long fib1(int n) {    if (n < 1 || n > 92)          return 0;    if (n < 3)      return 1;    return fib1(n - 1) + fib1(n - 2);  }  /*   *  方法二：平推法   *  最高支持 n = 92 ，否則超出 Long.MAX_VALUE   * @param n    * @return f(n)    * */  public static long fib2(int n) {    if (n < 1 || n > 92)          return 0;
    //n:    1 2 3 4 5 ……    //F(n): 1 1 2 3 5 ……    long first = 1;    long second = 1;    for (int i = 3; i <= n; i++) {      long sum = first + second;      first = second;      second = sum;    }    return second;  }
}

• 正確性
• 可讀性
• 健壯性：對不合理輸入的反應(yīng)能力和處理能力。
• 時間復(fù)雜度（time complexity）： 估算程序指令的執(zhí)行次數(shù)（執(zhí)行時間）。
• 空間復(fù)雜度（space complexity）： 估算所需占用的存儲空間。

public static void test1(int n) {  //總執(zhí)行次數(shù) = 14  // 1（判斷語句可以忽略）  if (n > 10) {    System.out.println("n > 10");  } else if (n > 5) {    System.out.println("n > 5");  } else {    System.out.println("n <= 5");  }  // 1 + 4 + 4 + 4  for (int i = 0; i < 4; i++) {    System.out.println("test");  }}

public?static?void?test2(int?n)?{  //總執(zhí)行次數(shù) = 1 + 3n  //1 + n + n + n  for (int i = 0; i < n; i++) {    System.out.println("test");  }}

public static void test3(int n) {  //總執(zhí)行次數(shù) = 48n + 1  // 1 + 2n + n * (1 + 45)  for (int i = 0; i < n; i++) {    for (int j = 0; j < 15; j++) { // 1 + 15 + 15 + 15      System.out.println("test");    }  }}

public?static?void?test4(int?n)?{  //總執(zhí)行次數(shù) = 3n^2 +3n +1  // 1 + 2n + n * (1 + 3n)  for (int i = 0; i < n; i++) {    for (int j = 0; j < n; j++) { // 1 + n + n + n      System.out.println("test");    }  }}

public static void test5(int n) {  //總執(zhí)行次數(shù) = log2(n)  /*   * n = 2 , 執(zhí)行 1 次   * n = 4 , 執(zhí)行 2 次   * n = 8 , 執(zhí)行 3 次    * */  while ((n = n/2) > 0) { // 倍速減小    System.out.println("test"); // 只考慮這一句的執(zhí)行次數(shù)  }}

public?static?void?test6(int?n)?{  //總執(zhí)行次數(shù) = log5(n)  while ((n = n/5) > 0) {    System.out.println("test"); // 只考慮這一句的執(zhí)行次數(shù)  }}

public?static?void?test7(int?n)?{  //總執(zhí)行次數(shù) = 3n*log2(n) + 3log2(n) + 1  // 1 + 2 * log2(n) + log2(n) * (1 + 3n)  /*   * n = 2 , 執(zhí)行 1 次   * n = 4 , 執(zhí)行 2 次   * n = 8 , 執(zhí)行 3 次    * */  for (int i = 1; i < n; i += i) { // i = i + i = i * 2（倍速增大）    for (int j = 0; j < n; j++) { // 1 + n + n + n      System.out.println("test");    }  }}

大O表示法的性質(zhì)：

• （）
• （）
• （）

• 當(dāng)數(shù)據(jù)規(guī)模較小時， 各復(fù)雜度對應(yīng)的曲線如下圖所示。
  
• 當(dāng)數(shù)據(jù)規(guī)模較大時， 各復(fù)雜度對應(yīng)的曲線如下圖所示。

（1）遞歸法

public?static?long?fib1(int?n)?{  if (n < 1 || n > 92)        return 0;  if (n < 3)    return 1;  return fib1(n - 1) + fib1(n - 2);}

（2）平推法

public static long fib2(int n) {  if (n < 1 || n > 92)        return 0;  //n:    1 2 3 4 5 ……  //F(n): 1 1 2 3 5 ……  long first = 1;  long second = 1;  for (int i = 3; i <= n; i++) {    long sum = first + second;    first = second;    second = sum;  }  return second;}

有道無術(shù)，術(shù)可成；有術(shù)無道，止于術(shù)

歡迎大家關(guān)注Java之道公眾號

好文章，我在看??