Big O 如何扩展？
How Does Big O Scale?
主要问题：
假设我有一些算法，运行时间复杂度为 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 表示法有什么关系？
is there then anymore I can gather from the algorithm being O(log(n)) other than, it will be faster than that in the long run?
实现 O(log n) 算法所需的时间会随着问题的大小增长得非常非常慢。它不会随着问题规模的增加而变得更快，但增长将是最小的。
Or would it be "useless" for me to use in practice, with input sizes of my dimension?
这取决于可用的备选方案。如果有更快但“更差”(big-O-wise) 的算法，则确定每个实现更快的输入大小是有意义的。然而，O(log n) 总是会在长 运行（对于足够大的 n）中赢得 O(n) 算法。如果没有更快的选择，为什么要担心？ O(log n) 很好，即使你并不“需要”它。
Big-O 只会帮助您选择可以随着问题规模的增长按预期扩展 的算法。一个算法的 big-O class 说 没有 关于该算法的 特定实现 对 [=22] 的执行情况=]特定输入 特定机器。事实上，对于较小的问题，经常使用“坏”算法（例如，复杂度为 O(n^2)）而不是“好”算法（例如，O(n log n)），因为它们会更快对于那些输入尺寸。查看排序：对于非常小的输入，快速排序的许多实现都回退到插入排序：
想到 java 的标准库 source-code 中的 This line：它的作者通过实验确定，对于少于 7 个元素的数组，insert-sort 是比快速排序更快。
坏消息是渐近复杂度公式无助于预测 running-time 实际 N 的算法（我什至敢说根本没有帮助 ).
因为对于小 N，运行 时间通常由 low-order 项的复杂性决定。
而对于较大的 N，RAM 模型（constant-time 访问任何地址）是无关紧要的。由于高速缓存和虚拟内存效应，访问时间可能相差几个数量级！
另请注意，big-O 分析涉及 worst-case 复杂性，这可能与您尝试的情况相去甚远。即使 expected-case 复杂度也可能无关紧要，因为它依赖于特定的输入分布，这可能是不现实的，而且离散度可能很大。
主要问题：
假设我有一些算法，运行时间复杂度为 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 表示法有什么关系？
is there then anymore I can gather from the algorithm being O(log(n)) other than, it will be faster than that in the long run?
实现 O(log n) 算法所需的时间会随着问题的大小增长得非常非常慢。它不会随着问题规模的增加而变得更快，但增长将是最小的。
Or would it be "useless" for me to use in practice, with input sizes of my dimension?
这取决于可用的备选方案。如果有更快但“更差”(big-O-wise) 的算法，则确定每个实现更快的输入大小是有意义的。然而，O(log n) 总是会在长 运行（对于足够大的 n）中赢得 O(n) 算法。如果没有更快的选择，为什么要担心？ O(log n) 很好，即使你并不“需要”它。
Big-O 只会帮助您选择可以随着问题规模的增长按预期扩展 的算法。一个算法的 big-O class 说 没有 关于该算法的 特定实现 对 [=22] 的执行情况=]特定输入 特定机器。事实上，对于较小的问题，经常使用“坏”算法（例如，复杂度为 O(n^2)）而不是“好”算法（例如，O(n log n)），因为它们会更快对于那些输入尺寸。查看排序：对于非常小的输入，快速排序的许多实现都回退到插入排序：
想到 java 的标准库 source-code 中的This line：它的作者通过实验确定，对于少于 7 个元素的数组，insert-sort 是比快速排序更快。
坏消息是渐近复杂度公式无助于预测 running-time 实际 N 的算法（我什至敢说根本没有帮助 ).
因为对于小 N，运行 时间通常由 low-order 项的复杂性决定。
而对于较大的 N，RAM 模型（constant-time 访问任何地址）是无关紧要的。由于高速缓存和虚拟内存效应，访问时间可能相差几个数量级！
另请注意，big-O 分析涉及 worst-case 复杂性，这可能与您尝试的情况相去甚远。即使 expected-case 复杂度也可能无关紧要，因为它依赖于特定的输入分布，这可能是不现实的，而且离散度可能很大。