Algorithm Outline

---

算法

---

• 定义
  有限指令集
  可接受输入
  产生输出
  步骤有限
  每条指令要求:
  1.有充分目标,无歧义
  2.在计算机的能力范围内
  3.不依赖计算机语言及具体实现
• 伪代码表示算法

void SelectionSort(int List[],int N)
{//将N个整数List[0]...List[N-1]进行非递减排序
    for ( i=0; i<N; i++ )
        MinPosition =ScanForMin( List, i, N-1);
        //从i到N-1中找到最小元,并将位置赋给MinPosition.
        Swap( List[i], List[MinPosition]);
        //将未排序部分的最小元素替换到有序部分的最后位置
}

---

好的算法

• 时间复杂度
  数量级最高不超过n²,并尽可能优化
• 空间复杂度
  不会造成内存溢出，少用递归

---

分析“二分法”查找

查找算法中的“二分法”是这样定义的：
给定N个从小到大排好序的整数序列List[],以及某待查找整数X,我们的目标是找到X在List中的下标。即若有List[i]=X,则返回i;否则返回-1表示没有找到。
二分法是先找到序列的中点List[M],与X进行比较,若相等则返回中点下标;否则,若List[M]>X,则在左边的子系列中查找X;若List[M]<X,则在右边的子系列中查找X。
试写出算法的伪码描述,并分析最坏、最好情况下的时间、空间复杂度。

---

int binary_search(int List[],int X)
{
    low=0;
    high=N;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(list[mid]==X)
            return mid;
        else if(X<list[mid])
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}

-时间复杂度
Tworst(n)=logn
Tbest(n)=1
S(n)=1

---

最大子列和问题

给定一个含N个随机正负整数的序列,求最大的子列和。

---

• 暴力求解法

int PlanA(int A[],int N)
{
    int ThisSum,MaxSum = 0;
    int i,j,k;
    for( i=0; i<N; i++ )
    {//子列的左端
        ThisSum = 0;
        for( j=i; j<N; j++ )
        {//子列的右端
            ThisSum += A[k];
            if(ThisSum>MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}

-时间复杂度
T(n^2)

---

• 递归分治法

-伪代码思路

int PlanB(int A[],int N)
{
    MaxLeft=MaxLeft(A,start,end);//计算左子列最大和
    MaxRight=MaxRight(A,start,end);//计算右子列最大和
    MaxMid=MaxMid(A,start,end);//跨越中线的子列最大和
    return Max(MaxLeft,MaxRight,MaxMid);//返回最大的子列和
}
int MaxLeft(int A,int start,int end)
{//左子列最大和
    MaxLeft=MaxLeft(A,start,end);//递归求左子列最大和
    MaxRight=MaxRight(A,start,end);//递归求右子列最大和
    MaxMid=MaxMid(A,start,end);//递归求跨越中线的子列最大和
    return Max(MaxLeft,MaxRight,MaxMid);
}
int MaxRight(int A,int start,int end)
{//右子列最大和
    MaxLeft=MaxLeft(A,start,end);//递归求左子列最大和
    MaxRight=MaxRight(A,start,end);//递归求右子列最大和
    MaxMid=MaxMid(A,start,end);//递归求跨越中线的子列最大和
    return Max(MaxLeft,MaxRight,MaxMid);
}
int MaxMid(int A,int start,int end)
{//跨越中线子列最大和
    MaxLAdd=MaxLAdd(A,start,end);//中线向左相加的最大和,至少一位
    MaxRAdd=MaxRAdd(A,start,end);//中线向右相加的最大和,至少一位
    return MaxLAdd+MaxRAdd;
}

-算法具体实现

int MaxSubseqSum(int A[],int start,int end);
int MaxSubseqSum_M(int A[],int start,int end);
int PlanB(int A[],int N)
{
    int MaxSum;
    MaxSum=MaxSubseqSum(A,0,N-1);//计算最大的子列和
    return MaxSum;
}
int MaxHalfSum(int A[],int mid,int end)
{//返回半边相加的最大和
    int i,j,Now,Max;
    Now=Max=0;
    if(mid==end) return A[mid];
    j=(mid<end)?1:-1
    for(i=mid;i!=end+j;i+=j)
    {   Now = Now+A[i];
        if(Now>Max)
            Max = Now;
    }
    return Max;
}
int MaxSubseqSum_M(int A[],int start,int end)
{//计算跨中线子列最大和
    int i;
    int MaxLAdd,MaxRAdd;
    MaxLAdd=MaxHalfSum(A,(start+end)/2,start);
    //中线向左最大和,至少一位
    MaxRAdd=MaxHalfSum(A,(start+end)/2+1,end);
    //中线向右最大和,至少一位
    return (MaxLAdd>MaxRAdd)?MaxLAdd:MaxRAdd;
}
int MaxSubseqSum(int A[],int start,int end)
{//计算最大的子列和
    int MaxLeft,MaxRight,MaxMid;
    if(start==end)
        retrun A[start];
    MaxLeft=MaxSubseqSum(A,start,(start+end)/2);//计算左子列最大和
    MaxRight=MaxSubseqSum(A,(start+end)/2+1,end);//计算右子列最大和
    MaxMid=MaxSubseqSum_M(A,start,end);//跨越中线的子列最大和
    return (MaxLeft>MaxRight)?
            ((MaxLeft>MaxMid)?MaxLeft:MaxMid):
            ((MaxRight>MaxMid)?MaxRight:MaxMid);//返回最大的子列和
}

-时间复杂度
T(N)=2T(N/2)+cN,T(1)=O(1)
 =2[2T(N/2^2^)+cN/2]+cN,N=N/2
 =2^k^ O(1)+ckN,N=N/2^k^=1,k=logN
 =O(NlogN)

---

• 在线处理法

int PlanC( int A[], int N )  
{   int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for( i = 0; i < N; i++ ) {
        ThisSum += A[i]; /* 向右累加 */
        if( ThisSum > MaxSum )
                MaxSum = ThisSum; /* 发现更大和则更新当前结果 */
        else if( ThisSum < 0 ) /* 如果当前子列和为负 */
                ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */
    }
    return MaxSum;  
}

-时间复杂度
T(N)=N

---