首页 > 编程语言 > 详细

基本算法(02) - 渐近符号

时间:2020-04-14 09:14:44      阅读:62      评论:0      收藏:0      [点我收藏+]

符号O

  • O符号,f(n) = O(g(n)),表示f(n)的复杂度最多与g(n)一个数量级,即小于等于。
  • 当我们评估一个算法,只能评估出该算法的“时间复杂度”上限的时候,就用O表示。

符号o

o符号,f(n) = o(g(n)),表示f(n)的复杂度要比g(n)的数量级小,即小于。

符号Ω

Ω符号,f(n) = Ω(g(n)),f(n)的复杂度最少与g(n)一个数量级,即大于等于。

  • 当我们评估一个算法,只能评估出该算法的“时间复杂度”下限的时候,就用Ω表示。

符号ω

ω符号,f(n) = ω(g(n)),表示f(n)的复杂度要比g(n)的数量级大,即大于。

符号Θ

Θ符号,(n) = Θ(g(n)),表示f(n)的复杂度既大于等于g(n)的复杂度,又小于等于g(n)的复杂度,即于g(n)的复杂度相等。

性质及类比

  1. 传递性:
    f(n) = ?(g(n)) 和 g(n) = ?(h(n)) => f(n) = ?(h(n))
    f(n) = O(g(n)) 和 g(n) = O(h(n)) => f(n) = O(h(n))
    f(n) = ?(g(n)) 和 g(n) = ?(h(n)) => f(n) = ?(h(n))
    f(n) = o(g(n)) 和 g(n) = o(h(n)) => f(n) = o(h(n))
    f(n) = ω(g(n)) 和 g(n) = ω(h(n)) => f(n) = ω(h(n))
  2. 自反性:
    f(n) = ?(f(n))
    f(n) = O(f(n))
    f(n) = ?(f(n))
  3. 转置对称性:
    f(n) = ?(g(n)) 当且仅当 g(n) = ?(f(n))
    f(n) = O(g(n)) 当且仅当 g(n) = ?(f(n))
    f(n) = o(g(n)) 当且仅当 g(n) = ω(f(n))
  4. 类比:
    可以类比:
    O Ω Θ o ω
    ≤ ≥ = < >
    但类比并不是等价于;同时小符号是大符号更为严格的记号,但却没有严格的小θ。

基本算法(02) - 渐近符号

原文:https://www.cnblogs.com/duchaoqun/p/12695613.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!