簡介#
調和級數 (Harmonic Series) 是一個數學級數，其通項為 \(1/n\)，也就是：
$$
1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots
$$
不過這邊要介紹的是他在時間複雜度中的應用，最長出現在因倍數相關的題目中。
例題#
請你求 \(1 \sim n\) 裡面所有數，它有幾個正因數，如 \(12\) 有 \(1, 2, 3, 4, 6, 12\)，所以答案是 \(6\)。
首先，我們可以對於每個數，然後在它之中的數枚舉，如果整除就將答案加一。
int n;
int fac[n+1];
cin >> n; // 輸入 n
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if ((i % j) == 0) { // 整除
fac[i]++;
}
}
}
for (int i = 1; i <= n; i++) {
cout << fac[i] << ' ';
}
那這個時間複雜度是 \(O(n^2)\)。
接著是另一個方法，我們枚舉所有數，然後對於 \(n\) 以內，是它的倍數的都將答案加一。
int n;
int fac[n+1];
cin >> n; // 輸入 n
for (int i = 1; i <= n; i++) { // 枚舉因數
for (int j = i; j <= n; j+= i) {
fac[j] ++; // 枚舉倍數
}
}
for (int i = 1; i <= n; i++) {
cout << fac[i] << ' ';
}
那這個時間複雜度看似是 \(O(n^2)\)，但仔細觀察，會是 \(n + (n/2) + (n/3) +… + (n/n)\)，根據調和級數的性質，這個和其實是 \(O(n \log n)\) 的！
