1.测试运行时间、最大子列和计算

// 测试运行时间
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cmath>
usingnamespacestd;
voidprintN1(intn);
voidprintN2(intn);
floatff1(floatx);
floatff2(floatx);
floatcost(floatt,floatf(float));
intmain()
{
    constfloatx=1.1;
    cout<<"ff1"<<"运行结果："<<ff1(x)<<"   运行时间："<<cost(x,ff1)<<'s'<<endl;
    cout<<"ff2"<<"运行结果："<<ff2(x)<<"   运行时间："<<cost(x,ff2)<<'s'<<endl;
}
floatcost(floatt,float*f(float))
{
    clock_ts,e;
    floatcost;
    s=clock();
    f(t);
    e=clock();
    cost=(float)(s-e)/CLK_TCK;
    returncost;
}
voidprintN1(intn)            //递归算法涉及到程序的调用和程序状态的记录，会额外消耗空间
{                            //此时空间复杂度S(n)=c·n
    if(n>1)printN1(n-1);
    printf("%d\n",n);
}
voidprintN2(intn)
{                            //非递归算法中没有申请额外空间空间复杂度为常数级
    inti;
    for(i=0;i<n;i++)
    {
        printf("%d",i);
    }
}
floatff1(floatx)
{                            //for循环执行n次，pow函数中x进行i-1次乘法，即一次循环中执行i-1次乘法和1次除法
    floati,f=1;              //加减运算相对乘除运算较为简单，对计算机而言可会略不计
    for(i=1;i<=100;i++)f+=pow(x,i)/i;    //算法总计进行乘除法n*(1+n)/2，T(n)=O(n)
    returnf;
}
floatff2(floatx)
{
    floati,f=1.0/100.0;                  //for循环执行100次，每次进行2次乘除法
    for(i=100;i>1;i--)f=x*f+1.0/(i-1.0); //T(n)=O(n)
    f=f*x+1;
    returnf;
}

#include<cmath>
/*  给定N个整数的序列{A1,A2,…,AN}，求函数f(i,j)=max{0,∑ij(Ak)}的最大值  */
/*  算法1:T(N)=O(N^3)  */
    int MaxSubseqSum1(int A[],int N)    //将所有子列和都算出来
    {                             
        int ThisSum,MaxSum=0;
        int i,j,k;
        for(i=0;i<N;i++)
        {
            for(j=i;j<N;j++)
            {
                ThisSum=0;
                for(k=i;k<=j;k++)ThisSum+=A[k];         //实际上，在i相等的情况下，一轮j循环结束后进入下一个j的循环时
                if(ThisSum>MaxSum)MaxSum=ThisSum;       //只有最后一个元素是新增的，根本没有必要从i开始加
            }                                           //因此，k循环是完全多余的
        }
        return MaxSum;
    }
/*  算法2:T(N)=O(N^2) */
    int MaxSubseqSum2(int A[],int N)
    {
        int ThisSum,MaxSum=0;
        int i,j;
        for(i=0;i<N;i++)
        {
            ThisSum=0;
            for(j=i;j<N;j++)
            {
                ThisSum+=A[j];
                if(ThisSum>MaxSum)MaxSum=ThisSum;
            }
        }
        return MaxSum;
    }
/*  算法3:分而治之 */
/*  T(N)=2T(N/2)+cN,   T(1)=O(1)
        =2[2T(N/4)+cN/2]+cN
        =(2^k)*O(1)+ckN,    其中N/2^k=1
        =O(NlogN)   */
    int MaxSubseqSum3(int A[],int start,int end)
    {
        int mid=(end+start)/2,LeftSum,RightSum,lplusrSum,lMaxSum=0,rMaxSum=0,ThisSum=0;
        if(start==end)return A[mid];
        LeftSum=MaxSubseqSum3(A,start,mid);
        RightSum=MaxSubseqSum3(A,mid+1,end);
        for(int i=mid;i>=start;i--)
        {
            ThisSum+=A[i];
            if(ThisSum>lMaxSum)lMaxSum=ThisSum;
        }
        ThisSum=0;
        for(int i=mid+1;i<=end;i++)
        {
            ThisSum+=A[i];
            if(ThisSum>rMaxSum)rMaxSum=ThisSum;
        }
        lplusrSum=lMaxSum+rMaxSum;
        int outmax=(LeftSum>RightSum)?LeftSum:RightSum;
        return (outmax>lplusrSum)?outmax:lplusrSum;
    }

/*  算法4:在线处理  
    “在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方终止输入，算法都能给出正确解  */
/*  T(N)=O(N) */
    int MaxSubseqSum4(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;
    }

/* 分治法求最大子列和标准示例程序(来自浙江大学数据结构课程)*/

int Max3( int A, int B, int C )
{ /* 返回3个整数中的最大值 */
    return A > B ? A > C ? A : C : B > C ? B : C;
}

int DivideAndConquer( int List[], int left, int right )
{ /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
    int LeftBorderSum, RightBorderSum;
    int center, i;

    if( left == right )  { /* 递归的终止条件，子列只有1个数字 */
        if( List[left] > 0 )  return List[left];
        else return 0;
    }

    /* 下面是"分"的过程 */
    center = ( left + right ) / 2; /* 找到中分点 */
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    MaxRightSum = DivideAndConquer( List, center+1, right );

    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */

    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */

    /* 下面返回"治"的结果 */
    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}

int MaxSubseqSum3( int List[], int N )
{ /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer( List, 0, N-1 );
}