搜索不断变化的字符串的 Big O 表示法是什么

Question

我有下面的函数可以找到字符串中最长的非重复子字符串。我知道 for 循环是 O(n)，但是通过在调用函数 indexOf.

时在 tmp 字符串中搜索当前字符，额外的时间是多少

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

Answer 1

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

如果您的字母表有限（例如，如果它只能包含来自 a,b,...,z 的字符）- 那么 [=12= 的长度] 的大小有限（在 a-z 示例中为 26，这来自 pigeonhole principle）。在这种情况下，您可以说 indexOf() 并创建一个新字符串（通过使用运算符 +）花费了 O(1) 时间，因为它正在创建一个具有有限大小的字符串。在这种情况下，该算法需要 O(n) 时间。

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

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

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

搜索不断变化的字符串的 Big O 表示法是什么

What is the BigO notation on searching on a string that keeps changing for a character

java

string

algorithm

big-o

time-complexity