調和級數

簡介

調和級數 (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] << &#39; &#39;;
}

那這個時間複雜度是 $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)$ 的！