时间戳

首页 > 解决方案 > 什么是搜索不断变化的字符的字符串的 BigO 表示法

java - 什么是搜索不断变化的字符的字符串的 BigO 表示法

问题描述

我有下面的函数，可以找到字符串中最长的非重复子字符串。我知道 for 循环是 O(n) 但是通过在调用函数的 tmp 字符串中搜索当前字符将是额外的时间indexOf。

public static String find(String input) {
    String currentLongest = input.length() > 0 ? "" + input.charAt(0) : "";
    String tmp = currentLongest;
    for (int i = 1; i < input.length(); i++) {
        int index = tmp.indexOf(""+input.charAt(i));
        if (index  == -1) {
            tmp = tmp + input.charAt(i);
            if (tmp.length() > currentLongest.length())
                currentLongest = tmp;
        } else
            tmp = tmp.substring(index+1)+input.charAt(i);
    }
    return currentLongest;
}

标签： javastringalgorithmtime-complexitybig-o

解决方案

indexOf()和重新创建tmp（使用运算符+）都发生在每次迭代中，都需要时间O(|S|)，其中|S|是tmp本次迭代的长度。现在，问题是tmp有界的长度？

如果您的字母表是有限的（例如，如果它只能包含来自 a、b、...、z 的字符） - 那么长度的tmp大小是有限的（在 az 示例中为 26，这来自鸽洞原理）。在这种情况下，您可以说indexOf()创建一个新字符串（通过使用运算符 +）需要O(1)时间，因为它正在创建一个有界大小的字符串。在这种情况下，算法需要O(n)时间。

但是，如果字母表是无限制的，您可以输入一个完全没有重复的字符串。在这种情况下，循环的每次迭代都需要O(i)时间。这给了你。

1 + 2 + ... n = n (n+1)/2

在 中O(n^2)，算法的复杂度变为O(n^2)

推荐阅读