Big O 如何扩展？
主要问题：
假设我有一些算法，运行时间为 O(n^2)。
我明白了，如果我输入的 n 是原始 n 大小的两倍，我会得到最大时间复杂度的 4 倍。
但它与输入大小为 n 运行算法两次有什么关系呢？
我为什么问：
我之所以问，是因为我做了一个算法，其大O表示法是O(log_2(n))。但运行它并将其与 O(log_2(n)) 进行比较表明，对于 10 亿量级的输入，它的表现要好得多。该算法仅适用于大小为 10k-20k 的输入。这意味着它的性能比 $C_1*log_2(n)$ 好得多，
我知道大 O 表示法是最大值，但感觉就像我问“你有多高？”大 O 表示法回答“我比 40 米短”。
我在谷歌上搜索了一下，发现“大 O”“在工业界”主要用于可扩展性。也就是说，您希望您的 n 达到接近其大 O 的程度。
那么，就我而言，使用大 O 表示法是否有意义？多次运行相同的算法而不是增加输入大小与大 O 表示法有何关系？
Main Question:
Say I have some algorithm, that runs in O(n^2).
I get that, if I input an n twice the size of the original n I get 4 doubling of the maximal time complexity.
But how does it relate to running the algorithm twice with an input size of n?
Why I am asking:
The reason for why I'm asking, is because I made an algorithm whose big O notation was O(log_2(n)). But running it and comparing it to O(log_2(n)) showed, that it performed FAR better for inputs at the magnitude of 1 billion. The algorithm would only be used on inputs the size of 10k-20k. Meaning that it performed wastly better than $C_1*log_2(n)$
I get that big O notation is the maximum, but it felt like I asked "How tall are you?" and the big O notation answered "I am shorter than 40 meters".
I googled around a bit and found, that big O is - "in industry" - primarily used for scalability. I.e you expect your n to reach that point where it will get close to its big O.
Then, in my case, does it even make sense to use big O notation? How does running the same algorithm multiple times, rather than increasing the input size, relate to big O notation?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
实现 O(log n) 算法所需的时间将随着问题规模的增长而变得非常非常缓慢。随着问题规模的增大，它不会变得更快，但增长幅度会很小。
这取决于可用的替代方案。如果有一个更快但“更糟糕”（big-O-wise）的算法，那么确定每个算法的实现速度更快的输入大小是有意义的。然而，从长远来看（对于足够大的 n），O(log n) 总是会胜过 O(n) 算法。如果没有更快的替代方案，为什么还要担心呢？即使您不“需要”它，O(log n) 也很好。
Big-O 仅帮助您选择能够随着问题规模的增长按预期扩展的算法。算法的 big-O 类没有说明该算法的特定实现对于特定输入在特定输入上的执行情况机器。事实上，对于较小的问题，经常使用“坏”算法（例如，O(n^2) 复杂度）而不是“好”算法（例如，O(n log n)），仅仅是因为它们会更快对于这些输入大小。看一下排序：对于非常小的输入，快速排序的许多实现都会回退到插入排序：
java 标准库源代码中的这一行我想到的是：它的作者通过实验确定，对于少于 7 个元素的数组，插入排序比快速排序更快。
Time required by an implementation of an O(log n) algorithm will grow very, very slowly with problem size. It will not become faster with larger problem sizes, but the growth will be minimal.
It depends on the available alternatives. If there is a faster but "worse" (big-O-wise) algorithm, it can make sense determine the input sizes where implementations of each are faster. An O(log n) will, however, always win over, say, O(n) algorithms in the long run (for big enough n). If there is no faster alternative, why worry? O(log n) is good to have, even if you do not "need" it.
Big-O only helps you to choose algorithms that can scale as expected as problem sizes grow. An algorithm's big-O class says nothing about how well a specific implementation of that algorithm will perform for a specific input on a specific machine. Indeed, it is frequent to use "bad" algorithms (with, say, O(n^2) complexity) instead of "good" algorithms (say, O(n log n)) for smaller problems, simply because they will be faster for those input sizes. Look at sorting: many implementations of quicksort fall back to insertsort for very small inputs:
This line in java's standard library source-code comes to mind: its authors have experimentally determined that, for arrays of less than 7 elements, insert-sort is quicker than quicksort.
坏消息是渐近复杂度公式无助于预测实际 N 的算法的运行时间（我什至敢说根本没有帮助）。
因为对于小N，运行时间通常由复杂度的低阶项主导。
对于较大的 N，RAM 模型（对任何地址的恒定时间访问）是无关紧要的。由于缓存和虚拟内存的影响，访问时间可能会相差几个数量级！
另请注意，大 O 分析与最坏情况的复杂性相关，这可能与您尝试的情况相差甚远。即使预期情况的复杂性也可能无关紧要，因为它依赖于特定的输入分布，这可能不切实际，而且离散度可能很大。
The bad news is that the asymptotic complexity formulas don't help predict the running-time of algorithms for practical N (I would even dare say do not help at all).
Because for small N, the running time is usually dominated by the low-order terms of the complexity.
And for larger N, the RAM model (constant-time access to any address) is irrelevant. The access time can vary by several orders of magnitude due to cache and virtual memory effects !
Also note that big-O analysis relates to the worst-case complexity, which can be very far from the cases you try. Even expected-case complexity may be irrelevant, because it relies on a specific input distribution, which can be unrealistic, and dispersion can be large.