tldr; 最初发布的代码不应使浏览器崩溃。
下面解释了为什么嵌套循环并不总是对效率不利,并展示了一个反例,当运行超过 100,000 个模拟单词时,原始代码可以成功运行而不会导致浏览器崩溃。
发布的代码的复杂性很低,它应该运行得非常快。它在几分之一秒内执行(不到 20 毫秒!),即使是“20 * 8000” - 即 C * O(n)。请注意,时间复杂度是线性的,因为 checkLetters 中的嵌套循环具有恒定的时间:由于这个小的固定限制(每次调用最多“20 个循环”),它在这里并不代表性能问题。
因此,我认为这不是一个问题,它是一个效率问题。我断言原始代码不会“崩溃”现代浏览器环境。对于更长或未绑定的单词,然后使用(可能)较低复杂度的探测尝试可能会得到回报 - 但内部循环在这里以小的恒定时间运行。(实际上,由于单词中字母的分布和单词长度,我想对于像英语这样的自然语言,常数很少超过“90 个循环”。)
见http://jsfiddle.net/FqdX7/6/
library = []
for (w = 0; w < 100000; w++) {
library.push((w + "12345").slice(0,5))
}
function checkLetters(word){
for(i=0;i<5;i++){
for(j=i+1;j<5;j++){
if(word.charAt(i) == word.charAt(j)){
return false;
}
}
}
return true;
}
$('#time').text("running")
start = +(new Date)
var compLibrary = [];
for (var k=0;k<library.length;k++) {
if(checkLetters(library[k]) == true) {
compLibrary.push(library[k]);
}
}
time = +(new Date) - start
$('#time').text(time + "ms")
在我的机器上(在 Safari 中),对于 100,000 个单词的输入,代码运行时间约为 30毫秒(如果删除了“return false”,则约为 40 毫秒)!
相比之下,使用探针(seenChars 查找)的答案实际上在 Safari/Chrome 中运行得更糟。请参阅http://jsfiddle.net/Hw2wr/5/,其中 100k 字需要大约 270 毫秒 - 或大约慢 9 倍。但是,这高度依赖于浏览器,评论中的jsperf表明,在 Firefox中,探测方法更快(大约 2 倍),但在 IE中再次变慢(比如 4-5 倍)。
YMMV。我认为原始代码对于给定的情况是可以接受的,而“崩溃”问题在其他地方。