Big O Notation

Big O Notation是用來衡量Complexity的指標

1.Big O Notation

• The big O notation allows us to express complexity as a measure of its input size expressing complexity

• The complexity analysis is based on the worst case scenario, 只考慮worst case (最複雜的case)

• This express the complexity of an algorithm

  • Constant complexity

    • Hint: The complexity is based on the size of the input, the code takes the same time whatever the value of N, it uses the value of N, rather than use it as a size of input

  • O(N)

    • The complexity of an algorithm is O(N) if the time taken by the algorithm increases linearly when N increases

    • Hint: The number of operations obviously changes with the size of the input

  • O(N^2)

    • The complexity of an algorithm is O(N^2) if the time taken by the algorithm increases quadratically when N increases

    • Hint: Two nest loops will be of higher complexity, the complexity of this operation is O(N^2), as N changes quadratically.

• 當表達complexity時, 低位項以及常數項通常可以被忽略, 因為假設N非常大

• O(N^2 + 10000) is equivalent to O(N^2)

• O(N^2 + N) is equivalent to O(N^2)

2.Other cases (straight forward)

• 兩個迴圈, 一個是固定大小, 一個是用傳進來的參數n

  • O(N)

• 兩個迴圈, 分別是用傳進來的參數m, n

  • both m,n can be very large

    • O(N + M)

• 雙層迴圈, 分別是用傳進來的參數m, n

  • both m,n can be very large

  • O(N * M)

• 雙層迴圈, 用傳進來的參數n, 後面又有一個迴圈n

  • 只看最複雜的項

  • O(N^2)

3.Other cases (not straight forward)

• 雙層迴圈, 用傳進來的參數n, 外圈是1 ~ n, 內圈是n/2 ~ n

  public static void doublingLoopVariable(int n) {
      for (int i = 0; i < n) {
          System.out.println("Value of i is: " + i);
          i = i * 2;
      }
  }

  • N * N/2 = O(N^2)

• i在迴圈中改變

  • 每次i都會是之前的兩倍: 1, 2, 4, 8..., i的成長等同於2^i

  • There is some number "k" for which

    2 ^ k = N

  • Let's derive this, the value of "i" doubles at every iteration

    2 ^ k = N
    log2(2 ^ K) = log2 N
    K * log2 2 = log2 N
    K = log2 N