《数据结构与算法》(浙大MOOC)第1章 概论
程序员文章站
2022-07-02 23:01:46
1.1 引子clock工具的使用头文件:time.hclock()函数:捕捉从程序开始运行到clock()被调用时所消耗的时间单位:clock tick(时钟打点)数据类型:clock_t常数: CLK_TCK(CLOCKS_PER_SEC)表示:每秒钟的时钟打点数技巧:使程序多次运行,得到数量级的差别即可#include#include#includeclock_t start,st...
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
下一篇: 怎么办?人工智能可能引发公众的强烈反对