2018年10月10日

這一節(jié)將以一個具體的算法題給出4種不同解法，分析各自的時間復(fù)雜度并比較其各自的運行性能。

給出兩個求和公式，以下分析中會用到：

最大子序列和問題

，求 的最大值。（為方便起見，若所有整數(shù)均為負(fù)數(shù)，則最大子序列和為0）。

例如：輸入 ，其最大子序列和為 。

1，時間復(fù)雜度為 的解法

    public static int maxSubSum1(int[] a) {
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int thisSum = 0;
                for (int k = i; k <= j; k++) {
                    thisSum += a[k];
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

該種解法最簡單暴力，定義子序列的起始位置為i，結(jié)束位置為j，假設(shè)數(shù)組a的長度為N，當(dāng) 時，，共N種情況，當(dāng) 時，，共N-1種情況，以此類推，當(dāng) 時，，僅此一種情況；將i與j之間的所有元素和記為thisSum，一旦thisSum的值比maxSum大，就更新maxSum的值為thisSum。

第一個循環(huán)大小為N，第二個循環(huán)大小為N-i，第三個循環(huán)大小為j-i+1，則總運行次數(shù)和為：

首先有：

接著：

那么：

所以該種解法的時間復(fù)雜度為

2，時間復(fù)雜度為 的解法

   public static int maxSubSum2(int[] a) {
       int maxSum = 0;
       for (int i = 0; i < a.length; i++) {
           int thisSum = 0;
           for (int j = i; j < a.length; j++) {
               thisSum += a[j];
               if (thisSum > maxSum) {
                   maxSum = thisSum;
               }
           }
       }
       return maxSum;
   }

在第一種解法中，拿掉最里面的那層循環(huán)，并稍做改動，就是現(xiàn)在的解法2。

其中第一層循環(huán)大小為N，第二層循環(huán)為N-i，則總運行次數(shù)為：

其中：

那么：

所以第二種解法的時間復(fù)雜度為

3，時間復(fù)雜度為 的解法

如下圖所示，可以將數(shù)組分為三部分，分別為前中后三部分。

最大子序列和就可能出現(xiàn)在這三個部分中，其中 ，前半部分是從start到mid這一部分的元素，即 ，所以該部分最大元素為11；后半部分是從mid+1到end這一部分的元素，即 ，所以該部分最大元素為13；而中間部分元素是以mid起始，分別向左和向右進行累加計算，分別求出其向左和向右部分的最大值，從mid向左得到其最大值：，而向右是從mid+1開始算起得到其最大值：，最后將左右兩部分和相加即為中間部分的最大值：；比較前中后部分的最大值，發(fā)現(xiàn)中間部分的值20最大，所以該數(shù)組最大啊子序列和為20。

那么在程序中如何實現(xiàn)呢？這就要采用分治策略，將數(shù)組a分為前后兩半子數(shù)組b,c，再將前半數(shù)組b分為前后兩半子數(shù)組d,e，后半數(shù)組c分為前后兩半子數(shù)組f,g，……，直到數(shù)組不能再分為止，此時子數(shù)組中就只有一個元素，一個元素就好判斷了，該元素為正就直接把該元素值返回給上一級子數(shù)組，為負(fù)就返回0，然后回到上一級子數(shù)組，將之前返回的前后部分子數(shù)組的最大值與中間部分最大值進行比較，得出其最大值，接著將最大值返回其上一級子數(shù)組，直至回到原數(shù)組，這時原數(shù)組就得到了前后部分子數(shù)組的最大值，接著求出中間部分子數(shù)組的最大值并與前后部分進行比較即可得到整個數(shù)組的最大子序列和。

public static int maxSubSum3(int[] a) {
        return a.length > 0 ? maxSumRec(a, 0, a.length - 1) : 0;
    }

    private static int maxSumRec(int[] a, int left, int right) {
        if (left == right) {
            if (a[left] > 0) {
                return a[left];
            } else {
                return 0;
            }
        }

        int center = (left + right) / 2;
        int maxLeftSum = maxSumRec(a, left, center);
        int maxRightSum = maxSumRec(a, center + 1, right);

        int maxLeftBorderSum = 0;
        int leftBorderSum = 0;
        for (int i = center; i >= left; i--) {
            leftBorderSum += a[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBorderSum;
            }
        }

        int maxRightBorderSum = 0;
        int rightBorderSum = 0;
        for (int i = center + 1; i <= right; i++) {
            rightBorderSum += a[i];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }

        return max3(maxLeftSum, maxRightSum,
                maxLeftBorderSum + maxRightBorderSum);
    }

    private static int max3(int a, int b, int c) {
        return a > b ? a > c ? a : c : b > c ? b : c;
    }

其中center為數(shù)組中間元素的下標(biāo)，maxLeftSum和maxRightSum分別為數(shù)組前后部分的最大值，maxLeftBorderSum為中間部分向左計算的最大值，maxRightBorderSum為中間部分向右計算最大值；maxLeftBorderSum + maxRightBorderSum即為中間部分的最大值。

計算中間部分，即計算maxLeftBorderSum和maxRightBorderSum總花費時間為 ，而計算前后兩半部分，即maxLeftSum和maxRightSum每個花費 個時間單元，則總共花費時間：

其中 ，則 ，，，。

那么當(dāng) ，則 ，忽略低階項，所以該方法的時間復(fù)雜度為：。

4，時間復(fù)雜度為 的解法

public static int maxSubSum4(int[] a) {
        int maxSum = 0;
        int thisSum = 0;

        for (int i = 0; i < a.length; i++) {
            thisSum += a[i];

            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {
                thisSum = 0;
            }
        }

        return maxSum;
    }

此種方法將時間復(fù)雜度優(yōu)化到了 ，只需一輪循環(huán)即可找到最大子序列；其思路為：若當(dāng)前子序列的和thisSum為負(fù)數(shù)，則將thisSum置為0，下一個數(shù)組元素作為新的子序列的起始位置，thisSum從該元素開始累加，直至找到最大子序列的和。

5，對比分析

使用下面代碼測試上述4中解法所消耗的時間：

public static void getTimingInfo(int n, int alg) {
        int[] test = new int[n];
        Random rand = new Random();

        long startTime = System.currentTimeMillis();
        long totalTime = 0;

        int i;
        for (i = 0; totalTime < 4000; i++) {
            for (int j = 0; j < test.length; j++) {
                test[j] = rand.nextInt(100) - 50;
            }
            switch (alg) {
                case 1:
                    maxSubSum1(test);
                    break;
                case 2:
                    maxSubSum2(test);
                    break;
                case 3:
                    maxSubSum3(test);
                    break;
                case 4:
                    maxSubSum4(test);
                    break;
                default:
            }

            totalTime = System.currentTimeMillis() - startTime;
        }
        System.out.print(String.format("\t%12.6f",
                (totalTime * 1000 / i) / (double) 1000000));
    }

    public static void main(String[] args) {
        for (int n = 100; n <= 1000000; n *= 10) {
            System.out.print(String.format("N = %7d", n));

            for (int alg = 1; alg <= 4; alg++) {
                if ((alg == 1 && n > 50000) || (alg == 2 && n > 500000)) {
                    System.out.print("\t      NA    ");
                    continue;
                }
                getTimingInfo(n, alg);
            }
            System.out.println();
        }
    }

運行結(jié)果如下圖，當(dāng)預(yù)測時間過長，將其設(shè)為NA，從圖中可以看出，不同時間復(fù)雜度的程序雖然得出的結(jié)果是一樣的，但運行性能相差巨大，猶如波音與摩拜的差別。

總結(jié)：以后寫代碼之前要多思考，避免一上來就暴力求解，造成巨大的性能開銷，應(yīng)盡量將程序優(yōu)化到線性階或線性對數(shù)階以內(nèi)。