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

Question

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

算法1

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

假设charAt方法的运行时间为O(1)，则第一个算法为O(N)，第二个为O(N^2)。对于所有输入，线性时间算法不应该比二次算法更快。它会比某个 N（可能是数百万）后的二次方更快。

例如：

void funcA(int n){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < 10000; j++){
            int k = i + j;
        }
    }
}


void funcB(int n){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            int k = i + j;
        }
    }
}

尽管 funcA 是线性的而 funcB 是二次的，但很容易看出当 n < 10000 时 funcB 将比 funcA 更快。在您的情况下，hashSet 需要时间来计算哈希值，因此输入速度可能较慢一定大小。

Answer 2

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

Answer 3

您的测试数据有问题，例如，如果您将自己限制为英语字符 (a-z)，如果字符串长度 > 26，您肯定会重复。在具体示例中，您提供了字符串"abcdefghijklmnopqrstuvwxxyz" 已排序，并在末尾找到重复元素 x。因此，迭代数组查找速度更快，因为在您继续解析字符串时构建 HashSet 会产生开销。

一个更好的测试是用随机生成的大整数序列和一个大的最大值来测试这个，例如Long.MAX_VALUE

下面的测试反驳了您关于数组搜索更快的断言。运行多看几次，自己看看。或者你可以取 1000 次运行的平均值，等等：

public class FindDuplicatesTest {

  public static final String s = generateRandomString(100000);

  private static String generateRandomString(int numChars) {
    Random random = new Random();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < numChars; i++) {
      int codePoint = random.nextInt(65536);
      sb.append(Character.toChars(codePoint));
    }
    return sb.toString();
  }

  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;
  }

  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;
  }

  public static void main(String[] args) {
    FindDuplicatesTest app = new FindDuplicatesTest();

    long start = System.nanoTime();
    boolean result = app.isUnique(s);
    long stop = System.nanoTime();
    System.out.println(result);

    System.out.println("HashSet Search Time: " + (stop - start));

    start = System.nanoTime();
    result = app.isUnique2(s);
    stop = System.nanoTime();
    System.out.println(result);

    System.out.println("Array Search Time: " + (stop - start));

  }
}

Answer 4

您正在进行的微基准测试可能会提供有关算法复杂性的误导性信息。

您的算法很容易 "port" 检查整数数组中的重复项。

然后我建议测试 10^7 元素数组的性能，您肯定会看到差异。

这样您就可以确认您最初对哈希集的正确估计 O(N) 与第二个 "loop" 版本的 O(N^2)。

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

What is the complexity of these two string based algorithms?

java

algorithm

performance

big-o

time-complexity