考虑大小为“N”的哈希表。

如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）

我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章

让“N”对应于袜子独特颜色/图案数量的近似上限。

一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）

拿起第一只袜子放在桌子上。现在再挑一只袜子；如果它与第一个拾取的匹配，请将其放在第一个拾取上。如果没有，把它放在桌子上，离第一个小距离。挑选第三只袜子；如果它与前两个匹配，请将它放在它们的上面，或者将它放置在距离第三个的一小段距离处。重复上述步骤，直到你捡起所有袜子。

这是基于比较的模型中的Omega（n log n）下限。（唯一有效的操作是比较两只袜子。）

假设你知道你的2n只袜子是这样排列的：

p1 p2 p3。。。pn pf（1）pf（2）。。。功率因数（n）

其中f是集合{1,2，…，n}的未知排列。知道这一点不会使问题变得更难。有n个！可能的输出（上半部分和下半部分之间的匹配），这意味着您需要log（n！）=Omega（n log n）比较。这可通过分类获得。

由于您对元素区别性问题的连接感兴趣：证明元素区别性的Omega（n log n）界限比较困难，因为输出是二进制的yes/no。这里，输出必须是匹配的，并且可能输出的数量足以获得一个合适的界限。然而，有一个变量与元素的区别有关。假设你有2n只袜子，想知道它们是否可以唯一配对。您可以通过将（a1，a2，…，an）发送到（a1，a1，a2、a2，…、an，an）来获得ED的缩减。（附带地，通过拓扑结构，ED的硬度证明非常有趣。）

我认为，如果只允许等式测试，那么原始问题应该有一个Omega（n2）边界。我的直觉是：考虑一个测试后添加边的图形，并认为如果图形不密集，则输出不是唯一确定的。

我所做的就是拿起第一只袜子，把它放下（比如，放在洗衣碗的边缘）。然后我拿起另一只袜子，检查它是否与第一只袜子相同。如果是，我会把它们都去掉。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子，将其与前两只袜子进行比较（如果它们还在的话）。等

这种方法可以很容易地在阵列中实现，假设“移除”袜子是一个选项。实际上，你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序（见下文），那么您只需移动它们，就可以得到一个数组，该数组中所有袜子都成对排列。

假设袜子的唯一操作是比较相等，这个算法基本上仍然是n2算法，尽管我不知道平均情况（从未学会计算）。

当然，分类可以提高效率，尤其是在现实生活中，你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中，树也可以做到这一点，但这是额外的空间。当然，我们又回到了NlogN（或者更多，如果有几只袜子按排序标准是相同的，但不是来自同一双）。

除此之外，我想不出什么，但这种方法在现实生活中似乎非常有效

理论上的限制是O（n），因为你需要触摸每一只袜子（除非有些袜子已经配对）。

你可以用基数排序实现O（n）。你只需要为桶选择一些属性。

首先你可以选择（她的，我的）-把它们分成两堆，然后使用颜色（可以有任何颜色的顺序，例如按颜色名称的字母顺序）-按颜色将它们分成一堆（记住对同一堆中的所有袜子保持步骤1中的初始顺序），然后袜子的长度，然后是纹理，....

如果您可以选择有限数量的属性，但有足够多的属性可以唯一地标识每对属性，则应该使用O（k*n），如果我们可以考虑k是有限的，则使用O（n）。

由于人脑的结构与现代CPU完全不同，所以这个问题毫无实际意义。

人类可以利用“找到匹配的对”这一事实来战胜CPU算法，这对于一个不太大的集合来说是一个操作。

我的算法：

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但通常很丰富。