我正在学习算法分析.我无法理解O,Ω和Θ之间的差异.
它们的定义方式如下:
f(n) = O(g(n))装置c · g(n)是一个上限f(n).因此存在一些常数c,使得f(n)总是≤c · g(n),对于足够大的n(即,n ? n0对于某一常数n0).f(n) = ?(g(n))装置c · g(n)是一个下界f(n).因此存在一些常数c,f(n)总是≥c · g(n),对于所有人n ? n0.f(n) = ?(g(n))意味着c1 · g(n)是对上限f(n)和c2 · g(n)一个下限f(n),对于所有n ? n0.因此存在常数c1和c2使得f(n) ? c1 ·g(n)和f(n) …