algorithm - O(n) 解决问题的解决方案

Question

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

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

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)，因此您是错误的。目前，我想不出在这种假设下具有更好时间复杂度的算法。