昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
整理n双袜子的问题是O（n）。在你把它们扔进洗衣篮之前，你先把左边的衣服穿到右边的衣服上。取出时，你剪下线，把每一对线放进抽屉里——对n对线进行2次操作，所以O（n）。
现在，下一个问题很简单，你是自己洗衣服，还是妻子洗衣服。这可能是一个完全不同领域的问题。：）
其他回答
成本：移动袜子->高，查找/搜索袜子排成一排->小
我们想做的是减少移动次数，并用搜索次数进行补偿。此外，我们还可以利用智人的多威胁环境，在解密缓存中保存更多的东西。
X=您的，Y=您的配偶
从所有袜子的A堆开始：
选择两个袜子，将相应的X袜子放在X线上，将Y袜子放在Y线上的下一个可用位置。
直到A为空。
对于每行X和Y
选择行中的第一只袜子，沿着行搜索，直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时，当前正在查看的袜子与之前的袜子相同，请对这些袜子执行步骤2。
可选地，在第一步中，您从该行中拾取两个袜子，而不是两个，因为缓存内存足够大，我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，那么考虑到受试者的记忆足够大，你可以同时解析三只袜子。
直到X和Y都为空。
Done
然而，由于这与选择排序具有相似的复杂性，由于I/O（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。
理论上的限制是O（n），因为你需要触摸每一只袜子（除非有些袜子已经配对）。
你可以用基数排序实现O（n）。你只需要为桶选择一些属性。
首先你可以选择（她的，我的）-把它们分成两堆，然后使用颜色（可以有任何颜色的顺序，例如按颜色名称的字母顺序）-按颜色将它们分成一堆（记住对同一堆中的所有袜子保持步骤1中的初始顺序），然后袜子的长度，然后是纹理，....
如果您可以选择有限数量的属性，但有足够多的属性可以唯一地标识每对属性，则应该使用O（k*n），如果我们可以考虑k是有限的，则使用O（n）。
我的解决方案并不完全符合您的要求，因为它正式需要O（n）“额外”空间。然而，考虑到我的条件，它在我的实际应用中非常有效。因此，我认为这应该很有趣。
与其他任务合并
我的特殊情况是，我不用烘干机，只是把衣服挂在普通的烘干机上。挂布需要O（n）操作（顺便说一句，我在这里总是考虑垃圾箱包装问题），这个问题本质上需要线性的“额外”空间。当我从桶里拿出一只新袜子时，如果这双袜子已经挂好了，我会试着把它挂在旁边。如果是新袜子，我会在旁边留出一些空间。
Oracle机器更好；-）
显然，这需要一些额外的工作来检查是否有匹配的袜子已经挂在某个地方，这将为计算机提供系数约为1/2的解O（n^2）。但在这种情况下，“人为因素”实际上是一种优势——如果匹配的袜子已经挂起，我通常可以很快（几乎为O（1））识别出它（可能涉及到大脑缓存中的一些难以察觉的因素）——将其视为一种有限的“预言机”，如oracle Machine；-）我们人类在某些情况下比数字机器有这些优势；-）
快到O（n）！
因此，将袜子配对的问题与挂布的问题联系起来，我可以免费获得O（n）“额外的空间”，并有一个及时的解决方案，大约O（n），只需要比简单的挂布多一点的工作，即使在非常糟糕的星期一早晨，也可以立即获得一双完整的袜子…；-）
真实世界方法：
尽快将袜子从未分类的袜子堆中取出，一次一个，然后放在前面。桩应布置得有一定的空间效率，所有袜子指向相同的方向；桩的数量受你容易到达的距离的限制。选择一堆袜子时，应尽快将袜子放在一堆看起来很像的袜子上；偶尔出现的I型（把袜子放在不属于它的袜子堆上）或II型（当有一堆类似的袜子时，把袜子放进自己的袜子堆里）错误是可以容忍的——最重要的考虑是速度。
一旦所有袜子都成了一堆，快速穿过多个袜子堆，创建成对的袜子，然后将它们取下（这些袜子朝抽屉方向）。如果袜子堆中有不匹配的袜子，请将它们重新堆到最好的位置（在尽可能快的限制范围内）。当处理完所有的多袜子堆后，将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦，你完了——我有很多袜子，直到大部分都脏了才洗。另一个实际注意事项是：我将一双袜子的顶部翻转到另一双袜子上，利用它们的弹性财产，以便它们在被运送到抽屉和抽屉中时保持在一起。
我所做的就是拿起第一只袜子，把它放下（比如，放在洗衣碗的边缘）。然后我拿起另一只袜子，检查它是否与第一只袜子相同。如果是，我会把它们都去掉。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子，将其与前两只袜子进行比较（如果它们还在的话）。等
这种方法可以很容易地在阵列中实现，假设“移除”袜子是一个选项。实际上，你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序（见下文），那么您只需移动它们，就可以得到一个数组，该数组中所有袜子都成对排列。
假设袜子的唯一操作是比较相等，这个算法基本上仍然是n2算法，尽管我不知道平均情况（从未学会计算）。
当然，分类可以提高效率，尤其是在现实生活中，你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中，树也可以做到这一点，但这是额外的空间。当然，我们又回到了NlogN（或者更多，如果有几只袜子按排序标准是相同的，但不是来自同一双）。
除此之外，我想不出什么，但这种方法在现实生活中似乎非常有效
