能否以Theta(log n)时间复杂度计算1到n的求和？

Great question! Even though the closed-form formula sum = n*(n+1)/2 gives us an optimal O(1) solution (way more efficient than Θ(log n)), it’s totally a fun practice exercise to build a Θ(log n) implementation—especially since the naive loop you shared runs in Θ(n) time.

The Θ(log n) Approach: Binary Multiplication #

The core of Θ(log n) algorithms is reducing the problem size by half at each step, which is exactly what binary multiplication does. Since the sum formula boils down to multiplying two numbers (n and n+1) then dividing by 2, we can implement that multiplication in Θ(log n) time instead of relying on built-in multiplication (which is optimized, but we’re doing this for practice!).

Here’s a sample C++ implementation that uses binary multiplication to get the sum:

long long binary_multiply(long long a, long long b) {
    long long result = 0;
    while (b > 0) {
        // Add a to result if the current bit of b is set
        if (b % 2 == 1) {
            result += a;
        }
        // Double a (equivalent to a left bit shift) and halve b (right bit shift)
        a *= 2;
        b /= 2;
    }
    return result;
}

long long sum_1_to_n(long long n) {
    long long product = binary_multiply(n, n + 1);
    // Either n or n+1 is even, so division by 2 will be an integer
    return product / 2;
}

Why This is Θ(log n) #

The binary_multiply loop runs exactly log2(b) times, which is Θ(log n) since b is n+1. Each iteration does constant-time operations (addition, multiplication/division by 2—these are just bitwise shifts under the hood for integers). The final division by 2 is a single constant-time step, so overall the whole function runs in Θ(log n) time.

A Common Pitfall: Divide-and-Conquer Gone Wrong #

You might initially think of splitting the sum into two halves (like 1 to mid and mid+1 to n) and recursively summing both, but that approach actually ends up being Θ(n) time. Let’s break it down: if your recursive function calls itself twice per step, the time complexity follows T(n) = 2T(n/2) + O(1), which by the Master Theorem gives Θ(n)—same as the naive loop. So that’s not what we want here.

Wrap-Up #

The binary multiplication method is the way to go for a true Θ(log n) implementation. It’s a great way to practice how logarithmic-time algorithms work by leveraging bitwise operations and problem reduction.

内容的提问来源于stack exchange，提问作者Hyungjoon Jeon