# 時間複雜度 > 上一篇文章　[物件導向程式設計](https://hackmd.io/vhoWABf4SXmBTn9P8v2BtA) > 下一篇文章　[簡單演算法-排序](https://hackmd.io/AbLO_6vkTiq63tKrp-L7_w) > 先備知識　　[數學上的時間複雜度](https://mycollegenotebook.medium.com/%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-%E6%BC%B8%E9%80%B2%E5%87%BD%E6%95%B8-397ca19cdc4c)/[葬送的芙莉蓮](https://ani.gamer.com.tw/animeVideo.php?sn=35241) > 延伸閱讀　　[埃拉托斯特尼筛法时间复杂度的证明](https://blog.csdn.net/qaqwqaqwq/article/details/123828657)/[用樹狀圖來做時間複雜度分析](https://mycollegenotebook.medium.com/時間複雜度-遞迴-上-f6d51a462394)/[master theorem](https://mycollegenotebook.medium.com/時間複雜度-遞迴-下-master-th-307ad4608ab6) --- ## <font size=6>前言</font><br> 恭喜你學完了進階的Python語法了 :fireworks: ，努力過的人都是戰士 。接下來你將要學習到雜七雜八的演算法，也就是學習要如何用特定方法來解決一項問題。**但在學習演算法之前，你需要先學會評價它**。以下是個評估演算法的範例。 > ### 範例1： 在已經排序好的數列中找到特定數字 > 我想要在 `1 21 38 49 500 679 7138 8879 9879 10123` 中找到 `8879` > :::success > ### 每次找都切一半 > 把數列剖半一次，找到 `500` 。 > `500`< `8879` ，因為數列有經過排序，所以我們知道`500` 左邊的數字也都小於 `8879`。 > 我們把他們都從可能性中踢除，使得數列剩下 `679 7138 8879 9879 10123`。 > > 再把數列剖半一次，找到 `8879`。 噫！好誒！我中了！ > > **找尋步數：2** > ::: > :::danger > ### 從頭一個一個去找 > ~~1~~ → ~~21~~ → ~~38~~ → ~~49~~ → ~~500~~ → ~~679~~ → ~~7138~~ → 8879 > > **尋找步數：8** > ::: 當我們用時間來當作評價標準時，使用第一種方法尋找數字比第二種快多了。因此我們會給第一種方法較高的評價。 那評價演算法的目的到底是什麼呢？第二種方法不是也能解題嗎？我們之所以會要求演算法要夠快，是因為在打各種程式競賽時，那些競賽都會將程式執行時間限時（超出時限會產生 Time Limit Error, TLE）。當時間限制較短時，你就要去評估哪種演算法比較快，他所需要的時間能不能低於時間限制？再來決定我要不要用它。 **評估演算法所需要花費的時間，我們就將它稱作時間複雜度分析。** :::spoiler **註**（點我展開） 1. 演算法 == 解決問題的方法 2. 我們在評估程式時間時，要評估的是程式最大的執行時間。這是因為有些噁心的程式題目都會用很噁心的測資，讓你程式跑超久。就連海塔都噁心到了! ::: ## <font size=6>要如何求得程式的時間複雜度</font><br> 前面介紹了時間複雜度的功用到底是甚麼，接下來要來說明時間複雜度要如何量化。 ### 現在我要利用前面提到的 範例1 來說明時間複雜度要如何量化 > ### 範例1： 在已經排序好的數列中從頭一個一個去找特定數字 > 在 `1 21 38 49 500 679 7138 8879 9879 10123` 中找到 `8879` > ~~1~~ → ~~21~~ → ~~38~~ → ~~49~~ → ~~500~~ → ~~679~~ → ~~7138~~ → 8879 > > **尋找步數：8** ### 我們一步一步來推倒此範例的時間複雜度 1. 範例1中找到 `8879` 所需要的尋找步數為 `8` 2. 如果今天我們要找的數字不是 `8879` ， 而是 `10123` ， 我們的尋找步數就會變成 `10` ， 也就是這個數列的長度。 3. 我們在數列 `1 21 38 49 500 679 7138 8879 9879 10123` 中，尋找一個特定數字 `x` 的時候，尋找步數最高就是這個數列的長度 `10`。 4. 當數列長度為 `n` 的時候，我尋找特定數字 `x` 所需要的步數最高就是 `n`。 5. 因此，該範例的時間複雜度為 `n` 6. 我們把時間複雜度符號化，記作 `O(n)` :::spoiler **什麼是 O(f(n))**（點我展開） 當我資料長度為 `n` 時 ， 我處理它所要花費的最長時間是 `f(n)` > **example1** `O(n^2)` 代表資料長度為 `n` 時 ， 我處理它所要花費的最長時間是 `n^2` > **example2** `O(log(n))` 代表資料長度為 `n` 時 ， 我處理它所要花費的最長時間是 `log(n)` > [!CAUTION]注意! > 此處的定義並不嚴謹，要看嚴謹的 O(f(n)) 定義，[請見](https://mycollegenotebook.medium.com/%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-%E6%BC%B8%E9%80%B2%E5%87%BD%E6%95%B8-397ca19cdc4c) ::: ### 接下來，我會用程式碼再解釋一遍 範例1 的時間複雜度 >### 範例1程式碼 > ```python= > arr = [1, 21, 38, 49, 500, 679, 7138, 8879, 9879, 10123]　#數列 > count = 0 #計算迴圈總共跑了幾次 > x = 31453 #要尋找的特定數字 > for elm in arr: > count+=1 > if x == elm: > break > > print(count) > ``` > **Output |** `10` 在上述程式碼中，我將特定數字 `x` 的數值改為 `31453`；並且我宣告了 `count` 來計算該迴圈總共跑了多少次。沒意外也不會出意外，因為 `x` 並不在數列中所以迴圈會跑到底，**`count` 的數值就會等於數列長度**。 **`count` 最多為多少(也就是迴圈跑的次數)，迴圈的時間複雜度就是多少。** 所以上述範例的時間複雜度就是`O(n)`。 ### 接下來用另一個範例讓你明白該如何判斷迴圈以及遞迴的時間複雜度吧! > ### 範例2： 階層的時間複雜度 > 在看這篇文章的你，應該會知道 `n! = 1*2*3*4*...*n` 吧!不知道也沒關係，現在你知道了吧! > 用膝蓋想也知道，如果我要求 `n!` ，因為我要一項一項去乘，所以我的時間複雜度就是 `O(n)`，不信我用程式跑給你看。 >> ### 用迴圈來跑階層 >> ```python= >> n = 5 >> nLevel = 1 >> count = 0 >> >> for i in range(1,n+1): >> count+=1 >> nLevel*=i >> >> print("count: {} nLevel: {}".format(count,nLevel)) >> ``` >> **Output |** `count: 5 nLevel: 120` > >> ### 用遞迴來跑階層 >> ```python= >> def getLevel(i,count): >> count+=1 >> print("count: {}".format(count)) >> >> if (i <= 1): >> return 1 >> >> else: >> return i*getLevel(i-1,count) >> >>n = 5 >>nLevel = 1 >>count = 0 >> >>nLevel = getLevel(n,count) >> >> print("nLevel: {}".format(nLevel)) >>``` >> **Output** >> ``` >> count: 1 >> count: 2 >> count: 3 >> count: 4 >> count: 5 >> nLevel: 120 >> ``` --- ## <font size=6>經典例題：尋找質數的時間複雜度</font><br> 尋找質數是一個常見的問題，而**不同的解法會影響計算的速度**。有些方法很慢，需要很多時間才能找到答案，而有些方法則快很多。 ### 我們來看看不同的方法，並分析它們的時間複雜度。 > ### 範例3：判斷數字`n`是不是質數 >> ### 方法1: 窮舉法 >> 尋找質數最直觀的做法就是窮舉法。當我們要判斷一個數`n`是否為質數時，從 `2` 開始，一個一個檢查有沒有數字能整除`n`。如果都沒有，就代表`n`只能被 `1` 和 `n` 本身整除，也就是說`n`是質數。 >> >> ### 程式碼 >> ```python= >> def is_prime(n): >> if n < 2: # n 如果是 0 1 或是負數，它就不會是質數 >> return False >> >> for i in range(2, n): # 從 2 到 n-1 >> if n % i == 0: # 如果 n 可以被 i 整除，代表 n 不是質數 >> return False >> >> return True # 找不到因數，代表 n 為質數 >> ``` >> ### 時間複雜度分析 >> • 在最壞的情況下（例如 `n = 101`），我們需要從 `2` 檢查到 `100`，所以最多需要 `n-2 ≈ O(n)` 次計算。 >> • 時間複雜度為 `O(n)`，這樣的方法碰上太大的 `n` 會執行緩慢。 > >> ### 方法2: 開根號法 >> 窮舉法的問題是我們檢查了太多數字，其實我們不需要檢查到 n-1，只要檢查到 n 的平方根（√n）就夠了！為什麼呢？ >> - 如果 n 不是質數，那麼它一定可以寫成兩個數的乘積：`n = a*b` >> - `a` 與 `b` 其中至少有一個數小於等於 `√n`，否則 `a` 和 `b` 兩個都大於 `√n`，那麼 `a × b` 會比 `n` 還要大，這是不可能的！ >> >> 所以我們只需要檢查從 2 到 √n 的數字，如果 n 沒有被這些數整除，那它就是質數。 >> >> ### 程式碼 >> ```python= >> import math >> >> def is_prime_sqrt(n): >> if n < 2: >> return False >> for i in range(2, int(math.sqrt(n)) + 1): # 只檢查到 √n >> if n % i == 0: >> return False >> return True >> ``` >> ### 時間複雜度分析 >> 經過開根號後，我們最多只需要檢查到 `√n`，因此計算次數從 `O(n)` 降到了 `O(√n)`。 ### 這個範例只需要判斷數字 `n` 是否為質數對吧！所以複雜度分別會是 `O(n)`與 `O(√n)`。 讓我稍微來改個題目 > ### 範例4： 多筆數字的質數判斷 > ``` > q > test1 > test2 > . > . > . > testq > ``` > 第一行 `q` 代表在接下來 `q` 行中，每一行都會輸入任意數字，其範圍為 `1~n`，請判斷這些數字是否為質數 > >> ### 方法1: 窮舉法 >> 藉由上一個範例我們知道窮舉法每求一個數字，其時間複雜度會是 `O(n)`，那麼求 `q` 個數字就直接在前面乘上 `q` ， 也就是 `O(q*n)` > >> ### 方法2: 開根號法 >> 也是藉由上一個範例我們知道開根號法每求一個數字，其時間複雜度會是 `O(√n)`，那麼求 `q` 個數字就直接在前面乘上 `q` ， 也就是 `O(q*√n)` ### 當我把題目修改為判斷 `q` 個數字是否為質數，其複雜度分別會變成 `O(q*n)`與 `O(q*√n)`。 在這邊補充一個觀念，在程式OJ(online judge)中你用 Python 去跑程式，當時間限制為 `1s`，代表程式大約可以跑 `1*10^6` 行（如果你沒有用 file input/output 等等很花時間的功能的話啦。 假設今天我的 `q = n = 10^5` ， OJ 給你的時限為 `10s`，你會發現**兩種做法都會超時**： - 窮舉法 `O(q*n) = 10^10` > `10^7` - 開根號法 `O(q*√n) = 10^7.5` > `10^7` ### 來建立個質數表格吧～ 如果我們先建立一個 `1~n` 內的質數表格，之後我們就可以用這個表格來判斷數字是否為質數，這樣只要查表就能判斷此數字是否為質數了。也就是說我的時間複雜度就是建立表格的時間 `O(f(n))` + 判斷 `q` 個數字所需要的時間 `O(q)`。 **加總過後就是 `O(q+f(n))`**。我現在只要把建立表格時間`O(f(n))`縮小，就能在 `10s`內跑完程式了。 > ### 範例4： 多筆數字的質數判斷 > ``` > q > test1 > test2 > . > . > . > testq > ``` > 第一行 `q` 代表在接下來 `q` 行中，每一行都會輸入任意數字，其範圍為 `1~n`，請判斷這些數字是否為質數 > >> ### 建立表格-埃拉托色尼篩法 >> **讓我們來一步步找到 `1~n` 之間的所有質數。** >> >> - 先建立一個數列 `[2, 3, 4, ..., n]`，假設所有數都是質數。 >> - 從最小的數開始，如果它是質數，就把它所有的倍數都劃掉（假設質數`b`倍數的是`a*b`，因為它為兩數相乘，所以一定是合數）。 >>- 繼續往後找，找到下一個沒被劃掉的數，這個數就是質數，再把它的倍數都劃掉。 >>- 持續執行這個動作，直到所有數都被標記。 >> >> **所有步驟轉成動畫就會像這樣子** >> ![Sieve of Eratosthenes](https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif) >> >>### 程式碼 >>```python= >>def sieve(n): >> isPrime = [True] * (n + 1) # 建立一個長度為 n+1 的布林陣列 >> isPrime[0] = isPrime[1] = False # 0 和 1 不是質數 >> >> for i in range(2, int(math.sqrt(n)) + 1): # 只需檢查到 √n (你可以用開根號法想想為何只要檢查到 √n) >> if isPrime[i]: # 如果 i 是質數 >> for j in range(i * 2, n + 1, i): # 把 i 的倍數都標記為 False >> isPrime[j] = False >> >> return isPrime # 回傳質數判斷布林陣列 >>``` >>:::spoiler **程式碼補充解釋**（點我展開） >>**1. 解釋一下第二行中的布林陣列 `isPrime`** >>- `isPrime[i] = True` 代表 `i` 為質數 >>- `isPrime[i] = False` 代表 `i` 不是質數 >> >>**2. 第七行的 `for` 迴圈其實可以從 `i*i` 開始跑，而不用從 `2*i` 開始** >>魔法觀察力比芙莉蓮還敏銳的你可能發現，第七行 `for` 迴圈是要把 `i` 的倍數標為**非質數**，會不會有些數字被重複標記到？ >>當我在標記 `5` 的倍數時，`2*5` `3*5` `4*5` 早就被前面的 `2` `3` 標記過了，因此我不需要再標註一次。所以我直接從 `5*5` 開始去找倍數。 >>經過改正後，其實只有很少部分數字會被避免重複標記到就是了。像是 `30` 還是會被 `2 3 5` 給重複標記。 >>::: >>### 時間複雜度分析 >>建立質數表的時間按照上面的雙重迴圈你可以得到`[n/2]+[n/3]+[n/5]...+[n/√n]`，這邊告訴你這個數字加總後，他的時間複雜度是 `O(n log log n)`。至於為什麼，你可能要去看看[《埃拉托斯特尼筛法时间复杂度的证明》](https://blog.csdn.net/qaqwqaqwq/article/details/123828657)。 >> >>我們得到建立質數表所需的時間後，要再加上 `q` ，因為**範例4**中，要判斷 `q` 個數字是否為質數。最後，得到**時間複雜度是 `O(q+n log log n)`**。 >> >>比起 `O(q*√n)` ，先建立質數表更適合 `q` & `n` 都很大的情況。 > >>### 建立表格-線性篩法 >>前面提到建立表格的方法的問題在於，它會讓同一個數字可能被多個質數標記多次，導致額外的運算。(`40` 這個數字同時是 `2` & `5` 兩個數字的倍數，所以會被**標記兩次**不是質數)。那要如何確保每個數只會被標記一次呢? >> >>**你應該學過要如何把數字做質因數分解吧!** >>`1734=2*3*17^2` >>現在我重複一個動作 ==把最小質因數去掉== ，直到得到質數 >>- 將 `1734=2*3*17^2` 中，最小的質數 `2` 去掉，變成 `867=3*17^2` >>- 將 `867=3*17^2` 中，最小的質數 `3` 去掉，變成 `289=17*17` >>- 將 `289=17*17` 中，最小的質數 `17` 去掉，變成 `17=17` >> >>最後得到 質數`17` ，這個過程可以畫成一條線 `17` <- `289` <- `867` <- `1734` >> >>**讓我把 `2-13` 的數字都做相同處理** >>![1.drawio](https://hackmd.io/_uploads/Bk2R9oc3kg.png =50%x) >> >> >>如此一來，所有的合數都指向唯一一個數字，像是 `2 <- 4` >>我們在求此關係圖時，是從右邊一直除最小質因數直到左邊對吧! >> >>**如果今天我們能夠，由左邊推到右邊的話**(紅色 代表合數 綠色 代表質數) >>![linear](https://hackmd.io/_uploads/HJLSIhqn1l.gif =50%x) >> >>可以發現，我從根據此關係圖去一步一步跑，每個數字只會被標記到底是合數還是質數一次而已 >> >>**問題來了，我們知道數字`a`從右邊往左邊推就直接除掉`a`的最小質因數就好，但是要如何從左邊推倒到右邊呢?** >>魔法是個想像的世界，想像一下，剛剛圖片中每個數字往左邊都只有一個對應數字，但往右邊去看，卻不只一個數字，有甚麼方法可以正確列舉每個數字往右一個的所有對應數字呢? >>> **範例 `45`的右邊有哪些數字?** >>> 我們用逆推導的方式來去求。 `45 = 3^2*5` >>> - 假設，有個數字質因數分解為`k*3^2*5`，他往左推是 `45` >>> - `3^2*5` <- `k*3^2*5`。 >>> - 這代表`k` 為 `k 3 5` 中最小的質因數，那麼我就知道`k<=3`，而且是質數。也就是說 `k=2 or 3` >>> >>>`45` 往右推就是 `2*45` `3*45` 這兩個數字了 >> >>### 程式碼 >>1. 初始化一個 `is_prime` 陣列，假設所有數都是質數。 >>2. 建立一個 `primes` 陣列，用來存放篩選出的質數。 >>3. 從 `2` 開始遍歷所有數字，如果 `is_prime[i]` 為 `True`，則 `i` 是質數，加入 `primes` 陣列。 >>4. 對於每個質數 `p`，標記所有 `p` 的倍數不是質數，但我們只標記 `p * primes[j] ≤ n`，確保每個合數只被最小的質因數標記一次。 >>5. 重複這個過程，直到遍歷完整個範圍。 >> >>```python= >>def linear_sieve(n): >> is_prime = [True] * (n + 1) # 預設所有數都是質數 >> primes = [] # 用來存放篩選出的質數 >> >> for i in range(2, n + 1): >> if is_prime[i]: # 如果 i 是質數 >> primes.append(i) >> >> for p in primes: >> if i * p > n: # 超過範圍就停止 >> break >> is_prime[i * p] = False # 標記合數 >> if i % p == 0: # 確保每個數只被最小的質因數標記一次 >> break >> >> return primes # 回傳所有篩選出的質數 >>``` >>:::spoiler **程式碼補充解釋**（點我展開） >>**1. `is_prime` 陣列** >>這個陣列用來標記哪些數是質數，初始化時所有數都設為 `True`，但當發現一個數是合數時，就把它改成 `False`。 >> >>**2. `primes` 陣列** >>這是用來儲存當前質數的陣列，例如 `i = 10` 時， `primes = [2, 3, 5, 7]`。當迴圈結束，理所當然 `primes`會是`<=n`的所有質數表。 >>::: >>### 時間複雜度分析 >>每個數只會被標記一次：每個合數 x 只會被它的最小質因數 p 標記一次，不會被其他更大的質因數重複標記。也就是說複雜度為 `O(n)`。還要加上詢問`q`次數字的時間，所以為 `O(n+q)` ### 在範例4中，四種質數篩法時間複雜度 回到先前的假設`q = n = 10^5` ， OJ 給你的時限為 `10s`，也就是說大約可以跑 `10*10^6`行。 | 方法 | 時間複雜度 | `q = n = 10^5` | 超時 | | -------------- | --------------------- | -------------- | ------------------ | | 窮舉法 | `O(q*n)` | `10^10` | 超時 | | 開根號法 | `O(q*√n)` | `10^7.5` | 超時 | | 埃拉托色尼篩法 | `O(q+n(log (log n)))` | `3.4*10^5` | 噫！好誒！我過了！ | | 線性篩 | `O(q+n)` | `2*10^5` | 噫！好誒！我過了！ | :::spoiler **註**（點我展開） log(n) 在此處以 自然對數`e` 為底。至於為什麼，again[《埃拉托斯特尼筛法时间复杂度的证明》](https://blog.csdn.net/qaqwqaqwq/article/details/123828657)。 ::: --- > 上一篇文章　[物件導向程式設計](https://hackmd.io/vhoWABf4SXmBTn9P8v2BtA) > 下一篇文章　[簡單演算法-排序](https://hackmd.io/AbLO_6vkTiq63tKrp-L7_w) > 先備知識　　[數學上的時間複雜度](https://mycollegenotebook.medium.com/%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-%E6%BC%B8%E9%80%B2%E5%87%BD%E6%95%B8-397ca19cdc4c)/[葬送的芙莉蓮](https://ani.gamer.com.tw/animeVideo.php?sn=35241) > 延伸閱讀　　[埃拉托斯特尼筛法时间复杂度的证明](https://blog.csdn.net/qaqwqaqwq/article/details/123828657)/[用樹狀圖來做時間複雜度分析](https://mycollegenotebook.medium.com/時間複雜度-遞迴-上-f6d51a462394)/[master theorem](https://mycollegenotebook.medium.com/時間複雜度-遞迴-下-master-th-307ad4608ab6) > 觀念是非題　[時間複雜度觀念是非題](https://docs.google.com/forms/d/e/1FAIpQLSeDLV0Ridv1n-ycI4en6v4tk_OAVhUk0NhIHRD_0QvaSO1Rpw/viewform?usp=header)