我要评论1.1 引子
-
clock工具的使用
头文件：time.h
clock（）函数：捕捉从程序开始运行到clock（）被调用时所消耗的时间
单位：clock tick（时钟打点）
数据类型：clock_t
常数： CLK_TCK(CLOCKS_PER_SEC)
表示：每秒钟的时钟打点数 -
技巧：使程序多次运行，得到数量级的差别即可
#include<stdio.h>
#include<time.h>
#include<math.h>
clock_t start,stop;
double duration;
#define MAXN 10/*多项式最大项数，即多项式阶数+1*/
#define MAXK 1e7/*被测函数最大重复调用次数*/
double f1(int n, double a[], double x)
{/*多项式直接计算的方法*/
int i;
double p=a[0];
for(i=1;i<=n;i++)
p+=(a[i]*pow(x,i));
return p;
}
double f2(int n, double a[], double x)
{/*秦九韶算法*/
int i;
double p=a[n];
for(i=n;i>0;i--)
p=a[i-1]+x*p;
return p;
}
void run(double(*f)(int,double*,double), double a[],int case_n)
{/*此函数用于测试被侧函数的运行时间*/
/*case_n是输出的函数编号：1代表函数f1*/
int i;
start=clock();
for(i=0;i<=MAXK;i++)
(*f)(MAXN-1,a,1.1);
stop=clock();
duration=((double)(stop-start))/CLK_TCK；
printf("ticks%d=%f\n", case_n, (double)(stop-start));
printf("duration%d=%6.2e\n",case_n,duration);
}
int main()
{
int i;
double a[MAXN];/*储存多项式的系数*/
/*为本题的多项式系数赋值，即a[i]=i*/
for(i=0;i<MAXN;i++)a[i]=(double)i;
run(f1, a, 1);
run(f2, a, 2);
return 0;
}
- 解决问题的效率
- 数据的组织方式有关；
- 空间的利用效率有关；
- 算法的巧妙程度有关。
1.2 数据结构
数据结构的定义：
- 包含数据对象在计算机中的组织方式（类似于图书的摆放方法）；
- 一系列加在数据对象上的操作（类似于在书架上拿书和放书）。
抽象数据类型Abstract Data Type
- “数据类型”
- 数据对象集；
- 数据集合相关联的操作集；
-
“抽象”
数据类型不依赖与具体实现
-
与面向对象的思想一致：将数据对象和相关操作封装在一起，与内部具体实现关系不大。
1.3 算法
- 递归算法的空间利用率低
print函数递归的弊端
void PrintN(int N)
{/*打印从1到N的全部正整数*/
if(N>0){
PrintN(N-1);
printf("%d\n",N);
}
}
- 计算机在一个函数A内部处理函数B的调用时，必须先把A的当前状态保存在内存中，当B调用完成后再释放内存恢复状态，继续执行A的其余语句。
- 所以在该递归函数执行时，直到PrintN(0)才会开始逐级释放内存，N过大时计算机内存就会不足，造成非正常中断。
**
- 渐近分析的一些小窍门：
1.4 最大子列和问题
本文地址：https://blog.csdn.net/xxxtrbl/article/details/107326092
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论