---
# System prepended metadata

title: 演算法簡易整理
tags: [LeetCode, Algorithm]

---

###### 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)

![](https://i.imgur.com/dhT6fOL.png)


### 常見實際評估範例

#### O(1)

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

```csharp=
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)

```csharp=

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)

```csharp=
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)

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


```csharp=

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次，下述一個簡單明瞭的例子

```csharp=
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




## 關於空間複雜度

### 簡述