「数据结构」课堂笔记2.21

本节课主要记录了三个问题
1.关于李泽龙的题目（求相邻和最大数）
2.关于张世龙的题目（能否提升空间复杂度从而降低空间复杂度）
3.关于郑龙同学的题目（时间复杂度的计算）（细讲）

个人认为还是直播有画面好些，能有思路

求相邻和最大数

相邻和最大数在我们mooc中有四种算法，我们先全搬出来。

题目

主要看第1·2·4方法吧，第三种后面会讲递归思想，到时候回来看。

第一种方法（添加了主代码）

#include <stdio.h>
#include <stdlib.h>
int MaxSubseqSum1( int A[],int N);

int main()
{   
    int sum,n,i;
    scanf("%d",&n);
    int A[n];
    for(i=0;i<=n-1;i++){
        scanf("%d",A[i]);
    }
    MaxSubseqSum1(A,n);
    return 0;
}

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++){
/*本段作用对比A[j]到结尾上最大的数*/
            ThisSum=0;
            for(k=i;k<= j;k++)
                ThisSum +=A[k];
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
        }
    }
    return MaxSum;
}
/*第一个方法太啰嗦，不解释，
第二个就能看懂，从第二个开始看吧；
*/

第二种方法

int MaxSubseqSum2(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[j];
            if(ThisSum>MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}
/*第二个方法是：先对比以第一个数开头最大的，
再对比第二个数开头最大的，以此类推。每遇到比之前记录到更大的
就记录在MaxSum中。*/

第三种方法

/*第三个方法分而治之——本课程后面应该会学到————看看就好（本段代码不是那么严谨，习惯性用了java 的方法，意思懂了就好，真有需求我改一改。。）*/
int MaxSubseqSum3(int A[],int N)
{
    return DAR(nums,0,N-1);
}
int DAR(int[] A,int left,int right)//Divide and rule 分而治之
{
    if (left == right) return nums[left];

    int p = (left + right) / 2;

    int leftSum = DAR(nums, left, p);
    int rightSum = DAR(nums, p + 1, right);
    int crossSum = crossSum(nums, left, right, p);

    return Math.max(Math.max(leftSum, rightSum), crossSum);
}

public int crossSum(int[] nums, int left, int right, int p) {
    if (left == right) return nums[left];

    int leftSubsum = Integer.MIN_VALUE;
    int currSum = 0;
    for(int i = p; i > left - 1; --i) {
      currSum += nums[i];
      leftSubsum = Math.max(leftSubsum, currSum);
    }

    int rightSubsum = Integer.MIN_VALUE;
    currSum = 0;
    for(int i = p + 1; i < right + 1; ++i) {
      currSum += nums[i];
      rightSubsum = Math.max(rightSubsum, currSum);
    }

    return leftSubsum + rightSubsum;
  }

第四种方法

/*第四种方法在线处理，
在线的意思就是没输入一个数据即时处理
这是一种思想，
我们这道题计算了每个位置数开头后累加
直到这个位置开头的数字小于0以至于
后面部分加上后会更小，
然后开始下一个位置开头后的累加和
对比第二种方法，把每个位置往后全部计算
我们减少了逻辑上无效的数据，即增加了边界，减少了时间复杂度*/
int MaxSubseqSum4(int A[],int N)
{
    int ThisSum,MaxSum;
    int i;
    ThisSum = MaxSum = 0;/*最大值做初始边界为0*/
    for( i = 0; i<N;i++){
        ThisSum += A[i];/*从第i+1个数向右累加*/
        if(ThisSum>Maxsum)/*当累加和大于保存的最大值*/
            MaxSum = ThisSum;/*则，更新保存的最大值*/
        else if(ThisSum<0)/*当累加和<0*/
            ThisSum = 0;/*丢弃这个数，因为后面部分加上比不加大。*/
    }
}

提升空间复杂度降低时间复杂度

提的问题有点超纲，我也不太懂写了白写。。

有兴趣的话，看俺的算法ABC的笔记里面有一定的涉及。

---

时间复杂度计算

我们要计算时间复杂度当然要先了解时间复杂度。
时间复杂度：

抄书
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
语句的总执行时间或时间度量，T(n)
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

即语句执行次数，称为语句频度或时间频度。程序中一条语句与n相关的最大执行次数就是他的常数
即是时间复杂度。

要学会从输入中识别问题规模n，相同的输入问题规模，输入数据状态不一样，也可能会影响执行总时间。

如它们的总执行时间或时间度量不同，但时间复杂度相同，即，系数为1的最高次数n²输入大小为n。
举个实例

int A(void) {
    printf("O(1)\n");      //  执行 1 次t1
    return 0;       // 执行 1 次t2
}
//2次运算，T（n）== t1+t2 == 2 == O（1）
int B(int n) {
    for(int i = 0; i<n; i++) {         // 执行 (n + 1) 次,最后一次计算i不小于n后退出。t1
        printf("O(n)\n");      // 执行 n 次t2
    }
    return 0;       // 执行 1 次t3
}
//2n+2次运算，T（n）== (n+1)t1 + nt2 + t3 == 2n + 2 == O（n）

我们再回来看我们这道题

#include "stdio.h"
#include <stdlib.h>
int fact(int n);//自定义求阶乘函数
int main()
{
    int i,n,sum;
    scanf("%d",&n);//执行1次，t1
    sum = 0;//执行1次，t2
    for(i=1;i<=n;i++){
        sum += fact(i);//执行n次，t3
    }
    printf("%d\n",sum);//执行1次，t6
    system("pause");//执行1次，t7
    return 0;//执行1次，t8
}
int fact(int n)
{
    int i,factn=1;
    if(n==1)
        return 1;
    for(i=1;i<=n;i++)//执行n+1/2次，t4(每次函数被调用执行的次数)
        factn *=i;//执行1次，t5(每次函数被调用执行的次数)
    return factn;
}

/*T(n) == t1+t2+t6+t7+t8+n*t3+n*(n+1)/2*(t4+t5)
       ==O(n²)*/

这样一看是不是就非常好理解了呢？

错题回顾

错因：没有真正理解时间复杂度的概念。
题解：

i=1;
while(i<=n)
  i=i*3;  
/*假定每次循环时间t1*/
/*3的（语句执行次数）次幂约为n，即执行总时间为：t1*log₃n*/
/*T（n）== t1*log₃n == O(logn)*/