owned this note   changed 10 months ago  
Published Linked with GitHub

演算法

介紹

演算法不是程式語言。演算法是用來解決特定問題的方法與過程。

一個定義良好的計算方式，會包含單一，或一組完整的輸入，並且產生出一個值，或一組值作為輸出，如果所有輸出的值都是正確答案，則說明解決了問題。

例子

假設今天要解決一個問題是：「如何把芋頭和牛奶，做成芋頭牛奶」

  1. 將芋頭切塊蒸至熟透。
  2. 將芋泥蒸熟後先放入白糖攪拌均勻。
  3. 再放入奶油攪拌均勻，最後加入牛奶時再將芋頭壓成泥狀即完成。

可以說這3個步驟就是把芋頭和牛奶做成芋頭牛奶的一種演算法

為什麼要學演算法?

  • 學習演算法可以了解在不同規模下的表現和效率，性能通常決定了什麼是可行的，什麼是不可能的。
  • 透過學習算法，了解不同的思維，特別在離散的框架上，很多時候和一般思維下會有一些不同的看法，以及觀點。
  • 加強理論的實現，如果只懂理論，從來沒實作過，很容易會導致遇到問題的時候，根本不知道怎麼下手，或者使用了所謂的 "笨" 方法。

在電腦科學中有一條公式：

無所不能 ？

所謂的電腦，可不只單純是主機、筆電，具上述計算能力的最小單位就是一個晶片，而晶片早就被廣泛應用在我們生活之中，像是遙控器，手機，電視，火警，保全。
所以只要具備計算能力硬體在的地方我們就需要演算法，也因此有演算法可以改變世界之說。

電腦並不聰明，反而很笨，對，電腦超級笨，超級無敵笨!!!

根據三個特性，發明了一種方式叫做 Programming 把現實世界要解決的問題變成數學，丟給電腦來幫我們做運算，所以聰明的並不是電腦，而是背後的人用聰明的方式，讓其他人誤以為電腦很強大，很聰明。

演算法策略 (跳過)

https://hackmd.io/@HIPP0/HkYSwDwds

演算法優劣

常常聽到有人說，這個效率不好! 另外一個效率比較好，那到底怎麼來比較一個演算法的效率呢？

目標

  • 描述函數在極限中的行為方式。
  • 比較函數的 “大小” 的方法。
  • 如何表示算法的運行時間。
  • 判斷一個程式(做法)會不會 TLE
  • 透過測資反推所需的演算法效能

簡單方程比較

這邊簡單說一些常見的方程，在極限中的行為

非常重要的函數關係！！！！

指數函數 > 多項式函數 > 對數函數 > 常數函數

image

符號

然而描述一個函數有以下幾種方式 (但通常會直接用 big O 居多)

  • O-notation (big-o or o)
  • Ω-notation (big-omega)
  • Θ-notation
  • o-notation (little-o)
  • ω-notation (little-omega)

簡單一點的描述你可以看成

  • O ~ <=
  • Ω ~ >=
  • Θ ~ =
  • o ~ <
  • ω ~ >

所以當我們描述兩個方程 f, g 在趨近極限的狀況
f = O(g) 你就可以大致看成成 f <= g ，以此類推
接下來來進行比較嚴謹的定義

O-notation (big-o or o) ☆☆☆☆☆

O-notation（大O符號）描述了函數漸近行為的上限 (upper bound)：它表示一個函數的增長速度不會超過某個特定的速率。這個速率是基於最高次項的。

數學上的定義，若 f = O(g)，則存在一個常數 c > 0 使得當 N 夠大的時候，對於所有 n >= N，有 f(n) <= c(g(n))

舉例來說：

\(5x^2 + 3logx + x + 3\) = O(\(x^2\))
\(3e^x + 99x^{99}\) = O(\(e^x\))
\(3xlogx + 5x\) = O(\(3xlogx\))

推論題目效率需求

程式 (C++) 大概一秒跑 \(10^7 ~ 10^8\)

所以如果遇到 n = \(10^5\)，思考常見的函數

  • \(O(2^n)\) 很明顯不行
  • \(O(n^2)\) 不行因為 \(n^2\) = \(10^10\)
  • \(O(nlogn)\) 可以 \(nlogn\) = \(10^6\)
  • \(O(n)\) 可以
  • \(O(1)\) 肯定可以

例子

  • 判斷質數
  • 美麗島
  • 菜就多練
  • PPAP

常見演算法分析

\(O(n)\)




for (int i = 0 ; i < n ; i++) {
    // do something
}

O(\(n^2\))






for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < n ; j++) {
        // do something
    }
}

注意這裡是用 big-O ，所以以下情況也是 \(O(n^2)\)






for (int i = 0 ; i < n ; i++) {
    for (int j = i ; j < n ; j++) {
        // do something
    }
}

因為 \(\frac{1}{2}(n)(n+1)\) = \(O(n^2)\)

二分 (logn) 














int arr[5] = {1,2,3,4,5};
int left = 0, right = 5;
int target;
cin >> target;
while (left < right) {
    int mid = (left + right)/2;
    if (arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid;
    }
}
cout << "index = " << (left + right)/2;

為什麼二分會是 (logn)

假設區間大小是 n ，二分的時候每次都會讓區間大小縮小一半
第 1 次找: \(\frac{n}{2}\)
第 2 次找: \(\frac{n}{4}\)
\(....\)
第 k 次找: \(\frac{n}{2^k}\)
當 \(\frac{n}{2^k}\) 等於 1 的時候停止搜尋

所以得到
\(\frac{n}{2^k} = 1\)
\(k = log_2n = O(logn)\)

遞迴

簡單的可以直接看出來的 (讚!)
複雜遞迴: 可以使用 master theorem 來判斷
太複雜的??

輸入輸出問題

雖然複雜度可以估計，但實際上輸入輸出的時間也是耗費很大，所以為了避免掉這個問題，會使用，但基本上 CPE 不需要用也可以。

ios::snyc_with_stdio(false),cin.tie(0);

(畢竟如果卡了輸入輸出，就看不出演算法實際效率了，例如圖論題目，需要大量 node 以及 edge 的時候，通常輸入挺龐大的)

常見內建函數

  • memset O(N)
  • sort O(NlogN)
  • __gcd / gcd (c++17) O(logN)
  • lower_bound / upper_bound / equal_bound O(logN)
  • vector insert O(N) !!

練習

  • E001
Select a repo