2025年算法复杂度分析中的符号（Θ、Ο、ο、Ω、ω）简介

科技前沿 • 2025-02-24 17:25 • 阅读 70

大家好，我是讯享网，很高兴认识大家。

ο，读音：small-oh、欧米可荣（小写）；表示上界(not tight)，小于的意思。

Ω，读音：big omega、欧米伽（大写）；表示下界(tightness unknown)，大于等于的意思。

ω，读音：small omega、欧米伽（小写）；表示下界(not tight)，大于的意思。

大O符号（英语：Big O notation）是用于描述函数渐近行为的数学符号。更确切地说，

它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。

大Ω符号的定义与大O符号的定义类似，但主要区别是，大O符号表示函数在增长到一定

程度时总小于一个特定函数的常数倍，大Ω符号则表示总大于，来描述一个函数数量级的

渐近下界。

大Θ符号是大O符号和大Ω符号的结合。下面给出具体的数学定义:

函数f ( n )代表某一算法在输入大小为n的情况下的工作量（效率），则在n趋向很大的时候，我们将f (n)与另一行为已知的函数g(n)进行比较：

1）如果limf(x)/g(x)=0，则称f (n)在数量级上严格小于g(n)，记为f (n)=o( g(n))。

2）如果limf(x)/g(x)=∞，则称f (n)在数量级上严格大于g(n)，记为f (n)=w( g(n))。

3）如果limf(x)/g(x)=c，这里c为非0常数，则称f (n)在数量级上等于g(n)，即f (n)和g(n)是同一个数量级的函数，记为：f (n)=Θ( g(n))。

4）如果f (n)在数量级上小于或等于g(n)，则记为f (n)=O( g(n))。

5）如果f(n)在数量级上大于或等于g(n)，则记为f (n)=Ω( g(n))。

大O大Ω都是存在c，小o小w都是对于任意c
————————————————
版权声明：本文为CSDN博主「很吵请安静」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/_/article/details/