# 時間複雜度/二分搜 # 排序/資料結構 sprout-py 2021 --- 請問這個程式會執行多久？ ```py= for i in range(n): sum = sum + i print(sum) ``` --- ```py= for i in range(n): sum = sum + i print(sum) ``` | 指令 | 次數 | | ------------- | ----- | | next(i) | n - 1 | | sum = sum + i | n | | print(sum) | 1 | --- | 指令 | 次數 | 花費時間 | | ------------- | ----- | --- | | next(i) | n - 1 | c1 | | sum = sum + i | n | c2 | | print(sum) | 1 | c3 | 總共：$c1 \times (n - 1) + c2 \times n + c3$ --- 每個指令的執行速度不盡相同 且需要考量的點很多 (不同架構、快取...) 因此在評估程式的效能時 通常可以無視這之間的差距 --- | 指令 | 次數 | 花費時間 | | ------------- | ----- | --- | | next(i) | n - 1 | c1 | | sum = sum + i | n | c2 | | print(sum) | 1 | c3 | 總共：$(n - 1) + n + 1 = 2n$ --- 請問這個程式會執行多久？ ```py= for i in range(n): for j in range(n): sum = sum + i sum = sum + j ``` --- | 指令 | 次數 | | ------------- | ----------- | | next(i) | n - 1 | | next(j) | n * (n - 1) | | sum = sum + i | n * n | | sum = sum + j | n * n | --- 總共執行：$(n - 1) + n \times (n - 1) + n \times n + n \times n$ 也就是 $3n^2 - 1$ --- 比較一下這兩個多項式 $2n$ vs $3n^2 - 1$ 哪一個看起來比較大？ n 我要帶多少進去？ --- $100n + 1000$ vs $2^n + n$ n = 5? n = 12? --- 我們需要比較兩個多項式的漸進行為 因此衍生出了 Big-O 符號 --- ## Big-O $f(n) = O(g(n))$ 代表 $g(n)$ 是 $f(n)$ 的漸進上界 講白話一點就是 $f(n) = O(g(n))$ 代表當n夠大時 我們能找到一個常數 $c$ 使得 $c \times g(n)$ 大於 $f(n)$ --- 對於一個式子 我們取用次方數最高、n 很大時影響最大的項 並且將常數移除 當作時間複雜度 --- $3n + 2 => O(n)$ $3n^2 + 5n + 1 => O(n^2)$ $2^n + 5 => O(2^n)$ --- $2n => O(n)$ $3n^2 - 1 => O(n^2)$ --- How about this? ```py= for i in range(1, n + 1): for j in range(1, n - i + 2): sum = sum + i + j ``` --- ```py= for i in range(1, n + 1): for j in range(1, n - i + 2): sum = sum + i + j ``` $n + (n - 1) + (n - 2) + .... + 1 = \frac{(1 + n) \times n}{2} = \frac{n^2+n}{2}$ 時間複雜度：$O(n^2)$ --- How about this? ```py= for i in range(n + 1): sum = sum + i ``` vs ```py= sum = (1 + n) * n / 2 ``` --- 較差的時間複雜度在 $n$ 較小時 可能有較好的執行時間  --- 電腦一秒約可以做 $10^8$ 次基本運算 因此可以將程式的時間複雜度算出來 帶入數字判斷量級是否小於 $10^8$ --- 有經驗的人可以透過測資大小直接推算 題目要求的程式的時間複雜度大概是什麼 | N | 複雜度 | | --- | ------ | | $10$ | $O(n!)$ | | $20$ | $O(2^n\times n)$ | | $2000$ | $O(n^2)$ | | $10^5$ | $O(nlogn)$ | | $10^7$ | $O(n)$ | | $10^{18}$ | $O(1)$ | --- 嘗試估估看以前寫過的題目中 你的程式碼的時間複雜度是多少呢 neoj 3029 --- ```python= ls = list(map(int, input().split())) k = int(input()) for i in range(k): num = int(input()) if num in ls: print("YES") else: print("NO") ``` --- ```python= ls = input().split() k = int(input()) for i in range(k): num = input() if num in ls: print("YES") else: print("NO") ``` --- ## 基礎排序 --- ## 生活中的例子 - 一堆散落的紙有頁碼，我們想把它重新排成一本書。 - 要把學生的成績由大到小排序。 - ........ --- 給你一個長度為n的序列 你要把他們由小到大排序 --- ## Swap 先介紹基於比較、交換的算法。 ```python= a, b = b, a ``` --- ## Selection Sort - 在序列中找到最小的元素，並將他與第一個元素交換。 - 在序列中找到第二小的元素(也就是撇除掉第一個元素後的最小的元素)，並將他與第二個交換。 - 重複以上操作，直到排序好。 --- ## Selection Sort ```cpp def selection_sort(l): n = len(l) for i in range(n): mn = i for j in range(i+1, n): if l[j] < l[mn]: mn = j l[i], l[mn] = l[mn], l[i] ``` --- ## Bubble Sort - 從序列的最前面開始，一次比較陣列中兩兩相鄰的元素，然後根據將大的移到後面。 - 當我們比較過所有元素一次後，可以確保數值最大的元素在最後面。 - 接著扣掉陣列中的最後一個元素，接著重複上面的步驟進行兩兩比較。 --- ## Bubble Sort ```cpp def bubble_sorted(l): n = len(l) for i in range(n): for j in range(n - i - 1): if l[j] > l[j + 1]: l[j], l[j + 1] = l[j + 1], l[j] ``` --- ## Insertion Sort - 想像序列中有一部分是已經排序好的，那每次新增一個元素就去看他要插在排序好的序列的哪裡。 - 對於陣列中第 i 個值，假設 0 ~ i - 1 都排序好了，把 i 往左比較找到第一個小於他的元素並插在他右邊。 --- ## Insertion Sort ```python= def insertionSort(l): n = len(l) for i in range(n): key = l[i] j = i - 1 while j >= 0 and key < l[j]: l[j], l[j + 1] = l[j + 1], l[j] j -= 1 ``` --- ## Quick Sort [Quick Sort](http://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html) --- ## Merge Sort [Merge Sort](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html) --- ## 複雜度分析 - Bubble Sort - Best: $O(n^2)$, Worst $O(n^2)$ - Selection Sort - Best: $O(n^2)$, Worst $O(n^2)$ - Insertion Sort - Best: $O(n)$, Worst $O(n^2)$ - Quick Sort - Worst $O(n^2)$, Average $O(nlogn)$ - Merge Sort - $O(nlogn)$ --- 有複雜度比 $O(nlogn)$ 更好的排序方法嗎？ --- 基於比較的排序演算法最好就是 $O(nlogn)$ [優質文章](https://tmt514.github.io/algorithm-analysis/sorting/comparison-based-sorting.html#定理-18) --- n = 100 時 Bubble sort vs quick sort ? --- ## 不基於比較的排序方法 - Counting Sort - Bucket sort - radix sort --- ## Counting Sort - 假如數值介於 0 ~ 999，我們就開一個長度為1000的陣列去記每一種數字出現幾次。 - 最後由小到大輸出 --- ## (stabled) Counting Sort ```python= def countingSort(l): n = len(l) tmp = [0] * n cnt = [0] * 100 for i in range(0, n): cnt[l[i]] += 1 for i in range(100): cnt[i] += cnt[i - 1] i = n - 1 while i >= 0: tmp[cnt[l[i]] - 1] = l[i] cnt[l[i]] -= 1 i -= 1 for i in range(0, n): l[i] = tmp[i] ``` --- ## Counting Sort 時間複雜度是 $O(n)$ 嗎? --- ## Counting Sort k 為數字範圍 時間複雜度 $O(n + k)$ --- {%youtube kPRA0W1kECg %} --- ## 二分搜 --- 猜數字 1 ~ 100 中猜我想的數字 我會告訴你我想的比你猜多還大或小 請問我最小猜幾次能猜到 --- 猜數字 1 ~ 100 中猜我想的數字 我會告訴你我想的比你猜多還大或小 請問我最小猜幾次能保證猜到? --- 100, 50, 25, 13, 7, 4, 2, 1 --- 給你遞增數列 $[0, 1, 2, 3, 6, 8, 9, 10]$ 求 $2$ 在哪 從左到右掃過陣列是 $O(N)$ 沒有用到遞增數列的性質！ --- ### 觀察 $[0, 1, 2, 3, 6, 8, 9, 10]$ * 數字是升序的 --- $[?, ?, ?, [3], ?, ?, ?, ?]$ * 先問中間的數字 * 2 一定在 3 的左邊！ --- $[?, ?, ?, 3, X, X, X, X]$ --- $[?, [1], ?, 3, X, X, X, X]$ * 再問中間的數字 * 2 一定在 1 的右邊！ --- $[X, 1, ?, 3, X, X, X, X]$ --- $[X, 1, [2], 3, X, X, X, X]$ * 再問中間的數字... --- ```python def binary_search(arr, left, right, hkey): while left <= right: mid = left + (right - left) // 2 if arr[mid] == hkey: return mid elif arr[mid] < hkey: left = mid + 1 elif arr[mid] > hkey: right = mid - 1 return -1 } ``` --- 複雜度分析 $N$ 為序列長度 因為每一次可能的解答的集合都會減少一半 $N$ 一直除以$2$要除幾次才能等於 $1$ 因此複雜度為 $O(logN)$ --- ```python= from bisect import bisect_left def BinarySearch(a, x): i = bisect_left(a, x) if i != len(a) and a[i] == x: return i else: return -1 ``` --- 我們也可以利用二分搜的概念去逼近答案 Ex: 找一個數字開根號的值為多少 --- ```python= eps = 1e-9 def sqrt(n): l = 0 r = n while r - l >= eps: mid = (l + r) / 2 if mid * mid > n: r = mid else : l = mid return (l + r) / 2 ``` --- # 資料結構 --- ```python L = [1,2,3....] S = set(L) a in L a in S # 這兩個執行時間是一樣的嗎？ ``` --- ```python res = [i for i in range(100000000)] S = set(res) L = list(res) a = 99999999 a in S a in L ``` --- https://wiki.python.org/moin/TimeComplexity --- ## Queue - FIFO（First In First Out） - enqueue 放入 queue 的尾端 - dequeue 把 queue 中最前面的取出來  --- ```py= class Queue: def __init__(self): self.queue = [] def dequeue(self): char = self.queue[0] self.queue = self.queue[1:] return char def enqueue(self, char): self.queue.append(char) ``` --- 任何有排隊順序性的都有queue的框架在 - process queue - 訂單系統的 queue - ... --- ## Stack - FILO (First In Last Out) - push 把元素放在stack的最上面 - pop 把stack中最上面的元素取出來  --- ```python= class Stack: def __init__(self): self.stack = [] def pop(self): return self.stack.pop() def push(self, char): self.stack.append(char) ``` --- 遞迴 vs stack ```python= def fib(n): if n == 1 or n == 2: return 1 return fib(n - 1) + fib(n - 2) ``` --- | stack | | -------- | | x | | x | | x | | x | | x | | x | --- | stack | | -------- | | x | | x | | x | | x | | x | | fib(5) | --- | stack | | -------- | | x | | x | | x | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | fib(1) | | fib(2) | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | fib(2) | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | x | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | x | | x | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | fib(2) | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | x | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | fib(1) | | fib(2) | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | x | | fib(3) | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | x | | x | | fib(4) | | fib(5) | --- | stack | | -------- | | x | | x | | x | | x | | x | | fib(5) | --- | stack | | -------- | | x | | x | | x | | x | | x | | x | --- ## Linked-list  ---  --- linked list vs array | Operation | linked list | Array | | --------- | ----------- | ----- | | i-th | O(n) | O(1) | | insert afther i-th | O(1) | O(n) | | delete i-th | O(1) | O(n) | --- {%youtube pKO9UjSeLew %} ---