3

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

任务是找到字符串中的第一个唯一字符。我的回答很简单：

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

链接到一个ideone示例

我的第一个想法是，由于它查看每个字符，然后在 期间再次查看每个字符，replaceAll()它将是 O(n^2)。

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

我在问什么：

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

我不是在问什么：

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

4

4 回答 4

4

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

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

于 2013-02-20T16:17:43.303 回答
1

最坏的情况是O(n^2)n 是输入字符串的长度。想象一下除了最后一个字符之外每个字符都加倍的情况，例如“aabbccddeeffg”。然后有 n/2 次循环迭代，每次调用replaceAll都必须扫描整个剩余的字符串，这也与 成正比n。

编辑：正如 Ivaylo 指出的那样，如果您的字母表的大小是恒定的，那么从技术上讲，O(n)因为您从不多次考虑任何字符。

于 2013-02-20T16:16:08.557 回答
1

让我们标记：

m = 单词中唯一字母的数量
n = 输入长度

这是复杂度计算：
主循环最多进行m次，因为有 m 个不同的字母，
.Replaceall 在每个循环中最多检查 O(n) 次比较。

总数为：O(m*n)

O(m*n) 循环的示例是：输入 = aabbccdd，

m=4, n=8

算法阶段：

1. input = aabbccdd, complex - 8
2. input = bbccdd, complex = 6
3. input = ccdd, complex = 4
4. input = dd, complex = 2

总计 = 8+6+4+2 = 20 = O(m*n)

于 2013-02-20T16:26:32.820 回答
1

让m你的字母表的大小，让n你的字符串的长度。更糟糕的情况是在字母之间均匀分布字符串的字符，这意味着字母表n / m中的每个字母都有字符，让我们用 . 标记这个数量q。例如，字符串aabbccddeeffgghh是字母之间均匀分布的16字符a-h，所以这里n=16和m=8你有q=2每个字母的字符。

现在，您的算法实际上是遍历字母表中的字母（它只使用它们在字符串中出现的顺序），并且对于每次迭代，它必须遍历字符串的长度（n）并将其缩小q（n -= q）。因此，在最坏的情况下，您执行的所有操作数量是：

s = n + n-(1*q) + ... + n-((m-1)*q)

您可以看到这s是算术级数的第一个m元素的总和：

s = (n + n-((m-1)*q) * m / 2 =  
    (n + n-((m-1)*(n/m)) * m / 2 ~ n * m / 2
于 2013-02-20T17:02:23.800 回答