编程珠玑第八章-算法设计技术

水深无声 2022-09-23 10:54 202阅读 0赞

首先思考一个问题，给定一个含有n个元素的vector，找出其中最大的子向量（即所有元素之和为最大值）。如果是都为正数，那么问题变得十分简单，整个vector即是最大子向量，但是如果是正数负数混合的形式呢？问题将变得复杂，接下来将简要介绍几种算法的思路。其复杂度由最初的立方算法降低到最终的线性算法!(提供的代码细节处如数据类型例如int之类自己根据情况填加)  
立方算法，思想很简单，即遍历所有情况：

maxfactor = 0;
    for (i = 0；i<n; i++)
    {
        for(j = i; j < n ; j++)
            sum = 0;
            for(k = i; k < j ; k++)
                sum += x[k];
            maxfactor = max(maxfactor,sum);//此处采用字符？：的形式更好
    }

其实不必每有一个\[i,j\]便重新求和一次，可以在遍历的过程中进行求和，因此，可以降低算法的复杂度为平方算法：

maxfactor = 0;
    for (i = 0；i<n; i++)
    {
        sum = 0;
        for(j = i; j < n ; j++)     
            sum += x[j];
            maxfactor = max(maxfactor,sum);
    }

使用常见的分治算法又可以进一步的降低算法的复杂度O(nlogn)：

float maxsum(1,u)
    {
        if 1 > u
            return -1;
        if 1 == u
            return max(0,u);
        return m = (1 + u)>>1;
        //the left
        leftmax = sum = 0;
        for(i = m ; i > 1 ; i--)
        {
            sum += x[i];
            leftmax = max(leftmax,sum);
        }
        //the right
        rightmax = sum = 0;
        for(i = m ; i < n ; i++)
        {
            sum += x[i];
            rightmax = max(rightmax,sum);
        }
        return max(leftmax+rightmax,maxsum(1,m),max(m+1,n));
    
    }

扫描算法，思路借鉴分治算法，不过使复杂度达到最低O(n)，即线性算法：

maxfactor = 0;
    maxending = 0;
    for (i = 0; i < n; i++)
    {
        maxending += x[i];
        maxending = max(maxending,0);
        maxfactor = max(maxfactor,maxending);
    }

注意：复杂度低的算法不意味着对于任何规模的问题，运行时间都低于复杂度高的算法，若通过画制时间曲线，会发现有一个拐点，在拐点处相等，规模越大，低复杂度算法的优势越明显。