O(n)的解决方案来解决boggle

Question

解决boggle的函数的最佳时间复杂度O(n)是多少,其中boggle board是n？

我觉得n^2因为每个角色都要看2(n-1)其他角色.采访者认为,这不是n^2一个O(1)字典查找.

Answer 1

我终于弄明白了。答案随着时间的推移呈指数级增长。

想象一下 4X4 的网格

ABCD
EFGH
IJKL
MNOP

那么例如，任何以AABCDHGFEIJKLPONM开头的有序子序列都是一个潜在的单词；以 AEIMNOPLHDCBFJKG 或 AEIMNOPLHGFIK 或 ABCDHLPONMIEFGKJ开头的任何有序子序列也是如此A。然后我们需要查看以 B 开头的潜在单词，然后以 C 开头，等等。

让我们换个角度来看这个问题。假设我们只需要考虑 _ABCD，其中_代表一些起始字符，例如X；那么属于幂集的潜在单词是：

XD; XC; XCD; XB; XBD; etc.

因此，仅考虑从每个字符开始的顺时针螺旋，我们已经在考虑n^2*2^(n-1)。n^2因为网格是n by n这样的，所以对于4 by 4网格来说有 16 个可能的起始字符。并且2^(n-1)因为每个起始角色所领导的力量组。当然，顺时针螺旋并不是唯一可能的模式。但我们已经可以看到第一个模式的时间复杂度：Big-Omega(2^n)，它是指数级的。