javascript - 无法使用复杂性度量定义更好的算法

Question

我需要编写一个算法来检查字符串中字符的唯一性。我编写了以下算法:

function unique(s) {
    for (var i=0; i<s.length-1; i++) {
        for (j=i+1; j<s.length; j++) {
            if (s[i] === s[j]) {
                return false;
            }
        }
    }
    return true;
}

计算最坏情况下的操作数时，公式为

n/2x(n-1)=(n^2-n)/2

复杂度O(n)=n^2。

现在，我可能编写了以下未优化的算法:

function unique(s) {
    for (var i=0; i<s.length; i++) {
        for (j=0; j<s.length; j++) {
            if ((s[i] === s[j]) && (i!==j)) {
                return false;
            }
        }
    }
    return true;
}

但它给出了相同的0(n)=n^2。所以看来我无法根据 0(n) 判断哪种算法更好 - 这是正确的吗？那么为什么要使用0(n)呢？什么指标可以表明第一个算法比第二个算法更好？

Answer 1

不管表面上如何，你的算法都是 O(n)，而不是 O(n^2)。

s 是一个字符串，字符限制为 16 位。这意味着外层循环最多执行 65536 次，并且只有当字符串的长度正好是 65536 个字符并且每个代码点恰好包含一次时，才会出现这种最大情况。

通过此观察，您可以创建 O(1) 解决方案。只需添加一个初始检查来查看字符串是否长于 65536 个字符，如果是则立即返回 true。如果不是，则使用任一算法来检查字符串是否有重复项。