首页 > 代码库 > 算法分析
算法分析
算法就是一系列解决问题的指令,对于给定的输入,能够在有限时间内获得预期的输出。一个好的算法和一篇好的文章一样,都是不断努力,反复修正的结果。算法分析主要从运行时间和存储空间两方面讨论算法的效率。相信有些人会有跟我一样的感觉,对于一些算法,有时我们一眼就能看出它的时间复杂度,但就是无法比较规范的表达出来。本文就系统的整理一下如何规范推导算法的时间和空间复杂度。
算法分析的一个依据是,输入规模(又称问题规模,记为 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))。此外还有”大Ω”用来表示最坏情况下的性能下限;”大θ”用来描述算法的最优性能。
算法分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。