daily Programming: BIG O

Big O time is the language and metric we use to describe the efficiency of algorithms. Not understanding it thoroughly can really hurt you in developing an algorithm. Not only might you be hudged harshly for not really understanding big O, but you will also struggle to judge when your alogorithm is getting gaster or slower.

Gayle Laakmann McDowell, Cracking the Coding Interview, 6th Edition 189 Programming Questions and Solutions

開~ 紮馬步，紮了一整個禮拜

還是要好好面對著個 XDD 之前工作的時候都自動忽略 (我不是本科系的拉~ 沒差~拉……)

Time Complexity

• Electronic Transfer: O(s)

  • s 指檔案大小，檔案越大，傳輸時間越長

• Airplane Transfer: O(1)

  • 有考慮慮到檔案大小，但時間是固定的 不會 因為檔案越大時間越長

Best Case, Worst Case, and Expected Case

• 書用 quickSort 來當解釋範例

  • [比基準值小的數] 基準值 (pivot) [比基準值大的數]

Best Case

• 整個array的數值都一樣，只會花上 O(N) 的時間，整個array只會刷一次~~ YA~~ (你以為可以天天過年這麼好運? XDD)

Worst Case

• 帶賽狀態，每次隨機挑都挑到最大 XDD，就會花上 O(N*N) 的時間，哭哭~~~ (實際上蠻常帶賽的 XDD)

Expected Case

• 正所謂中庸之道~ 行走江湖就是要看得開~ 通常來說不會遇到最極端的兩個情況，預期所執行的時間就會是 O(N log N)

Space Complexity

• Space complexity is a parallel concept to time complexity.

  • O(n): create an array of size n

  • O(n*n): two-dimentional array of size n x n

• Take O(n) time and O(n) space

  • Recursive calls

       int sum(int n){
          if (n <= 0) {
             return 0;
          }
          return n + sum(n-1);
       }
  

  • Each call adds a level to the stack

      sum(4)
        -> sum(3)
          -> sum(2)
            -> sum(1)
              -> sum(0)
  

• O(n) time and O(1) space

int pairSumSequence(int n) {
   int sum = 0;
   for (int i = 0; i < n; i++) {
       sum += pairSum(i, i + 1);
   }
   return sum;
}

int pairSum(int a, int b) {
   return a + b;
}