1.数据结构
在上图中,数据就是课程、类别和作者,结构就是课程与类别和作者的关系。简单的说,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科,学好数据结构可以使计算机更高效地工作。
2.算法
我们一般会通过分析不同算法的时间复杂度和空间复杂度来进行比较它们的好坏。
一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出 T(n) 的同数量级(它的同数量级有以下:1,log(2)n,n,n log(2)n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n) = 该数量级,若 T(n)/f(n) 求极限可得到一常数c,则时间复杂度T(n) = O(f(n))。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
程序执行时所需存储空间包括以下两部分:
(1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。
(2)可变空间。这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。
S(n)=O(f(n))
其中n为问题的规模,S(n)表示空间复杂度。
例题
例:求最大子序列和:给定一整数序列A1, A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大
例如:整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
解法一:穷举法(复杂度:O(n^3))
int maxSubSum1(inta[],intsize )
{
intmaxSum = 0;
for(inti = 0; i < size; i++ )
for(intj = 1; j < size; j++ )
{
int thisSum = 0;
for(intk = i; k <= j; k++ )
thisSum += a[k];
if( thisSum > maxSum )
maxSum = thisSum;
}
return maxSum;
}
解法二:根据Sum(i, j+1) = Sum(i, j) + A[j+1]递推(算法复杂度O(n^2))
int max_sub(inta[],intsize)
{
int i,j,v;
int max=a[0];
for(i=0;i
{
v=0;
for(j=i;j
{
v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]
if(v>max) max=v;
}
}
return max;
}
解法三:动态规划(线性复杂度)
在这一遍扫描数组当中,从左到右记录当前子序列的和temp_sum,若这个和不断增加,那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数,那么当前子序列的和将会减小。此时temp_sum 将会小于max,当然max也就不更新。如果temp_sum降到0时,说明前面已经扫描的那一段就可以抛弃了,这时将temp_sum置为0。然后,temp_sum将从后面开始将这个子段进行分析,若有比当前max大的子段,继续更新max。这样一趟扫描结果也就出来了。
intmax_sub2(inta[],intsize)
{
inti,max=0,temp_sum=0;
for(i=0;i
{
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
elseif(temp_sum<0)
temp_sum=0;
}
return max;
}