Ask HN：拼图的 Big-O 复杂度是多少？
1 分•作者: AnimalMuppet•4 个月前
假设我有一个由 n 块拼图组成的拼图游戏？如果我完全没有参考图（也许它完全是白色的，或者类似的东西），那么复杂度是否为 O(n!)，因为我需要查看是否可以将每一块拼图与其他所有拼图连接起来？
但它不仅仅是一个线性排列。它是一个矩形（或者可能是正方形）。那么，如果它是一个正方形（大小为 m * m，其中 m = sqrt(n)），这会如何改变复杂度？
然后你有边框，大小为 4m。至少你可以识别出这些拼图（除非某些内部拼图有直线边，这在某些拼图中会发生）。这会如何改变复杂度？
然后你有参考图。这会给你提供更多信息。至少，它让你能够根据拼图上的图案将拼图分成不同的组。那么，在实践中，实际的复杂度是多少？是类似 O(n^2) 吗？
当然，一定有一些关于这方面的文献。有人知道吗？
查看原文
Let's say I have a jigsaw puzzle with n pieces? If you get no help from the picture (maybe it's completely white or something), then is the complexity O(n!), because I have to see if I can join every piece to every other?<p>But it's not just a linear array. It's a rectangle (or perhaps square). So if it's a square (of size m * m, where m = sqrt(n)), how does that change the complexity?<p>And then you have the border, of size 4m. At least <i>those</i> pieces you can identify (unless some interior pieces have straight edges, which happens in some puzzles). How does <i>that</i> change the complexity?<p>And then you have the picture. This gives you far more information. If nothing else, it lets you sort the pieces into buckets, based on what is pictured on them. So in practice, what's the actual complexity? Is it something like O(n^2)?<p>Surely there must be some literature on this. Does anyone know?