###### tags: `Algorithm` `LeetCode`

# 演算法簡易整理

近期開始與朋友刷題，稍微複習以前沒學好的演算法基礎

## 關於時間複雜度

### 簡述

簡單來說就是執行一段程式碼所需耗費時間，較不科普的講法就是用一個數學函式去定義執行時間，基本上都用會用大O符號表示。

大O(BigO)在數學裡又稱為漸進符號，用來描述一個函式數量等級的漸進上界。這邊稍微舉個維基百科的例子，例如一個函式數

f(n) = n^2 + 3n

當n特別大的時候，3n比起第一項相對來說就會小很多，因此對於這個函數，在n趨近於無窮大時，與n^2漸進等價，我們可以將原本的f(n)=n^2+3n記做

f(n)~n^2

為什麼會提到BigO? 因為實際上我們不會去看電腦實際跑的時間式多少來決定效能，每台硬體狀況不同。因此會使用數學BigO去預測評估實際的執行時間上是多少。[不過時間複雜度標記法完全忽略了程式語言特性和平台特性](https://reurl.cc/yeZyd6)。同個算法有可能用 C 寫執行較快，用 Java 、 Python 寫執行較慢。所以時間複雜度也只是粗估的參考數值而已。

這邊稍微列一下常見的[時間複雜度列表](https://reurl.cc/EZKZnn)


### 常見實際評估範例

#### O(1)

n不管輸入多少，都不會影響實際執行時間

void PrintConsole(string msg) {
  printf(msg);
}

[常見情境](https://reurl.cc/n5zzZ6)
- Accessing Array Index (int a = ARR[5];)
- Inserting a node in Linked List
- Pushing and Poping on Stack
- Insertion and Removal from Queue
- Finding out the parent or left/right child of a node in a tree stored in Array
- Jumping to Next/Previous element in Doubly Linked List

#### O(n)

隨著n量越大，耗費時間越多，輸入n 會被for迴圈n 次，故時間複雜度寫作：O(n^2)

int[] numbers = [1,2,3,4,5]

int TotalSum(int[] numbers){
    int sum = 0;
    for(i=0;i<=number.length;i++){
        sum+=number[i];
    }
    return sum;
}

[常見情境](https://reurl.cc/n5zzZ6)
- Traversing an array
- Traversing a linked list
- Linear Search
- Deletion of a specific element in a Linked List (Not sorted)
- Comparing two strings
- Checking for Palindrome
- Counting/Bucket Sort and here too you can find a million more such examples....

#### O(n^2)

輸入nums 會被for迴圈做 n*n 次(兩個O(n)的for)，時間複雜度寫作：O(n^2)

public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];             
    for(int i=0; i<nums.length ; i++){             
        for(int j=1+i; j<nums.length; j++){
            if(nums[i]+nums[j]==target){
                result[0]=i;
                result[1]=j;
                return result;  
            }            
        }            
    }
        return result;  
}

[常見情境](https://reurl.cc/n5zzZ6)
- Bubble Sort
- Insertion Sort
- Selection Sort
- Traversing a simple 2D array

#### O(log n)

當迴圈為非線性迴圈時，複雜度成指數型成長，典型例子如下

float x = 100;

while (x > 0) {  
   x = x/2;  
}  

| Iteration | x | Calculate |
| -------- | -------- | -------- |
| 0 | 100 | 100
| 1 | 50 | x = 100/2
| 2 | 25 | x = 50/2
| 3 | 12.5 | x = 25/2
| .. | .. | ...
| n | x/n^2 | x =

歸納

| Iteration | x |
| -------- | -------- |
| 0 | x |
| 1 | x/2 |
| 2 | x/4 |
| 3 | x/8 |
| .. | .. |
| n | x/n^2 |

x/n^2 = 1

n^2 = x 兩邊取log

n = log(x)

[常見情境](https://reurl.cc/n5zzZ6)
- [Binary Search](https://reurl.cc/EZ7gpa)
- Finding largest/smallest number in a binary search tree
- Certain Divide and Conquer Algorithms based on Linear functionality
- Calculating Fibonacci Numbers - Best Method The basic premise here is NOT using the - complete data, and reducing the problem size with every iteration

#### O(n log n)

可以視為log n 做了 n次，下述一個簡單明瞭的例子

int n = 100
// Executed n times, so O(n)
for(int i = 0; i < n; i++) 
{
    //Executed O(log n) times
    for(int j = n; j > 0; j/=2)
    {

    }
}

[常見情境](https://reurl.cc/n5zzZ6)

- Merge Sort
- Heap Sort
- Quick Sort
- Certain Divide and Conquer Algorithms based on optimizing O(n^2) algorithms

## 關於空間複雜度

### 簡述