Big Omega，Big Oh，Big theta

Question

我正在读Yashavnt P. Kanetkar的一本书《数据结构》。在这本书的第11页中，我发现书中提到的算法有三种：

a.算法的增长速度至少与某些函数一样快。

b.以相同速度增长的算法。

c.增长速度不快的算法。

后来又说：

a.是Big Omega (n)

b.是大θ(n)

c.是大Oh (n)。

我不明白它的意思，所以我在youtube上搜索了一些视频。我从他们那里学到的是Big Omega是最好的情况的代表。Big Oh代表了最坏的情况。Big theta是平均案例场景的表示。我知道这些案子是什么。然而，我不能理解这本书试图通过这三个类别来表示什么，以及它们如何与这三个案例场景相关联。

Answer 1

Big Theta是数学家的近似值，回答了“它的规模有多大”这个问题；随着问题变得越来越大，函数还需要多少时间/内存？它去掉了所有恒定的因素和任何随着问题变得更大而变得不那么重要的术语，只留下一个简单的表达式。

Big Oh是一种变体，你给出的是“不比差”；这有时更容易解决，而且它是保守的错误，所以它仍然有用。

Big Omega是相反的变体，你给出的是“不比”更好。这有时也很有用，但不太常见。