欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

《数据结构与算法》(浙大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. 空间的利用效率有关;
  3. 算法的巧妙程度有关。

1.2 数据结构

数据结构的定义:

  1. 包含数据对象在计算机中的组织方式(类似于图书的摆放方法);
  2. 一系列加在数据对象上的操作(类似于在书架上拿书和放书)。

抽象数据类型Abstract Data Type

  • “数据类型”
  1. 数据对象集;
  2. 数据集合相关联的操作集;
  • “抽象”

    数据类型不依赖与具体实现

  • 与面向对象的思想一致:将数据对象和相关操作封装在一起,与内部具体实现关系不大。

1.3 算法

  1. 递归算法的空间利用率低

print函数递归的弊端

void PrintN(int N)
{/*打印从1到N的全部正整数*/
	if(N>0){
		PrintN(N-1);
		printf("%d\n",N);
	}
}
  1. 计算机在一个函数A内部处理函数B的调用时,必须先把A的当前状态保存在内存中,当B调用完成后再释放内存恢复状态,继续执行A的其余语句。
  2. 所以在该递归函数执行时,直到PrintN(0)才会开始逐级释放内存,N过大时计算机内存就会不足,造成非正常中断。

**

  • 渐近分析的一些小窍门:

《数据结构与算法》(浙大MOOC)第1章 概论《数据结构与算法》(浙大MOOC)第1章 概论
1.4 最大子列和问题

最大自列和问题相关整理

本文地址:https://blog.csdn.net/xxxtrbl/article/details/107326092