java - 这两种基于字符串的算法的复杂度是多少？

Question

我编写了这两个算法来检查字符串中是否有重复字符(ABBC、AAAC)。第一种使用 hashset 数据结构，而第二种完全依赖于迭代。

算法一

String s = "abcdefghijklmnopqrstuvwxxyz";

public boolean isUnique(String s) {

        Set<Character> charSet = new HashSet<Character>();

        for(int i=0; i<s.length(); i++) {
            if(charSet.contains(s.charAt(i))) {
                return false;   
            } 
            charSet.add(s.charAt(i));
        }   
        return true;
}

算法2

String s = "abcdefghijklmnopqrstuvwxxyz";

public boolean isUnique2(String s) {

        for(int i=0; i<s.length()-1; i++) {
            for(int j = i+1; j<s.length(); j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
}

我的想法是，第一个算法是O(N)，第二个算法是O(N^2)。当我在我的(可能不可靠的)笔记本电脑上运行执行时间测试时，第一个算法的平均速度是 2020ns，而第二个算法是 995ns。这违背了我对算法复杂性的计算，有人可以告诉我吗？

Answer 1

当使用 O() 表示法时，您会忽略常量，这意味着 O(n) == (10^10*n)。因此，虽然 O(n^2)>O(n) 渐近为真，但对于较小的 n 值则不一定为真。在您的情况下，想象一下调整哈希集后面的数组的大小可能比迭代输入更耗时。