数据结构——解决问题的方法的效率与什么有关?

MOOC数据结构
数据结构 + 算法

与数据的组织方式有关

例子:如何在书架上摆放图书?对中等规模、大规模的图书摆放,你有什么更好的建议?
老师提示:提出这个问题,实际上是想让大家思考,在考虑大规模数据存储的时候会遇到什么问题,以及如何根据功能(也就是关联的算法,最常见的就是插入查找删除)需要设计存储方式?

与空间的利用率有关

例子:写程序实现一个函数PrintN,使得传入一个正整数为N的参数后,能顺序打印从1N的全部正整数
实现一:循环实现,略
实现二:递归实现,如下

1
2
3
4
5
6
7
8
9
void printN(int n)
{
if(n)
{
printN(n -1);
printf("%d\n", n);
}
return;
}

与算法的巧妙程度有关

例子:一元n次多项式的求值问题
实现一:普通算法,略
实现二:秦九韶算法(转化为n个一次式的算法),略

补充:常用的程序运行时间的计时方法模板
其中,
clock():捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick,即“时钟打点”
常数CLK_TCK(或CLOCKS_PER_SEC):机器时钟每秒所走的时钟打点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <time.h>
#define MAXN 1e6 // 被测函数最大重复调用次数
clock_t start; // clock_t是clock()返回的变量类型
clock_t stop;

int main()
{
start = clock();
int i;
for(i = 0; i < MAXN; i++)
{
func(); // 被测函数
}
stop = clock();
printf("运行时间为%6.2e\n", ((double)(stop - start)) / CLOCKS_PER_SEC / MAXN); // 注意格式控制符及强制类型转换
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2020-2021 zhangguoliu
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信