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。如果不是，则使用您的任一算法检查字符串是否重复。