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

Question

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

我觉得这是n^2因为对于每个角色，我们必须看看2(n-1)其他角色。面试官争辩说这不是n^2为了O(1)查字典。

Answer 1

字典的功能还不是很清楚。

有点傻，但我认为正确的答案如下：

由于在 boggle 中，单词可以采用任意方式（从每个字符到该单词中尚未使用的任何相邻（水平、垂直或对角线）字符），对于长度为 的单词，单词的L组合最多可达 ，8^L除非您消除字符出现多次的组合。无论如何，考虑L到是常数（因为使用的字典是常数），这个值也是常数。总而言之，从给定位置开始查找单词的时间复杂度为O(1).

所以剩下的是单词的起始位置，它在空间中n^2，所以你的 boggle 求解器的时间复杂度是O(n^2)，你是对的。

如前所述，我认为这种论证有点愚蠢。

问题可能是不想将字典视为常量，因为它非常大。假设它无限大，但它实现了对现有单词O(1)的查找（这是我们可以用于字典的唯一查询，特别是没有查找单词前缀），并进一步假设不是限制因素与字长相比，时间复杂度是指数级的。但我认为在本练习中，查找仅对现有单词成功的假设是错误的。n

另一个可能的假设是，字典查找单词前缀（返回是否存在以给定字符串开头但不一定等于字符串的单词）。在这种情况下，我们可以实现一个更好、更复杂的算法来搜索有限的搜索空间（每个字符最多使用一次）。字长的一个限制因素是n^2，因为没有一个字（包含在当前的 boggle board 中）可以比这个长（因为我们只能使用每个字符一次）。同样，起始位置在空间中n^2，因此基于路径的愚蠢算法的时间复杂度为O(n^4)，所以你错了. 目前，在这种假设下，我想不出具有更好时间复杂度的算法。

Answer 2

看看http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html。动态规划解决方案是 O(D)，其中 D 是字典的大小。

Answer 3

我终于弄明白了。答案在时间上是指数级的。

想象一个 4X4 拼图网格

ABCD
EFGH
IJKL
MNOP

那么例如，任何以AABCDHGFEIJKLPONM 开头的有序子序列都是潜在词；A以 AEIMNOPLHDCBFJKG 或 AEIMNOPLHGFIK 或 ABCDHLPONMIEFGKJ开头的任何有序子序列也是如此。然后我们需要查看以 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)，它是指数的。