舉例介紹
寫同樣的一段程式碼，別人的code卻比自己寫的code還要有效率，也就是跑得更快，為什麼呢?
其根本原因很可能出在演算法的問題上。
以 找出所有質數（Prime Numbers） 為例，不同的演算法效率差異巨大。以暴力解法來看:
#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 秒
總結來說，演算法是一組明確的步驟（指令），用來解決特定問題。其本質為解決問題的方法。
而好的演算法可以讓程式執行更快，這也是我們所追求的。
