首页 > 代码库 > 算法分析

算法分析

  算法就是一系列解决问题的指令,对于给定的输入,能够在有限时间内获得预期的输出。一个好的算法和一篇好的文章一样,都是不断努力,反复修正的结果。算法分析主要从运行时间和存储空间两方面讨论算法的效率。相信有些人会有跟我一样的感觉,对于一些算法,有时我们一眼就能看出它的时间复杂度,但就是无法比较规范的表达出来。本文就系统的整理一下如何规范推导算法的时间和空间复杂度。

  算法分析的一个依据是,输入规模(又称问题规模,记为 n),根据直觉,程序的运行时间随着问题规模的增大而变长。那么怎么衡量程序的运行时间呢?其实程序大部分时间只花在某些重要的操作(指令)上,比如大部分排序基本操作就是比较交换,所以另一个依据就是,程序基本操作执行的次数。如果把基本操作的次数记为 f(n) ,每次执行的时间为  Cop 那么可以用以下公式估算运行时间 :

技术分享

  假设 f(n)=n(n-1)/2,那么如果输入规模翻倍,算法大约运行 4 倍的时间,这是因为当 n 值很大时,就有:

技术分享

  那么:

技术分享

  所以对于大规模的输入,我们忽略了一些常量,而更加关注程序运行时间的增长速度,也可以称为相对增长率。为了更方便的描述 T(n) 的增长数量级,使用”大O”来表示增长数量级的上限(也可以说是算法性能的渐进上限),其数学定义是:对于T(n)和f(n),如果存在常数 C 和 n0 使得当n≥n0时,都有 0≤T(n)≤C×f(n),则记为T(n)=O(f(n))。此外还有”大Ω”用来表示最坏情况下的性能下限;”大θ”用来描述算法的最优性能。

算法分析