算法设计中的时间小论

限制时空的循环左旋小节中描述了算法对程序的一方面影响:
好的算法思路会使程序更加简单。
这一回我们将会讲到另一方面: 复杂深奥的算法有时可以极大的提高程序性能。

1.简单问题与简单想法
问题来自一维空间的模式识别:
输入一串n个整数的向量,求其中任何连续子向量空间中的最大和情况。
如:

31 -41 59 26 -53 58 97 -93 -23 84
        2            6
ans is x[2..6] == 187

程序的输出应该为 187, 即 59+26-53+58+97

当然,我们稍一思索就有了简单答案:

A:
maxsofar = 0
for i = [0, n)
  for j = [i, n)
   sum = 0
    for k = [i,j]
    sum += x[k]
maxsofar = max(sum, maxsofar)

上面的算法对于每一个向量 x[i..j] 都求 sum(x[k]) (i<=k<=j)

2. 接下来的算法提取出了算法A中明显反复计算的部分

B:
maxsofar = 0
for i = [0, n)
  sum = 0
 for j = [i, n)
  sum += x[j]
 /* for every j, sum mean sum of x[i..j]*/
  maxsofar = max(maxsofar, sum)

显然下一种算法也是O(n^2)的

  cumarr[-1] = 0
 for i = [0, n)
  cumarr[i] = cumarr[i-1] + x[i]
maxsofar = 0
for i = [0, n)
for j = [i, n)
 sum = cumarr[j] - cummarr[i-1]
 maxsofar = max(maxsofar, sum)

3. 接下来采用分治算法,使时间复杂度降低至 O(nlogn)
该题分治思想:
对于一个向量x[i..j] 内最大子向量的求解,
事实上是对 x[i..(i+j)/2] 与 x[(i+j)/2 +1 .. j] ,
和 x[k .. l] (k>i, l < j )(即跨越中间界的最大子向量), 三个分问题的求解。

float maxsum3(l, u)
 if (l > u) return 0
 if (l == u) return max(0, x[l])
 m = (l + u) /2
 
 lmax = sum = 0
 for ( i = m; i>=1; i–)
     sum += x[i]
     lmax = max(lmax, sum)
  rmax = sum = 0
 for i = (m , u]
     sum += x[i]
   rmax = max(rmax, sum)
return max(lmax + rmax, maxsum3(l, m), maxsum3(m+1, u))

当然实际上该算法也有缺陷,速度达到O(nlogn), 分治时最空间的要求也会增加,数据量达到10W时,
分治时的栈操作过于频繁而且跳转频繁,事实上也不是一个理想的算法。

4. 对于从o(n^2)降到O(nlogn)的算法,我们仍然想对其继续优化,
扫描算法:
对于x[i .. j] 向量,从最左端扫描至最右端,我们可以确定的是,最优答案所处的位置,
要么包含在 x[i .. j] 中 (如 maxsofar), 要么和后面的向量衔接,必包含 x[j] (如maxendinghere)

  • ….
  • maxsofar
  • ….
  • maxendinghere
maxsofar = 0
maxendinghere = 0
for i = [0, n)
  maxendinghere = max(maxendinghere + x[i], 0)
  maxsofar = max(maxsofar, maxendinghere)

运行时间为O(n), 我们称其为线性算法, 到此已经优化到极致了。

背后的故事:
最早提出问题的是布朗大学Ulf Grenander 面对一个模式匹配的问题,最初形式是二维向量的模式匹配,
Grenander将其化简为一维以便深入了解分析。
Grenander首先设计了算法1和算法2,并在1977年叙述给Michael Shamos,
后者花了一通宵设计出算法3,当时人们一致认为已经是很好的算法了。
而后Shamos在CMU(卡内基梅隆大学)研讨会上介绍的该问题及其历史,
结果与会的统计学家 Jay Kadane 在一分钟之内就勾勒出算法4,还好不会有更快的算法了,
因为任何正确的算法都至少需要O(n)时间。

虽然一维问题得到了完美解决,二维的问题却迟迟没有解决,
《编程珠玑》上提到到第二版将发行时(08年),问题被提出了20年,所有已知的算法都被认为开销过大而没有实装。

此条目发表在C, 编程分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

邮箱地址不会被公开。 必填项已用*标注