本节课主要记录了三个问题
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)*/
网友评论