3. 算法效率

同一个问题的不同算法在性能上的比较，现在的方法主要是算法时间复杂度。算法效率是算法操作（operate)或处理(treat)数据的重复次数最小。

例题选自《编程珠玑》第8章，算法设计技术。

这个问题是一维模式识别（人工智能）中的一个问题。

输入有n个元素的向量，输出连续子向量中的最大和。向量是数学的概念，用数组表示向量，输出连续元素序列和的最大值。问题的关键是元素允许负值，若不允许负值，最大和是数组，规定所有元素是负数时，子向量最大和定义为0。

一维数组d[0..9]={31,-41,59,26,-53,58,97,-93,-23,84}。子向量最大和d[2..6]的和，187。

需要解决的关键问题是明晰子向量d[i,,j]的边界(i,j)，怎么将数组分组。因此不同的方法组成不同的算法。主要有三次方或二次方算法，分治法--树形算法，O(n)算法。

3.1 三次方与二次方算法

(1)三次方算法。对任意0<=i<=j<=n，(i,j) 是子向量d[i..j]的边界。因此，数据分组的方法是，根据所有(i,j)明晰的一个子向量d[i,j]，计算d[i,j]中元素的和，比较所有子向量的和(称为数据分组)，求出最大值。

边界i的范围{0,...,n-1}，用一个循环表示, 边界j的范围{i,...,n-1}, 用第二层循环表示. 对两层循环明晰的一个子向量d[i..j] 计算元素的和, 用第三层循环表示. 因此算法有三层循环, 每一层循环最多n的一次方, 算法是三次方算法.

program1 

        maxsofar=0

        for  i=[0,n)

            for