并行执行算法的可能性。

我不知道是否有O(log n)和O(1)类的例子，但对于某些问题，当算法更容易并行执行时，您会选择具有更高复杂度类的算法。

有些算法不能并行化，但复杂度很低。考虑另一种算法，它可以达到相同的结果，并且可以很容易地并行化，但具有更高的复杂度类。当在一台机器上执行时，第二种算法速度较慢，但当在多台机器上执行时，实际执行时间越来越短，而第一种算法无法加快速度。

Alistra指出了这一点，但未能提供任何例子，所以我会。

您有一个包含10,000个UPC代码的列表，用于您的商店销售的产品。10位UPC，整数价格(便士价格)和30个字符的收据描述。

O(log N)方法:你有一个排序的列表。ASCII是44字节，Unicode是84字节。或者，将UPC视为int64，将得到42和72字节。10,000条记录——在最高的情况下，您看到的存储空间略低于1mb。

O(1)方法:不存储UPC，而是将其用作数组的一个条目。在最低的情况下，您将看到近三分之一tb的存储空间。

Which approach you use depends on your hardware. On most any reasonable modern configuration you're going to use the log N approach. I can picture the second approach being the right answer if for some reason you're running in an environment where RAM is critically short but you have plenty of mass storage. A third of a terabyte on a disk is no big deal, getting your data in one probe of the disk is worth something. The simple binary approach takes 13 on average. (Note, however, that by clustering your keys you can get this down to a guaranteed 3 reads and in practice you would cache the first one.)

Yes.

在实际情况下，我们运行了一些使用短字符串和长字符串键进行表查找的测试。

我们使用了std::map, std::unordered_map和一个哈希，该哈希最多对字符串长度进行10次采样(我们的键倾向于guidlike，所以这是体面的)，以及一个哈希，对每个字符进行采样(理论上减少了冲突)，一个未排序的向量，其中我们进行==比较，以及(如果我没记错的话)一个未排序的向量，其中我们还存储了一个哈希，首先比较哈希，然后比较字符。

这些算法的范围从O(1) (unordered_map)到O(n)(线性搜索)。

对于中等大小的N，通常O(N)优于O(1)。我们怀疑这是因为基于节点的容器需要我们的计算机在内存中跳跃更多，而基于线性的容器则不需要。

O(lgn)存在于两者之间。我不记得是怎么回事了。

性能差异并不大，在更大的数据集上，基于哈希的表现要好得多。所以我们坚持使用基于哈希的无序映射。

实际上，对于合理的n大小，O(lgn)为O(1)。如果你的计算机在你的表中只有40亿的空间，那么O(lgn)的上界是32。(lg(2^32)=32)(在计算机科学中，lg是log based 2的简称)。

在实践中，lg(n)算法比O(1)算法慢，不是因为对数增长因子，而是因为lg(n)部分通常意味着算法有一定程度的复杂性，并且这种复杂性比lg(n)项中的任何“增长”都增加了更大的常数因子。

然而，复杂的O(1)算法(如哈希映射)很容易具有类似或更大的常数因子。

人们已经回答了你的确切问题，所以我要回答一个稍微不同的问题，人们来这里时可能会想到这个问题。

许多“O(1)时间”算法和数据结构实际上只需要预期的O(1)时间，这意味着它们的平均运行时间是O(1)，可能仅在某些假设下。

常见的例子:哈希表，“数组列表”的扩展(也就是动态大小的数组/向量)。

在这种情况下，您可能更喜欢使用保证时间绝对受对数限制的数据结构或算法，即使它们的平均性能可能更差。 一个例子可能是平衡二叉搜索树，它的运行时间平均较差，但在最坏的情况下更好。

我在这里的回答是，在随机矩阵的所有行的快速随机加权选择是一个例子，当m不是太大时，复杂度为O(m)的算法比复杂度为O(log(m))的算法更快。

在n有界且O(1)算法的常数乘子高于log(n)上的界的任意点。例如，在哈希集中存储值是O(1)，但可能需要对哈希函数进行昂贵的计算。如果数据项可以简单地进行比较(相对于某些顺序)，并且n的边界是这样的，log n明显小于任何一项上的哈希计算，那么存储在平衡二叉树中可能比存储在哈希集中更快。