IsUnique：实现一个算法来确定一个字符串是否包含所有唯一字符。
在我的一个版本中，我使用的是 RegExp。谁能向我解释一下这个算法的时间复杂度是多少，为什么？
const isUniqueV2 = function isUniqueV2(str) {
const cleanStr = str.toLowerCase().replace(/[^a-z0-9]/g, '');
const strlen = cleanStr.length;
if(!strlen) return false;
const reg = new RegExp(/(.)[^\1]*?\1/g);
if(reg.test(cleanStr)) return false;
return true;
}
RegExp 的时间复杂度因实现而异。我有一个 O(N) 的版本。我只想知道这个会比使用字典 O(N) 的表现更好吗？
从技术上讲，在最坏的情况下，算法的时间复杂度将为O(N)，但为什么它O(N)有点复杂。需要考虑三个操作。
首先，toLowerCase()在输入字符串上。这是O(N)关于字符串的长度，很容易。
二、第一个.replace功能：.replace(/[^a-z0-9]/g, '')。这也是O(N)- 遍历所有字符，并用空字符串替换非字母数字字符。
第三，也是最复杂的：/(.)[^\1]*?\1/g测试。让我们首先分解这个正则表达式。请注意，\1在字符集内部可能不会执行您认为的那样 - 它不是反向引用，它匹配索引 1 处的 unicode 字符，即标题开始控制字符：
console.log(/[\1]/.test(String.fromCharCode(1)));
console.log(String.fromCharCode(1));
// not the sort of thing that would appear in an ordinary string, as you can see那不是你想要的。为了简单起见，让我们解决这个问题 - 它不会对算法的复杂性产生任何影响，所以让我们假设我们正在使用该模式/(.).*?\1/。
它将捕获组中的第一个字符，然后懒惰重复任何字符，尝试再次找到与第一组匹配的字符。正则表达式引擎将尝试从字符串中的第一个字符开始进行此测试 - 如果字符串长度为N，则它将从 index 开始0并迭代索引0到N - 1，检查是否有任何字符与 index 处的字符匹配0。由于我们假设最坏的情况，我们可以假设这会失败（没有找到第一个字符的重复项），并且我们已经执行了大约 N 次操作。然后，引擎将尝试从下一个索引 index开始匹配1，并将迭代每个后续字符，直到它到达字符串的末尾（N - 1)，查找与索引 1 匹配的相同字符。最坏的情况是，这将失败，我们刚刚执行了 aroundN - 1操作，引擎将向前跟踪另一个字符，到索引 2。看到模式了吗？
Starting index ~Operations required to check this index ~Total operations
0 N N
1 N-1 2N-1
2 N-2 3N-3
3 N-3 4N-6
4 N-4 5N-10
...
N-1 1 N^2 - 0.5N^2
最坏的情况是，字符串中没有重复的字符，引擎会采取一些0.5N^2步骤来执行整个.test功能。这并不准确，因为有一些与匹配捕获的字符相关的开销，但与该N^2因素相比微不足道。在regex101上尝试一下- 您可以看到 62 个字母数字字符的输入需要 2203 步，这与0.5 * 62^2 = 1922.
所以，因为这个.test函数O(N^2)在最坏的情况下具有复杂性，所以听起来整个算法具有O(N^2)复杂性，对吧？其实，不！原因是第一个.replace(/[^a-z0-9]/g, '')确保被测试的字符串将只包含小写字母和数字（36 个可能的字符）。这意味着.test在返回之前最多只能迭代 36 个字符true——第 37 个字符（或之后的任何字符）必然是前一个字符之一的副本，因为只有 36 个可能的唯一字符。最坏情况的字符串看起来像
0123456789abcdefghijklmnopqrstuvwxyzzzzzzzzzzzzzzzzzzzzzz...
这需要一些36N步骤才能到达zs，发现它们是重复的，然后通过.test. 因此，最坏的情况为.test，考虑到输入约束，其实O(N)，不是O(N^2)！
总结一下：这toLowerCase()是O(N)最坏的情况。该.replace是O(N)在最坏的情况下。最后，.test是O(N)在最坏的情况下。因此，您的函数的时间复杂度O(N)处于最坏的情况。
综上所述，尽管它可能是O(N)，但与您的其他实现相比，它仍然相对低效，该实现遍历字符串中的每个字符并将其添加为对象的属性，true一旦找到任何重复字符就返回。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句