概论：
学习目的与要求
了解数据结构在计算机软件和计算机应用中的作用，掌握逻辑结构和存储结构，熟悉数据结构的两大类型和四种基本的存储方法，算法的五个要素，以及算法与程序的区别，熟悉算法的描述，掌握对算法的分析和时间复杂度的估算。
数据结构的两大类型：
1.线性结构。2.非线性结构。
四种基本存储方法：
1，顺序存储方法。2，链接存储方法。3，索引存储方法。4，散列存储方法。
算法的五个要素：
1，输入（0个或多个输入）
2，输出（至少一个或者多个输出）
3，有穷性（时间有限，执行次数有限）
4，确定性（算法中的每一条指令都有明确的含义，无二义性）
5，可行性（算法是可行的，即算法中描述的操作都可以通过基本的运算来完成）
算法和程序的区别：
算法是描述解题的方法，不依赖于具体的程序语言，可以是自然语言，计算机语言，数学语言或者约定的符号语言。
程序必须依赖于具体的计算机程序语言。
下面是用类C语言描述的算法（在C语言中不一定都能编译通过，它只是类似C语言的算法描述）：
float fact(int n)
{ //求n!就是从1开始连乘至n,即n!=1x2x3x...xn
int i;
float k=1.0;
for (i=1;i<=n;i++)
k=k*i;
return k
}
def fact(n): #python 的变量可以不声明类型在调用的过程中以实际参数确定变量 k=1.0 for i in range(1,n+1): k=k*i return k n=int(input("请输入一个大于1的正整数N，计算N的阶乘N！")) print("%d 的阶乘是：%d"%(n,fact(n))) 讯享网
程序上机执行结果如下：
请输入一个大于1的正整数N，计算N的阶乘N！50
50 的阶乘是：
分析算法：
一个算法的优劣取决于
1，执行算法所耗费的时间，即时间复杂性。
2，执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性。
3，算法易于理解，易于编程，易于调试等，即可读性和可操作性。
时间复杂度 算法中的基本操作重复执行的次数是问题规模n的某个函数f(n), 算法的时间量度记为：T（n)=O(f(n)),算法中每条语句执行的次数也称（频度）X 语句执行一次的时间=算法所耗费时间
求两个n 阶矩阵的乘积C=AxB,算法描述如下：
for (i=1;i<=n;i++){ // 耗费时间=n+1
for(j=1;j<=n;j++) // n(n+1)
c[i][j]=0; // 
for(k=1;k<=n;k++) //(n+1)
c[i][j]=c[i][j]+a[i][k]*b[k][j]; //
}
所以 T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1这个太复杂了，引入一个渐进时间复杂度T(n)=O(n3),当n-->时可以称T(n)和n3同阶，用n3来近似表示T(n) 时间复杂度，即为O(n3),叫做渐近时间复杂度。
例如:
x=0;
for(i=2;i<=n;i++)
for(j=2;j<=i-1;j++)
x=x+1;
时间复杂度为O(n2)
与n无关的记为O(1)
例如：
x=90;y=100;
while(y>0)
if(x>100){
x=x-5;y--;
}
else x++;
与n无关的都即为O（1）
算法的时间复杂度从小到大排列是：
常数阶O(1)<对数阶O(log<线性阶O(n)<线性对数阶O(nlog<平方阶O()<立方阶O()<k次方阶O()<指数阶O()<阶乘阶O(n!)
空间复杂度记为S(n)
算法在运行过程中临时占用的存储空间是问题规模n 的一个函数
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/23162.html