算法中的增长率(Rate of Growth)是什么意思?

2019-05-2717:21:43数据结构与算法Comments2,374 views字数 607阅读模式

一个函数或算法的代码块花费的时间随输入增长的速率称为增长率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html

假设你去买一辆小车和一辆自行车。如果你朋友刚好看到,问你在买什么,我们一般都会说:买小车。因为买小车比买自行车花费高多了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html

【总花费=小车的花费+自行车的花费】文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html

【总花费≈小车的花费(近似)】文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html

对于上面的例子,我们用一个函数来表示买车的花费,这个函数忽略低阶指数的项(相对于高阶项,他们的对函数结果的影响很小)。下面这个例子中n4 , 2n2, 100n, 和 500 分别是某个函数对应不同输入的花费,可以把它近似到n4,因为它的增长率最高。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html

【n4 + 2n2 + 100n + 500n ≈ n4文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html

下面是一些我们在程序设计过程中经常会遇到的增长率:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html

Time ComplexityNameExample
1ConstantAdding an element to the front of a linked list
log nLogarithmicFinding an element in a sorted array
nLinearFinding an element in a unsorted array
nlog nLinear LogarithmicSorting n items by ‘Divide and Conquer’
n2QuadraticShortest path between 2 nodes in a graph
n3CubicMatrix Multiplication
2nExponentialThe Towers of Hanoi problem
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12958.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/12958.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定