本文共 3332 字，大约阅读时间需要 11 分钟。
- 什么是数据结构算法
- 什么是算法
算法就是解决问题的一个步骤和方法，在计算机里表现有序的序列。
例子:求两正整数m、n的最大公因子的算法如下：
- 输入m、n
- m/n(整数)；余数->r(0<=r<=n)
- 若r=0，则当前n=结果，输入n，算法停止；否则，转到第4步
- n->m,r->n 转到第2步
如初始输入m=10,n=4,则m，n，r在算法中的变化如下：
m n r
10 4 2
4 2 0
即10和4的最大公因子是2。
- 使用C++语言编写最大公因子的求解
| #include <stdio.h> #include <algorithm> using namespace std; int main(int argc,char*argv[]) { int m,n,j; char flag = 'Y'; while(flag=='y'||flag=='Y') { // printf("\n"); scanf("input=%d%d",&m,&n); if(m>0&&n>0){ j = max(m,n); printf("output=%d\n",j); } printf("continue?(y/n) "); flag =getchar(); } return 0; } |
- 数据结构和算法等于什么
算法设计：取决于选定的逻辑结构
算法实现：依赖于采用的存储结构
数据结构+算法=程序
- 算法特性
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
- 算法分析
解决一个问题可以有多种不同算法，在算法正确的前提下，评价算法好坏的方法：
正确性、可读性、健壮性、时间效率高和存储量低。
消耗时间多少；
消耗存储空间的多少；
容易理解、容易编程和调试、容易维护。
- 算法效率的度量-算法时间复杂度
算法效率-用依据该算法编制的程序在计算机上执行所执行所消耗的时间来度量。
问题规模：输入数量的大小，用n来表示。
算法的时间符复杂度：算法消耗时间，它是问题规模的函数T（n）。
- 算法时间复杂度-事后统计法
事后统计法：
通过编写测试程序和设计测试数据，测试程序的运行时间，从而确定算法效率的高 低。
事后统计法的缺点：
- 依赖与特定的计算机硬件和软件。
- 需要花费大量尽力设计测试程序和测试数据。
- 算法时间复杂度-事前估计方法
事前估计方法：根据统计学的方法，对算法效率进行估算。
程序在计算机运行所消耗的时间取决于：
- 算法的设计
- 算法输入规模
- 编辑器对代码的优化
- 计算机执行指令的速度
- 算法效率的度量-事前估计方法
- 引用了大“O”
“O”表示一个数量级的概念。
根据算法中语句执行的最大次数（频度）来估算一个算法执行时间的数量级。
2.时间复杂度
算法中基本操作重复执行的次数是问题规模n的某个函数f（n）。
T（n） = O（f（n））
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。
3.语句的频度
是该语句重复执行次数。
- 例子求1到n的累加值
算法一：
| #include <stdio.h> int main(int argc,char * argv[]){ int i,sum=0,n=100; for(i=1;i<=n;i++){ sum=sum+i; } printf("sum is:%d\n",sum); return 0; } |
算法二：
| #include <stdio.h> int main(int argc,char * argv[]){ int sum=0,n=100; sum =(1+n)*n/2; printf("sum is:%d\n",sum); return 0; } |
- 总结时间复杂度内容
计算大O的放法：
- 根据语句频度，写出表达式。
- 常数部分变为1。
- 只保留最高阶项目，其余项的舍去。
- 如果最高阶项有乘数且不为1,表达式除与最高阶相乘的数。
例子：
| #include <stdio.h> int main(int argc,char * argv[]) { int i,j,n; for(i=0;i<n;i++){ for(j=i;j<n;j++){ printf("i+j=%d\n",i+j); } } } |
- 时间复杂度的最坏情况的平均情况
例子：在数组中查找特定元素
| int search(datatype A[n+1],datatype k){ int i=0;A[0]=k; while(i>0 && A[i]!=k){ i--; } return i; }
|
- 算法空间复杂度
算法的空间复杂度就是计算算法所需要的存储空间的大小。
S（n）=O（f（n））
如初始输入m=10,n=4,则m，n，r在算法中的变化如下：
m n r
10 4 2
4 2 0
即10和4的最大公因子是2。
| #include <stdio.h> #include <algorithm> using namespace std; int main(int argc,char*argv[]) { int m,n,j; char flag = 'Y'; while(flag=='y'||flag=='Y') { // printf("\n"); scanf("input=%d%d",&m,&n); if(m>0&&n>0){ j = max(m,n); printf("output=%d\n",j); } printf("continue?(y/n) "); flag =getchar(); } return 0; } |
算法设计：取决于选定的逻辑结构
算法实现：依赖于采用的存储结构
数据结构+算法=程序
解决一个问题可以有多种不同算法，在算法正确的前提下，评价算法好坏的方法：
正确性、可读性、健壮性、时间效率高和存储量低。
消耗时间多少；
消耗存储空间的多少；
容易理解、容易编程和调试、容易维护。
算法效率-用依据该算法编制的程序在计算机上执行所执行所消耗的时间来度量。
问题规模：输入数量的大小，用n来表示。
算法的时间符复杂度：算法消耗时间，它是问题规模的函数T（n）。
事后统计法：
通过编写测试程序和设计测试数据，测试程序的运行时间，从而确定算法效率的高 低。
事后统计法的缺点：
事前估计方法：根据统计学的方法，对算法效率进行估算。
程序在计算机运行所消耗的时间取决于：
“O”表示一个数量级的概念。
根据算法中语句执行的最大次数（频度）来估算一个算法执行时间的数量级。
算法中基本操作重复执行的次数是问题规模n的某个函数f（n）。
T（n） = O（f（n））
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。
是该语句重复执行次数。
算法一：
| #include <stdio.h> int main(int argc,char * argv[]){ int i,sum=0,n=100; for(i=1;i<=n;i++){ sum=sum+i; } printf("sum is:%d\n",sum); return 0; } |
算法二：
| #include <stdio.h> int main(int argc,char * argv[]){ int sum=0,n=100; sum =(1+n)*n/2; printf("sum is:%d\n",sum); return 0; } |
计算大O的放法：
例子：
| #include <stdio.h> int main(int argc,char * argv[]) { int i,j,n; for(i=0;i<n;i++){ for(j=i;j<n;j++){ printf("i+j=%d\n",i+j); } } } |
例子：在数组中查找特定元素
| int search(datatype A[n+1],datatype k){ int i=0;A[0]=k; while(i>0 && A[i]!=k){ i--; } return i; }
|
算法的空间复杂度就是计算算法所需要的存储空间的大小。
S（n）=O（f（n））
- 总结第三节内容
转载地址：http://acuti.baihongyu.com/