algorithm - 该算法的时间复杂度

Question

我一直在阅读有关时间复杂度的一些资料，并且已经掌握了基础知识。为了强化这个概念，我看了一下我最近在 SO 上给出的答案。出于某种原因，这个问题现在已经结束，但这不是重点。我无法弄清楚我的答案有多复杂，在我得到任何有用的反馈之前问题就被关闭了。

The task是找到字符串中的第一个唯一字符。我的回答很简单:

public String firstLonelyChar(String input)
{
    while(input.length() > 0)
    {
        int curLength = input.length();
        String first = String.valueOf(input.charAt(0));
        input = input.replaceAll(first, "");
        if(input.length() == curLength - 1)
            return first;
    }
    return null;
}

Link to an ideone example

我的第一个想法是，由于它会查看每个字符，然后在 replaceAll() 期间再次查看每个字符，所以时间复杂度为 O(n^2)。

但是，它让我开始思考它的实际工作方式。对于检查的每个字符，它会删除字符串中该字符的所有实例。所以n是不断缩小的。那是如何影响它的？这会使它成为 O(log n)，还是有什么我没有看到的？

我在问什么:

所写算法的时间复杂度是多少，为什么？

我没有问的是:

我不是在寻找改进它的建议。我知道可能有更好的方法来做到这一点。我试图更好地理解时间复杂度的概念，而不是找到最佳解决方案。

Answer 1

最糟糕的时间复杂度是字符串 aabb... 等等，每个字符恰好重复两次。现在这取决于字母表的大小，假设是 S。我们还用 L 注释初始字符串的长度。因此，对于每个字母，您都必须遍历整个字符串。但是，第一次这样做时，字符串的大小为 L，第二次为 L-2，依此类推。总体而言，您必须按照 L + (L-2) + ... + (L- S*2) 操作的顺序执行，即 L*S - 2*S *(S+1)，假设 L 大于 2*S。

顺便说一下，如果你的字母表的大小是常数，我想它是，你的代码的复杂性是 O(L)(尽管有一个很大的常数)。