该算法的时间复杂度

问题描述 投票：3回答：4

我一直在阅读关于时间复杂性的阅读，并且我已经掌握了基础知识。为了强化这个概念，我看了一下我最近在这里给出的答案。现在问题已经结束了，但这不是重点。我无法弄清楚我的答案的复杂性是什么，在得到任何有用的反馈之前问题已经结束。

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），还是有些东西我没看到？

我在问什么：

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

我不是要问：

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

algorithm time-complexity
4个回答
4
投票

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

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

1
投票

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

编辑：正如Ivaylo指出的那样，如果你的字母表的大小是不变的，那么从技术上讲，它是O(n)，因为你从不考虑过任何一个角色。

1
投票

让我们来标记：

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

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

总数为：O（m * n）

O（m * n）循环的一个例子是：input = 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）

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
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.