数据结构作业1 讲解和拓展
原题来自雪梨教育
http://www.edu2act.net/task/list/checked/
题后给出讲解和扩展
任务1_1 比较下列算法的时间复杂度
任务描述：
下面给出4个算法，请分析下列各算法的时间复杂度，请写清楚题号，并将每个小题的分析过程写出来，并给出分析结果。
（1）
-
for(i = 1; i <= n; i++)
-
scanf("%d", &num[i]);
-
ans = num[1];
-
for(i = 1; i <= n; i++)
-
{
-
for(j = i; j <= n; j++)
-
{
-
s = 0;
-
for(k = i; k <= j; k++)
-
s += num[k];
-
-
if(s > ans)
-
ans = s;
-
}
-
}
-
（2）
-
for(i = 1; i <= n; i++)
-
scanf("%d", &num[i]);
-
sum[0] = 0;
-
for(i = 1; i <= n; i++) {
-
sum[i] = num[i] + sum[i - 1];
-
}
-
-
ans = num[1];
-
for(i = 1; i <= n; i++) {
-
for(j = i; j <= n; j++) {
-
s = sum[j] - sum[i - 1];
-
if(s > ans) ans = s;
-
}
-
}
-
（3）
-
int solve(int left, int right)
-
{
-
if(left == right)
-
return num[left];
-
-
mid = (left + right) / 2;
-
lans = solve(left, mid);
-
rans = solve(mid + 1, right);
-
-
sum = 0, lmax = num[mid], rmax = num[mid + 1];
-
for(i = mid; i >= left; i--) {
-
sum += num[i];
-
if(sum > lmax) lmax = sum;
-
}
-
sum = 0;
-
for(i = mid + 1; i <= right; i++) {
-
sum += num[i];
-
if(sum > rmax) rmax = sum;
-
}
-
-
ans = lmax + rmax;
-
if(lans > ans) ans = lans;
-
if(rans > ans) ans = rans;
-
return ans;
-
}
-
-
int main(void)
-
{
-
scanf("%d", &n);
-
for(i = 1; i <= n; i++)
-
scanf("%d", &num[i]);
-
-
printf("%d\n", solve(1, n));
-
return 0;
-
}
（4）
-
for(i = 1; i <= n; i++)
-
scanf("%d", &num[i]);
-
-
num[0] = 0;
-
ans = num[1];
-
for(i = 1; i <= n; i++)
-
{
-
if(num[i - 1] > 0)
-
num[i] += num[i - 1];
-
else
-
num[i] += 0;
-
if(num[i] > ans)
-
ans = num[i];
-
}
任务1_2 数字反转的时空复杂度
任务描述：
下面两个函数fun1和fun2都是实现对整数的逆序输出功能，请根据下面题目要求，给出答案。
（1） 请分析函数fun1的时间复杂度和空间复杂度；
（2） 请分析函数fun2的时间复杂度和空间复杂度。
代码如下：
-
int fun1(int n)
-
{
-
int rev = 0;
-
while (n != 0) {
-
int pop = n % 10;
-
n /= 10;
-
rev = rev * 10 + pop;
-
}
-
return rev;
-
}
-
-
void fun2(int n)
-
{
-
printf("%d", n % 10);
-
if(n / 10 != 0)
-
fun2(n / 10);
-
}
-
-
int main(void)
-
{
-
printf("%d\n", fun1(10203));
-
fun2(10203);
-
-
return 0;
-
}
讲解：
说频度，或者求和公式往上堆出来的解释， 都是耍流氓
没有专业名词的讲解才是讲解
直接粘贴我交的作业
先用数学说明，后解释题意并分析。
分别为O(N^3),O(N^2),O(N*logN),O(N).
数学：
1）第一个循环O(N)
对于每一个i来说，j执行n-i+1次，对于每个j来说，k执行j-i+1次，我们把常数去掉，
对于每一个i，执行的常数操作为1+2+3+...+(n-i+1),等差数列[1+(n-i+1)](n-i+1)/2约等于(n-i)^2而i=1,2,....n，分别执行常熟操作次数为(n-1)^2,(n-2)^2......1^2,0^2.，可以看出是平方函数求和，而对x^2求和n项的公式为(n^3)/3+(n^2)/2+n/6，我们只看最大，去掉常数，也就是O(N^3).
O(N^3)+O(N)当然还是O(N^3)
2）前两个循环都是O(N),下面两重循环，对于每个i，j执行n-i次，当i=1，2....n，j执行次数为n-1,n-2....1,0,可以看出是等差数列求和，最高项是(n^2)/2，去掉系数，时间复杂度为O(N^2).
加起来：O(N^2)+O(N)+O(N)=O(N^2)
3）分析solve函数：采用二分，将序列分成两份，直到不可再分，执行的两个循环加起来就是遍历一遍左右端点之间数的复杂度。我们看所有从长度为1的子数组，数量为n，合并后，所有长度为2的子数组，数量为n/2，再合并，长度为4的子数组，数量为n/4，我们会发现对于每个长度1,2^2,2^4,2^3，的子数组，遍历一遍所有长度一样的子数组的复杂度都是O(N)，设一共有x种长度，2^x=n,很明显x=log(2,n)。
每次O(N)，次数o(log(2,n)),乘起来O(n*logn)
看main函数，接收数据是O(N)，加solve，等于O(n*logn)
4）接收数据O(N)，一个循环O(N)，加起来O(N)。
下面我根据完成的功能和思路分析一下：（思路简单，文字略长，不太会叙述）
这四个代码完成的功能都是求最大子数组（注意用词准确，子数组连续，子序列可以不连续）。
1）分别枚举每一个子数组的起点和终点，也就是i和j，对于每一个起点和终点，对中间部分求和，也就是k循环。显然有n个起点n个终点（去重减半，不影响复杂度），所以子数组数量为O(N^2)，对于每个子数组，我们要遍历一下求和，子数组长度1-n不等，遍历一遍平均O(N)，乘起来O(N^3).（注意可能产生时间更大的错觉）。找出所有子数组中最大的即可。
2）预处理出每一个以第一个元素开始，第i个元素结尾的子数组和，还是枚举每个起点终点，但是我们求和时直接减就可以了，不用遍历。对于每个子数组，操作为O(1),子数组数量O(N^2),所以总时间O(N^2).
3）二分，求左右两边最大子数组，取最大。但是还有一种情况：包含断点的那些子数组也要考虑，请思考那两个那两个循环为什么那么写？最后逻辑为何正确？
4）动态规划入门思想
没有枚举，num[i]的含义是以下标i结尾的所有子数组中最大的。
遍历数组，对于第i个元素，它的所有子数组下标范围有[1,i],[2,i].....[i-1,i],还有它自己，我们看i-1个元素，他的子数组为[1,i-1],[2,i-1].....[i-1]。请想num[i]的含义，我们求i结尾的，只要把i-1结尾的最大加上i就好了，当然如果i-1结尾最大子数组是负的，i结尾最大子数组就是它本身。
为什么O(N)？时间省在哪里了？我们省掉了许多没必要的计算，计算i时，之前的数组和已经都计算过，朴素算法并没有记录下来，而是重复计算，造成时间浪费。算法优化的过程就是去掉重复计算的过程。
1-2
fun1:时间O(log10,N)，空间O(1)
FUN2:时间O(log10,N)，空间O(log10,N)
第一个函数只是有限几个变量，所以空间O(1),一个循环n每次缩小十倍，时间O(log10,N).
第二个函数递归调用，这个函数没执行完就跳到另外的函数，会压函数栈，空间O(log(10,n)),
而时间还是O(log10,N)，复杂度没变但是时间稍长。
作业完了
我们说拓展：如何求二维数组的最大和子数组？
如果大家看懂了之前的讲解，我给个提示：利用第二个代码和第四个代码思想的结合
解释：
1 2 3 4
-1 -2 1 2
1 3 -2 1
-1 -2 -1 -3
如图是前三行整体最大
怎么做呢？
先用第二个代码的思想，我们进行预处理
每个数代表这一列到这个数位置截止，累加和。
1 2 3 4
0 0 4 6
1 3 2 7
0 1 1 4
然后，我们枚举每一列的起点和终点分别为第0，1，2，3行
然后压缩成一维来做
比如求1-3行的这个矩形，我们拿0和3行减一下就行了
0-1，1-2，1-3，4-4=-1，-1，-2，0就是1-3行压缩后的结果
然后按一维do来做就好
时间复杂度：n行m列：
预处理：每个元素弄一遍，O(N*M)
枚举压缩：起点n个终点n个，数量：O(N^2)，对于每个矩阵，我们压缩为一维，只要减一下就好，O(M)
dp：每个一维O(M)
求最大子长方体或者多维也一样，预处理，三维压二维，二维压一维，按一维dp来做。
算法优化的过程就是去除重复计算过程的过程
想象一下没有预处理没有dp的朴素做法时间是多少？
算法的魅力
以前写过这个问题的总结了，所以这次可能写的有点简单。看不懂再去之前博客找找
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/82788866
- 点赞
- 收藏
- 关注作者
评论（0）