# Week 4
###### tags: `C++`

[TOC]

## 時間複雜度 Time Complexity

### 意義
* 判斷一段程式能否在規定的時間內跑完
* 比較不同算法做同樣工作的速度

### 範例
1. 計算$2^n$的時間複雜度
方法一：一個一個乘 => n次
方法二：拆一半 => $log_2n$

2. 100n vs 200n
100n = f(n)
200n = g(n)
若f(n)/g(n)在n趨近無限大時趨近於0，則f(n) < g(n)，反之亦然
否則兩者一樣量級

### Big O Notation
#### 定義
f(n), g(n)
g(n)乘上某個數字c
使cg(n)永遠在f(n)上方

f(n) 屬於 O(g(n))
f(n) = 10n
> it cant get much worst than this

#### Big-theta notation
取最緊的上限
去掉低次向和係數

#### 常見複雜度
* Constant O(1)
* Linear time O(n)
* Logarithmic time O(nlogn)
* Quadratic timeL O($n^2$)

一個算法的時間複雜度為O(f(n))
=> 最差狀況的時間複雜度為${\theta}(f(n))$

### 計算
* n => 輸入的大小
* 陣列 => 陣列的大小
* 字串 => 字串的長度
#### O(1)
* 假設所有運算的時間都一樣
* 輸入為n 效率不會隨n變大改變

int n;
n = 1;
n = n+1*2;

#### O($n$)

for(int i = 0; i < n; i++){
    // constant time code
}

#### O($n^2$)

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        // constant time code
    }
}

#### 內建函式複雜度

sort(a, a+m)
=> O($mlogm$)

#### 例題：Stack Problem

## 前綴和

題目練習

### A - Kuriyama Mirai's Stones