Flyingis

Talking and thinking freely !
Flying in the world of GIS !
随笔 - 156, 文章 - 16, 评论 - 589, 引用 - 0
数据加载中……

算法分析规则

作者:Flyingis

    算法作为实现计算机程序实现时解决问题的方法,在计算机应用领域发挥着举足轻重的作用。它研究的内容是解决问题的方法,而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上,但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要,因此,在计算机程序设计中,算法设计往往处于核心地位。如何去设计一个适合特定应用的优秀算法是众多开发人员所关注的焦点,在算法设计时,需要了解算法设计的规则。

要想充分理解算法并有效地应用于实际问题,关键是对算法的分析。通常我们可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单,两个算法相互比较,它们都能解决同一问题,在相同环境下,哪个算法的速度快我们一般就会认为这个算法性能更好。数学方法能将算法分析的更为细致,能在严密的逻辑推理基础上判断算法的优劣,但在完成实际项目过程中,我们很多时候都不能去做这种严密的论证与推断,因为我们不是在完成一道数学难题,也不是数学领域的专家,将大量的时间花费在公式的计算与证明上会导致整个项目进度缓慢、成本过高,因此,在算法设计中,我们往往采用能近似表达性能的方法来展示某个算法的性能指标。例如,计算机对n2n2+2n的响应速度,当n比较大的时候几乎一样没什么区别,我们便可直接认为后者算法的复杂度为n2。在分析算法时,隐藏细节的数学表示法成为大O记法,它可以帮助我们简化算法复杂度的许多细节,提取主要成分,这和遥感图像处理中的主成分分析思想相近。

基于算法复杂度简化表达的思想基础上,我们通常会对算法进行最坏情况分析和平均情况分析。对于一个给定的算法,如果能保证它的最坏情况下的性能依然不错当然很好,但是在某些情况下,程序的最坏情况算法的运行时间和实际情况的运行时间相差很大,在实际应用中我们几乎不会碰到最坏情况下的输入,那么此时进行最坏情况分析显得有些画蛇添足,特别是分析最坏情况算法会花费大量精力的时候。算法的平均情况分析可以帮助我们估计程序的性能,作为算法分析的基本指标之一,但是平均情况和实际情况仍然会有相差很大的时候,这时我们便可以使用随机法来尽量模拟现实中的情况,这样可以得到在严格的概率意义上的预测运行时间。另外,对于一个经典算法,我们没有必要再去对该算法进行改进,研究它的上界和下界,只需要了解该算法的特性,然后在合适的时候使用它。

最后,当一个程序变快和变慢,让计算机反映出来的时间差几乎不会让人产生感觉的时候,我们也没有必要去改进这个算法,例如程序进行1000次循环花费0.001秒,改进后为0.1秒,在实际应用中通常也只需要几千次循环,此时我们就没有必要去花时间来研究这个算法了,只要该算法能正确完成任务即可。

posted on 2006-01-22 00:34 Flyingis 阅读(3241) 评论(9)  编辑  收藏 所属分类: Algorithm

评论

# re: 算法分析规则  回复  更多评论   

叫大O标记,可能好一点。因为西文叫Big O. :)
2006-01-22 13:09 | Big O

# re: 算法分析规则  回复  更多评论   

仔细读了一下,发现你对算法是不了解的。我简单更正一下。

Big O notaion是有严格数学定义的。你理解的那个不对。你说多项式的情况还可以,要其他函数形式呢?

Big O notation Definition:
f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

大O标记,表示的是函数的紧上界(注意是≤ ).如果只是<,就只是上界,用小O标记,表示。

其他,还有ω,Ω,表示紧下届,下届。Θ表示,同时上界和下届。

程序员是不需要自己写算法,但是需要了解算法的。 比如,java Collection Framework里面的sort,是改进的merge sort ,而且是stable的。了解了才可以用好他们:)
2006-01-22 13:35 | 程序员

# re: 算法分析规则  回复  更多评论   

补充一下,是叫做asymptotic upper bound,
中文真不知道叫什么。应该叫非表象上界,不是普通的上界。这个asymptotic是你说的简化细节的意思了。
2006-01-22 13:46 | 程序员

# re: 算法分析规则  回复  更多评论   

"大O记法"的中文定义:
若存在常数c和k,对所有n>k,使0<f(n)<cg(n)成立,函数f(n)就可以称为O(f(n))
使用O记法的原因主要是:当我们忽视数学公式中的小项时,当我们忽略对整个分析量只起了少量作用的部分程序时,限制可能出现的错误,并且根据算法总体运行时间的上界,对算法分类。定义中的小于还是小于等于还没有认真考究,感谢“程序员”的评论。
我学习算法一是因为兴趣,二是因为以后工作很可能会需要。和“程序员”建议的一样,细节我不会去深究,但要了解各种算法的特性。写一些文章有时显得有点班门弄斧,不妥之处请各位高手同行直接批评纠正,帮助我提高!
2006-01-22 16:41 | Flyingis

# re: 算法分析规则  回复  更多评论   

刚才在公司没有五笔,现在在写几句.不好意思我只是讨论问题,有冒犯的地方,老兄多包含.

大O标记其实是n>=k的时候函数的上界,有了这个定义才能时候算法分析.时间或空间复杂度进行推导的时候,某一步可以证明有这么一个K,n>=k的时候,g()>=f(),于是,就可以用O(g)来表示了.

不能如你说的就是简化掉表达示后面的东西,那在数学上也讲不通呀.

算法分析的技术,除了上面那种根据程序写出复杂度f,再推出O(g)的直接方式.还有一种叫做amortize的技术,中文应该翻译成分期尝还的分析技术.中文的教材里都不讲这个,分析基本都不讲,清华那本<数据结构>只讲结果不讲为什么没有证明过程,象一本速查手册,现在觉得那些教材编的太差了,误人子弟.
2006-01-22 16:54 | 程序员

# re: 算法分析规则  回复  更多评论   

今天看了你很多的blog还是收获很多的.以后多交流.有冒犯之处,多多原谅呀.
2006-01-22 16:59 | 程序员

# re: 算法分析规则  回复  更多评论   

@ 程序员

你见外了:)

在这里,我本来就应该抱着学习的态度来写文章,看大伙的评论。在我看来,只要是学术或研究方面的问题,可以直接指出,甚至争论,前提是只对事,不对人。能和比我经验丰富的人讨论问题是我的荣幸。

国内的教材的确令人不敢恭维,我现在看的是Robert Sedgewick的Algorithms in Java,感觉不错。

在学习过程中,我喜欢将看过的内容用自己的思维去重新组织一遍,然后觉得有用的东西就写下来,这里面自然就会有一些思想上的误区与表达上的问题,贴在blogjava上就是来和大家交流,让大家提意见的。只有一点一滴的积累,才有最后质的变化。

感谢你的指正!
2006-01-22 17:09 | Flyingis

# re: 算法分析规则  回复  更多评论   

你在美国?现在上网,又在公司加班了吧:)
2006-01-22 17:13 | Flyingis

# re: 算法分析规则  回复  更多评论   

现在已经在家了,白天到公司了.没有加班,比较闲所以有空在blog上瞎写了:)
2006-01-22 17:19 | 程序员

只有注册用户登录后才能发表评论。


网站导航: