假设我有N个未排序的整数数组。我想找到这些数组的交集。
解决这个问题有两种好方法。
首先，我可以使用nlogn排序对数组进行适当的排序，比如QuickSort或MergeSort。然后我可以在每个数组的开头放一个指针。将每个数组与其下面的数组进行比较，迭代较小的数组[pointer]的指针，或者如果它们都相等，则您找到了交集。
这是一个O（nlogn）解决方案，具有恒定的内存（因为一切都是在适当的位置完成的）。
第二种解决方案是使用哈希映射，将第一个数组中出现的值作为键，然后在遍历其余数组时递增这些值（然后获取所有值为N的值）。这是一个O（n）解决方案，具有O（n）内存，其中n是所有阵列的总大小。
理论上，前者的解是o（nlogn），后者是o（n）。然而，由于碰撞，项目可以随机分散在哈希图中，因此哈希图没有很好的局部性。另一个解决方案，虽然是o（nlogn），但一次遍历一个数组，显示出极好的局部性。由于CPU倾向于将当前索引旁边的数组值从内存中拉入缓存，因此O（nlogn）解决方案将比哈希映射解决方案更频繁地访问缓存。
因此，给定一个非常大的数组大小（随着元素数量的无穷大），o（nlogn）解实际上比o（n）解快是否可行？
对于整数，可以使用非比较排序（请参阅计数，基数排序）。一个大集合可能被编码，例如按顺序运行到范围中。这将压缩数据集，并允许跳过大块（请参阅RoaringBitmaps）。有可能对硬件友好，并具有O（n）复杂性。
复杂性理论不考虑常数。正如你所怀疑的，由于隐藏的常数，具有更高复杂性的算法总是有可能比其他算法更快。通过利用问题的性质，例如将解决方案限制为整数，存在通用方法无法实现的潜在优化。好的算法设计通常需要理解和利用这些约束。