《算法4》读书笔记 1.4 - 算法分析(Analysis of Algorithm)

———————————————————————————

First priority is to make you code ** CLEAR and CORRECT, but ** PERFORMANCE is also an essential, Keep Asking: How long will my program take, as a function of Input Size?

程序首先要简洁正确,性能也不可忽视

总是记得问自己:不同的输入情况下,我的程序的性能会如何?

———————————————————————————

《算法4》读书笔记 1.4 - 算法分析(Analysis of Algorithm)

算法分析,枯燥抽象,我的粗浅了解只停留在复杂度(big-Oh)、运行时间、占用内存上,很零散。《算法4》的讲解思路很有一套模式,感觉我也尝试做了一时刻的科学研究。

基本思路

开篇作者提出两个大家非常关心的两个问题:

这个程序多长时间跑完?

为什么报错“内存不足”了?

解决此类关于算法/程序分析的问题,作者建议的思路抽象、烧脑,但是系统、普世智慧:

Base on the ** Scientific Method,

Apply the ** Mathematical Analysis
to develop concise cost models

Do the ** Experimental Studies** to validate these models

基于科学研究的方法,

使用数学分析产生算法成本模型,

通过各种试验验证这些模型。

这是算法分析的大方向,其实我们也可以拿来用在很多方面,以后再研究。

科学方法 (OHPVV)

科学方法是科学家们用来研究理解现实世界的,我们进行算法分析的时候也可以套用这一方法,我简称为 OHPVV:

观察(Observe)

假设(Hyperthesize)

预测(Predict)

验证(Verify)

确认(Validate)

科学家这样做:

观察现实世界的问题现象,清楚的进行表述,通常进行具体的量化,比如牛顿发现苹果从树上往地上掉,当时他已经知道是由于重力的吸引,他想:如果苹果树长得更高,像月球那么高是不是还会掉呢?为什么月球没有掉下来呢?

对前面观察到的现象可能的答案进行猜想和假设,他设想月球受到一个向心力的作用,在做圆周运动,所以不会掉。

之后根据假设和设想,进行预测,验证自己的预测,并最终确认万有引力的假说。

将科学方法应用于算法分析中

那我们进行算法分析的时候如何借鉴这种科学方法呢?

  1. 观察程序在给定的不同输入情况下,运行多久?

    可以在程序的关键代码段执行前后加入计时代码,计算duration。
long start = System.currentTimeMillis()
.......<code>
long end = System.currentTimeMillis()
long duration = (start - end ) /1000.0;

这里容易忽视的一点是,程序的输入(Input Size)很关键。大文件和小文件的处理时间肯定不一样,算法分析的一个重点就是,如何保证程序在大量输入的情况下,依然可以在合理的时间内运行完。

  1. 建立一套数学模型,模拟计算程序运行时间
  • Develop an input model, including a definition of the problem size
  • Identify the inner loop
  • Define a cost model that includes operations in the inner loop
  • Determine the frequency of execution of those operations of the given input.

简单的说就是,界定程序的输入模型,找出程序的核心耗时代码块(通常循环语句比较占时),给出核心循环代码块中操作代码的成本模型(耗时),确定对于不同的输入模型(比如最坏情况下),这些操作代码的执行频率。

套用二八原则,就是大多数程序的运行时间取决于一小部分核心代码块的算法实现。

举例分析:Binary Search

public static int rank(int key, int[] a){
int lo=0;
int hi = a.length -1;
while (lo <=hi){
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}

输入模型:array a[N], size of N

核心循环块: while loop

成本模型:数组值之间的比较操作

运行频次分析:最坏情况下是 lgN+1

3 . 应用算法并进行试验、校正算法

这是算法分析的基本套路,掌握起来。至于具体的成本分析和频次分析这里不具体展开,后面会单独再写。

那现在做好算法分析了,接下来就是改进算法,测试,改进再测试了。

总结

当程序员解决一个新问题的时候,建议以下的策略:

Always keep asking "How long will it take, as a function of the input size?"

1。参考经典,简洁正确的实施代码

2。进行算法分析,分析:

  • 输入(input model)
  • 核心代码块(inner loop)
  • 成本模型(cost model)
  • 运行频次分析(analysis)

分析最坏情况很重要。

3。改进算法

4。测试新算法,重复2,3,4

算法分析很烧脑、费时,一般需要比较专业的人士做,但任何普通的程序员在日常工作中学会一些算法分析,对改进程序的性能,以及提升自己早日成为更专业人士,功不可没。

另外还有一点,数学真的很重要,很重要,很重要,后悔当初没有好好学习数学了。学生时代家长老师们挂在嘴边的话,“学好数理化,走遍天下都不怕”,现在想想,很有道理。

上一篇:java方法:MethodTest(05)


下一篇:[LeetCode] Sentence Similarity 句子相似度