Big-O Notation 包含哪些函数？
What functions are included in Big-O Notation?
我正在学习 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。这是正确的想法吗？
What functions are included in Big-O Notation?
全部*.
但是，有些功能更常用，例如您提到的O(logn)。原因是我们试图用大多数算法解决的问题的性质（例如排序），这使我们更方便地使用某些函数作为上限而不是其他函数。
PS：更具体地说，它是一个类的列表，其中n渐近无穷大。更多阅读 Order of functions.
对于您的具体问题，O(3^n) 与 O(2^n) 不同。一种查看方式是将值的比率视为 n --> 无穷大。在这种情况下，比率是：
(1.5)^n
而且它会无限增长。
同样，n^3与n^2不同，因为比率是：
n
随着 n --> 无穷大，它会无限增长。
另一方面，3*n和2*n是一样的。他们的比例是：
1.5
这 不会 增长为 n --> 无穷大。
了解并非所有函数都用于 big-O 非常重要。基本上，big-O 中的 "argument" 表示具有与 n --> 无穷大相同的渐近行为的函数 class。通常选择 class 中最简单的成员作为符号。
请记住，大 O 是复杂性的上限。当您实际分析算法时，您可能会使用更复杂的函数并包含常量。事实上，这些可能非常重要，并解释了为什么像冒泡排序这样的算法可能对小数据集是最优的，即使它对大数据集不是最优的。
正式 f(x) = O(g(x)) 当且仅当存在常量 c>0 和 n>0 使得：
c*g(x) > f(x) 对于所有 x 大于或等于 n。
记住这个定义，你可以将任何函数插入O，你将得到一组满足属性的函数。
另一种思考方式是将O定义为从函数到函数集的函数。也就是说，O(g) = { f : c*g(x) >= f(x) for all x > n} 用于常量 c 和 n，如上所述。使用这个定义，人们会说 f 在 O(g) 中，恕我直言，这更有意义，但由于历史原因，我们坚持使用等号的表示法。
现在，查看定义我们可以理解您提到的层次结构。 O(n^2) 出现在 O(n) 之后，因为 n = O(n^2) 为真但 n^2 = O(n) 为假（再次注意我没有使用 != 作为 = sign in the O notation is not a real equals 而是任意语法符号你不妨用矮人符文代替）。
另一件事，如果您想在作业中作弊，只需回答 O(n!) 即可，您在技术上是正确的（最好的正确类型）。现在，通常当人们问 "what order is this function" 时，他们要求的是紧界，即仍将充当界的最小增长函数。你可能也想看看 the definitions for other related notations。
我正在学习 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。这是正确的想法吗？
What functions are included in Big-O Notation?
全部*.
但是，有些功能更常用，例如您提到的O(logn)。原因是我们试图用大多数算法解决的问题的性质（例如排序），这使我们更方便地使用某些函数作为上限而不是其他函数。
PS：更具体地说，它是一个类的列表，其中n渐近无穷大。更多阅读 Order of functions.
对于您的具体问题，O(3^n) 与 O(2^n) 不同。一种查看方式是将值的比率视为 n --> 无穷大。在这种情况下，比率是：
(1.5)^n
而且它会无限增长。
同样，n^3与n^2不同，因为比率是：
n
随着 n --> 无穷大，它会无限增长。
另一方面，3*n和2*n是一样的。他们的比例是：
1.5
这 不会 增长为 n --> 无穷大。
了解并非所有函数都用于 big-O 非常重要。基本上，big-O 中的 "argument" 表示具有与 n --> 无穷大相同的渐近行为的函数 class。通常选择 class 中最简单的成员作为符号。
请记住，大 O 是复杂性的上限。当您实际分析算法时，您可能会使用更复杂的函数并包含常量。事实上，这些可能非常重要，并解释了为什么像冒泡排序这样的算法可能对小数据集是最优的，即使它对大数据集不是最优的。
正式 f(x) = O(g(x)) 当且仅当存在常量 c>0 和 n>0 使得：
c*g(x) > f(x) 对于所有 x 大于或等于 n。
记住这个定义，你可以将任何函数插入O，你将得到一组满足属性的函数。
另一种思考方式是将O定义为从函数到函数集的函数。也就是说，O(g) = { f : c*g(x) >= f(x) for all x > n} 用于常量 c 和 n，如上所述。使用这个定义，人们会说 f 在 O(g) 中，恕我直言，这更有意义，但由于历史原因，我们坚持使用等号的表示法。
现在，查看定义我们可以理解您提到的层次结构。 O(n^2) 出现在 O(n) 之后，因为 n = O(n^2) 为真但 n^2 = O(n) 为假（再次注意我没有使用 != 作为 = sign in the O notation is not a real equals 而是任意语法符号你不妨用矮人符文代替）。
另一件事，如果您想在作业中作弊，只需回答 O(n!) 即可，您在技术上是正确的（最好的正确类型）。现在，通常当人们问 "what order is this function" 时，他们要求的是紧界，即仍将充当界的最小增长函数。你可能也想看看 the definitions for other related notations。