Big O 的思维常数
我对如何确定常数何时对于找到大 O 很重要感到有点困惑。我知道我们应该忽略常数来找到大 O 但这个函数让我三思而后行：
f(n): 5n + 8n log n + 3 000 000
我认为这是 O(n log n) 但如果 n 开始时值很小，f(n) 将保持在 3 000 000 左右。那么我是否应该将这些类型的函数视为 n 是一个非常大的值？但如果我这样做，这是否现实，因为大多数代码没有 10 000 个样本大小？
I'm a bit confused on how to determine when constant is important to find big O. I know we're supposed to ignore constant to find big O but this function is making me think twice:
f(n): 5n + 8n log n + 3 000 000
I'd think this is O(n log n) but if n starts as small values, f(n) will stay around 3 000 000. So should i look at these type of functions as if n is a very large value? But if I do that, would that be realistic since most code doesn't have a 10 000 sample size?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
大 O 表示法用于查找当参数增长到无穷大时的极限行为。这就是为什么你忽略这个常量：随着
n变得越来越大，它会被淹没。查看 此问题了解更多详细信息。
但你已经发现了盲目追随大O的局限性之一：总是有其他考虑因素。您的常量实际上可能非常大（如您的情况），并且
n的值总是很小（如您的情况），因此您的算法实际上是O(1)。然而，从技术上讲，它的复杂度是O(n log n)，因为你应该忽略这个常量。Big O notation is used to find the limiting behaviour as the argument grows to infinity. That's why you ignore the constant: it gets swamped out as
ngets larger and larger.Check out the answers (particularly the highest-scoring one) of this question for further details.
But you've hit upon one of the limitations of mindlessly following Big O: there are always other considerations. Your constant could actually be quite large (as in your case) and your values of
nare always going to be small (as in your case), so effectively your algorithm isO(1). However, technically speaking, it'sO(n log n), because you're supposed to ignore the constant.当你计算一个函数的 Big-O 时，你总是想要考虑非常非常大的数字。这可以帮助您确定当样本量达到无穷大时（换句话说，当样本量变得非常大时）函数的性能。
通常，在计算 Big-O 后，您还需要查找
n0数字。您可以将这个n0数字视为临界点。任何大于n0的数字的函数的性能将等于Big-O。对于较小的数字，性能将由常数或函数中的其他因素决定。这就是为什么在评估函数性能时仅使用 Big-O 是不够的（尽管这是您应该确定的第一件事）。确定 Big-O 后，您应该对函数进行基准测试或计时，并确定n0临界点，并确定函数在大部分时间处理的样本大小或项目数量。有时您会编写适用于相对较小的数字集（例如 10 或 100）的函数，有时您的函数预计会处理数百万或数十亿的项目。
When you calculate the Big-O for a function you always want to think of very,very large numbers. That helps you determine the performance of your function when the sample size goes to infinity (in other words, when it grows very very large).
Usually, after you compute the Big-O you will also want to look for the
n0number. You can think of thisn0number as the tipping point. The performance of the function with any number larger thann0will be equal to Big-O. For smaller numbers, the performance will be dictated by the constants, or other factors in the function. That is why the Big-O alone is not sufficient when assessing the performance of a function (although it's the first thing you should determine). After you determine the Big-O, you should benchmark or time your function and determine then0tipping point and determine what sample sizes, or number of items, will your function process the majority of the time.Sometime you will write functions that will work on relatively small sets of numbers (say 10s or 100s) and some times your functions will be expected to process items on the order of millions or billions.
当数据大小/输入较小时，您应该考虑该常量。但由于在开发这些算法时，没有考虑上限，因此忽略了常量。
例如：
两者：归并排序和快速排序都是
nlogn。但快速排序有一个很小的常数因子，这就是为什么与合并排序相比，它对于小输入的表现更快。You should consider the constant when your data size/input is small. But since while developing these algorithms, upper bound is not considered, constants are ignored.
For example:
Both: merge sort and quick sort is
nlogn. But quicksort has a small constant factor, that s why it behaves faster for small input compared to merge sort.