algorithm - Big-O Notation 包含哪些函数？

Question

我正在学习 Big-O Notation 并正在完成一项我被卡住的作业。基本上，我被赋予了不同的功能，并且必须为它们编写 Big(O)。我认为我的困惑在于 Big-O 中可以包含哪些功能。我对层次结构的理解如下:O(1)O(登录)在)O(nlogn)O(n^2)O(2^n)O(n!)

我也理解为什么常量和更小的项被遗漏了，因为我们只是在寻找一个界限。我的问题是当函数不是用这些术语编写时会发生什么。例如(这不是我的确切问题，但类似)，3^n 不是 2^n 的常数倍数。 Big-O 是 O(3^n) 还是 O(2^n)？我的想法是 O(3^n) 因为 3^n 比 2^n 增长得更快，而 Big O 是一个上限。但我还没有看到 Big O 表示的基数不是上面列出的 2 或 n。这是正确的想法吗？

Answer 1

What functions are included in Big-O Notation?

全部^*。

---

但是，有些函数更常用，例如您提到的O(logn)。原因在于我们尝试用大多数算法(例如排序)解决的问题的性质，这使得我们更方便地使用某些函数作为上限而不是其他函数。

---

_{PS:更具体地说，它是一个类列表，其中 n 渐近无穷大。更多信息请阅读 Order of functions .}