尋找總和為n的連續子數列之算法分析

看到有這麼道算法題在部落格園讨論，算法 eaglet 和 邀月

都已經設計出來了，花了點時間讀了下，學到點東西順便記錄下來吧。

題目是從1...n的數列中，找出總和為n的連續子數列。

這裡先設好算法中需要用到的關鍵變量：

• s：目标子數列的第一個元素
• k：目标子數列的長度

那麼目标子數列可以表示為(s, k)

1. naive算法(n^2)

最笨的，但是最容易的想到的方法，就是窮舉所有的子數列：

for s = 1 to n

for k = 1 to n-s+1

if sum(s, k) == n

output(s, k)

複雜度為：n + (n-1) + (n-2) + (n-3).... = n(n-1)/2

是以，其複雜度是O(n^2)

2. 用二分法改進的naive算法 (nlog2n)

我們需要充分利用輸入的特性，這裡，原始數列的一個很明顯的特點就是有序，而利用有序數列提高效率的最常用方法就是二分法。這裡我們可以注意到，針對某個子數列起始點s，我們沒有必要逐個長度的去求和判斷，而是利用其有序的性質，先求(s, (n+s)/2)的和。如果等于n則輸出，如果大于n，則數列結尾在前半段，否則在後半段：

　　low = s

　　high = n

　　while low < high

　　　　mid = (low + high)/2

　　　　sum = sum(s, mid)

　　　　if sum == n

output(s, mid)

　　　　else if(sum > n)

high = mid

　　　　else

low = mid

很明顯，此算法複雜度為O(nlog2n)

3. 利用規律s*k <= n而設計的算法 (nlnn)

我們知道，s是目标子數列的第一個元素，也是最小的元素，是以必然有sum(s,k) >= s*k， 也就是n>=s*k, 也就是k <= n/s，于是算法可以寫成：

　　for k = 1 to n/s

　　　　if sum(s, k) == n

output(s, k);

此處，其複雜度并不是顯而易見，但稍加分析：

複雜度 = n + n/2 + n/3 + n/4 + ... + n/n = n (1 + 1/2 + 1/3 + 1/4 + .. + 1/n)，可以注意到，括号中的部分是一個調和級數，其和為lnn。

于是，此算法的複雜度為 O(nlnn)，比算法2稍佳，因為lnn的底數要稍大些。

4. 利用規律s*k = n-k(k-1)/2而設計的算法(sqrt(n))

我們知道，對于子數列求和，其公式為：

n = k(s+ (s+k-1))/2 = s*k + k(k-1)/2

得出：

s*k = n - k(k-1)/2

由這個公式我們可以得到兩點資訊：

• 1*k <= s*k = n-k(k-1)/2，推出n-k(k-1)/2 >= k
• 如果n-k(k-1)/2能夠整除k，則k是目标子數列的長度，而起始點可以由公式算出：s = (n-k(k-1)/2)/k

于是，算法就可以以k為變量遞增，以n-k(k-1)/2 >= k為限制條件：

k = 1

v = n-k(k-1)/2

while v >= k

　　if v % k == 0

output(v/k, k) // 如果能整除，則找到解，并且起始點為v/k

　　k++

　　v = n-k(k-1)/2

分析複雜度，我們隻需關注k的變化，k是從1遞增到某個數結束，關鍵是如何求這個截止的k。

我們的循環結束條件是：

n-k(k-1)/2 >= k

化簡得到：

k^2 + k <= 2n

k^2 <=  2n - k

因為k > 0，于是有

k^2 < 2n

k < sqrt(2n)

是以，這個截止的k就應該是sqrt(2n)或者略小于它

到這裡，就不難看出其算法複雜度為O(sqrt(n)) - 略去常數因子和低階函數