[武汉|结业弟子]JAVA-刘家铭|2017年10月02日的日报-技能树.IT修真院

发表于： 2017-10-02 21:20:25

2 946

今天完成的事情：

1:整理,录入了小课堂的东西

2:看书

明天计划的事情：

搞方案设计

遇到的问题：

无

收获：

①:算法效率的度量方法

1:事后统计方法(缺陷多,不考虑)

这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低

但这种方法显然有很大缺陷

①:必须依据算法实现编制好程序,这通常需要花费大量时间精力,如果编制出来发现错误或是糟糕的算法,就白做了

②:时间的比较依赖计算机硬件和软件等环境因素.不同的计算机性能处理算法的运算速度上会不一样,所用的操作系统,编译器,运行框架等软件的不同,也可以影响他们的结果.

就算是同一台机器,cpu使用率和内存占用情况不一样,也会造成细微差异

③:算法的测试数据设计困难,并且程序的运行时间往往还与测试数据的规模有很大关系.

效率高的算法在小的测试数据面前往往得不到体现.

比如10个数字的排序,不管用什么算法,差异都几乎是0.

而如果有一百万个随机数字排序,那不同算法的差异就非常大,我们为了比较算法,到底用多少数据来测试,这是很难判断的问题

2:事前分析估算方法

在计算机程序编制前,依据统计方法对算法进行估算

算法消耗的时间取决于下列因素:

1:算法采用的策略,方法

2:编译产生的代码质量

3:问题的输入规模

4:机器执行指令的速度

第一条是算法好坏的根本

第二条要由软件来支持

第四条要看硬件性能

也就是说,抛开这些与硬件软件相关的要素,一个程序的运行时间,依赖于算法的好坏和问题的输入规模.输入规模就是指输入量的多少

②:函数的渐进增长

例子:

2n+3和3n+1哪个算法更好?

其实这是不一定的,要看n的次数

假设n=1 那么算法a需要2*1+3=5次操作算法b需要3*1+1=4次操作

假设n=3 那么算法a需要2*3+3=9次操作算法b需要3*3+1=10次操作

假设n=100 那么算法a需要2*100+3=203次操作算法b需要3*100+1=301次操作

由以上例子可看出,输入规模n在没有限制的情况下,只要超过一个整数N,这个函数就总是大于另一个函数,我们称函数为渐进增长的.

小知识

1:如果n足够大,我们可以忽略后面的这些加法常数

2:与最高次项相乘的常数并不重要,比如4n+8与2n²+1

返回列表