j******2
发帖数: 362 | 1 是不是
n*n*pow(8, n*n)
感觉好恐怖 |
p*****2
发帖数: 21240 | |
j******2
发帖数: 362 | 3 式子列对了吧，二爷？
【在 p*****2 的大作中提到】
: 为什么恐怖呢？
|
j******2
发帖数: 362 | 4 是不是
n*n*pow(8, n*n)
感觉好恐怖 |
p*****2
发帖数: 21240 | |
j******2
发帖数: 362 | 6 式子列对了吧，二爷？
【在 p*****2 的大作中提到】
: 为什么恐怖呢？
|
b*******l
发帖数: 590 | 7 顶一下，我也想知道这个问题的答案，哪位大侠给个说法？ |
t*******3
发帖数: 734 | 8 一个naive的计算方法：
对于n*n的格子：
sum_{i=1,n^2}(n*n)*n*4^(i-1)=n^2 pow(4,n^2)
跟你的很接近。当然我的是上下左右4个方向。 如果对角线算起来，就是n^2 pow(8,n^
2).
【在 j******2 的大作中提到】
: 是不是
: n*n*pow(8, n*n)
: 感觉好恐怖
|
b*******l
发帖数: 590 | 9 对啊，为啥你多了个n^2呢？
n^
【在 t*******3 的大作中提到】
: 一个naive的计算方法：
: 对于n*n的格子：
: sum_{i=1,n^2}(n*n)*n*4^(i-1)=n^2 pow(4,n^2)
: 跟你的很接近。当然我的是上下左右4个方向。 如果对角线算起来，就是n^2 pow(8,n^
: 2).
|
t*******3
发帖数: 734 | 10 我写错了。 我多写了n^2.
我的结果跟你的是一样地。
不过这个计算方法是有错误的。
尤其是等word长度比较大的时候。 不是指数形式。 而是最多power级。因为要考虑一
些点已经visit过了。
【在 b*******l 的大作中提到】
: 对啊，为啥你多了个n^2呢？
:
: n^
|
n*******w
发帖数: 687 | 11 用big O表示的话，基本是lz说的那样。
最长word可能没有n平方那么长，指数上的n平方可以写成 min(n^2, word_limit)
可以用各种数据结构帮助剪枝。暴利递归解n=4大概是5分钟数量级。
tries可以到0.3s。上次看到有面试官问剪枝可以优化多少倍。最后答案是至少1000倍
以上。
听说过最快的是做到0.1s。大概就是把1M个单词文件读进内存的速度。解4*4几乎不需
要时间。
【在 t*******3 的大作中提到】
: 我写错了。 我多写了n^2.
: 我的结果跟你的是一样地。
: 不过这个计算方法是有错误的。
: 尤其是等word长度比较大的时候。 不是指数形式。 而是最多power级。因为要考虑一
: 些点已经visit过了。
|
b*******l
发帖数: 590 | 12 怎么利用数据库结构的帮助剪枝啊？大侠能否给个标准答案？我看网上的算法好像都是
那种很慢的。我自己运行了一下，真的很慢啊。
在下先谢过了。
【在 n*******w 的大作中提到】
: 用big O表示的话，基本是lz说的那样。
: 最长word可能没有n平方那么长，指数上的n平方可以写成 min(n^2, word_limit)
: 可以用各种数据结构帮助剪枝。暴利递归解n=4大概是5分钟数量级。
: tries可以到0.3s。上次看到有面试官问剪枝可以优化多少倍。最后答案是至少1000倍
: 以上。
: 听说过最快的是做到0.1s。大概就是把1M个单词文件读进内存的速度。解4*4几乎不需
: 要时间。
|
n*******w
发帖数: 687 | 13 标准答案算不上。可以说说我test过的数据结构吧。
1. 最黄最暴力的就是从matrix的任一位置开始，8个方向能走的全试试，走一步看走过
的路径组成单词是不是在dictionary里边。即使当前路径不是valid单词，也要继续往
下走。n=4运行时间数量级在5分钟。假设dictionary是1百万个单词量级
2. 稍微不那么黄的暴力解法是，对于dictionary里边的每个单词，去matrix里边走看
能不能走通。感觉上单词百万级会更慢，实际上可以降低运行时间到一分钟之内。原因
是，每个单词去走的时候，不需要每走一步就检测是不是合法单词，不合法直接退出，
大量的剪枝了。
3. 把dictionary建trie，这样在matrix里边每走一步都检查trie是不是能往下走。如
果当前prefix就已经invalid了，那这条路就不可能走出单词了。运行时间几乎等于建
trie的时间，大概是0.3s量级。
建trie的过程大概是建立一个27叉树，分别存a-z（不考虑case）以及结束标志比如$。
每个node不用存字符本身，存一个bool值就行。true表示这个路径存在否则不存在。相
当于把a-z map到0-25。
4. hashtable还没用过。如果建hashtable去剪枝，可以把matrix里边所有可能的两个
相邻字符存到hashtable里。key是两个相邻字符，value是这两个字符的位置信息。
然后对于每一个单词，每次取两个字符，看hashtable里边有没有这个key。并且检查
value是不是能跟之前走过的地方连起来并且合法。运行时间比trie更快，大概快一倍。
没试过相邻3个字符，估计还能加速。
欢迎提出更好的算法
【在 b*******l 的大作中提到】
: 怎么利用数据库结构的帮助剪枝啊？大侠能否给个标准答案？我看网上的算法好像都是
: 那种很慢的。我自己运行了一下，真的很慢啊。
: 在下先谢过了。
|
b*******l
发帖数: 590 | |
