演算法前導

舉例介紹

寫同樣的一段程式碼，別人的code卻比自己寫的code還要有效率，也就是跑得更快，為什麼呢?

其根本原因很可能出在演算法的問題上。

以暴力解法來看:

#include <stdio.h>
#include <math.h>

// 判斷 n 是否為質數
int isPrime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

// 找出範圍內所有質數
void findPrimes(int limit) {
    for (int i = 2; i <= limit; i++) {
        if (isPrime(i))
            printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int limit = 100;
    findPrimes(limit);
    return 0;
}

• 我們運行一個由 2 到 n 之間的迴圈，並對迴圈的每個值，判斷它是不是質數。

其實，有更快的檢查方法，我們透過將程式碼改為for (int i = 2; i <= sqrt(n); i++)可以優化整個程式的速度，尤其是範圍很大時。

#include <stdio.h>
#include <math.h>

// 判斷 n 是否為質數
int isPrime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

// 找出範圍內所有質數
void findPrimes(int limit) {
    for (int i = 2; i <= limit; i++) {
        if (isPrime(i))
            printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int limit = 100;
    findPrimes(limit);
    return 0;
}

for (int i = 2; i <= sqrt(n); i++) 這種方法比 for (int i = 2; i < n; i++) 更快的根本原因在於：

• 如果 n 有因數，那麼它的最小因數必定小於等於 sqrt(n)。
• 超過 sqrt(n) 之後，所有的因數都是前面已經找到的因數的對應乘積，所以不需要再檢查。

舉例(n = 36):

所有的因數對：

(1, 36)
(2, 18)
(3, 12)
(4, 9)
(6, 6)   <-- √36 = 6，之後開始重複
(9, 4)   <-- 重複
(12, 3)  <-- 重複
(18, 2)  <-- 重複
(36, 1)  <-- 重複

觀察發現，當 i > 6 (sqrt(36) = 6) 之後，我們只是在重複檢查已經出現過的因數對，所以沒必要再繼續檢查！

只要檢查到 sqrt(n)，就能找到所有因數，沒必要再繼續迴圈。

• 另外補充一點，你也可以將程式碼寫為for (int i = 2; i * i <= n; i++)，其概念相同。

差異測試

如果我們要測試兩個程式碼執行時間上的差異，這個程式碼可以幫助我們：

#include <stdio.h>
#include <math.h>
#include <time.h>

// 方法 1：暴力法
int isPrimeBruteForce(int n) {
    if (n < 2) return 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

// 方法 2：sqrt(n) 優化
int isPrimeOptimized(int n) {
    if (n < 2) return 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

int main() {
    int limit = 1000000;
    clock_t start, end;
    double time_used;

    // 測試暴力法
    start = clock();
    for (int i = 2; i <= limit; i++)
        isPrimeBruteForce(i);
    end = clock();
    time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("暴力法耗時: %.6f 秒\n", time_used);

    // 測試 sqrt(n) 優化
    start = clock();
    for (int i = 2; i <= limit; i++)
        isPrimeOptimized(i);
    end = clock();
    time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("sqrt(n) 優化耗時: %.6f 秒\n", time_used);

    return 0;
}

輸出:

暴力法耗時: 76.019764 秒
sqrt(n) 優化耗時: 0.276063 秒

總結來說，演算法是一組明確的步驟（指令），用來解決特定問題。其本質為解決問題的方法。

而好的演算法可以讓程式執行更快，這也是我們所追求的。