我必须打印出字符串中字符的出现次数。我使用了这样的东西：
String str="This is sample string";
HashSet<Character> hc= new HashSet<Character>();
for (int i = 0; i < str.length(); i++) {
if(!Character.isSpaceChar(str.charAt(i)) && hc.add( str.charAt(i)) ) {
int countMatches = StringUtils.countMatches(str, str.charAt(i));
System.out.println(str.charAt(i)+" occurs at "+countMatches +" times");
}
}
这是一种解决方案，但是我如何分析时间复杂度呢？我是初学者，所以请指导我完成学习过程。
首先，如果你正在寻找一个体面的复杂性分析介绍，下面的一个看起来不错：
- Dionysis Zindros对算法复杂性分析的温和介绍。
我建议您仔细阅读所有内容，并花时间进行页面中嵌入的练习。
代码的复杂性并非微不足道。
从表面上看，循环将执行 N 次，其中 N 是输入字符串的长度。 但是，如果我们看一下循环的作用，它可以做以下三件事之一：
- 如果字符是空格，则不执行任何其他操作
- 如果字符不是空格，则会将其添加(或重新添加(到哈希映射中
- 如果添加了该字符，则调用
countMatches。
无所事事的复杂性是O(1).
向地图添加条目的复杂性O(1)。
调用countMatches的复杂性是O(N)，因为它查看的是字符串的每个字符。
现在，如果我们考虑代码在做什么，我们可以很容易地识别最佳和最坏情况。
-
当字符串的所有 N 个字符都是空格时，会出现最好的情况。 这给出了
O(1)循环体的O(N)重复，给出了O(N)的最佳情况复杂性。 -
当所有 N 个字符都不同时，会发生最坏的情况。 这给出了
O(N)循环体的O(N)重复，给出了O(N^2)的最坏情况复杂性。 (你会认为...但请继续阅读！
一般情况呢？ 如果我们不更多地了解输入字符串的性质，这很困难。
如果随机选择字符，则重复字符的概率较小- ，空格字符的概率较小。
- 如果字符是字母文本，则空格更频繁，重复也是如此。 实际上，对于英语文本字符可能仅限于大写和小写拉丁字母(52(以及少量标点符号。 因此，对于一个长字符串，您可能会期望大约 60 个映射条目，并且性能会迅速收敛到
O(N).
最后，即使是最坏的情况也不是真的O(N^2)。 字符串是char值的序列，Javachar值限制为 0 到 65535 的范围。 因此，在 2^16 个不同的字符之后，所有字符都必须重复，因此即使是最坏的情况也会O(N)，因为N会变成无穷大。
(我确实提到过这不平凡？ 😀 (
这里你需要做的是解释必须采取多少步骤与字符串的长度。
对于字符串中的每个字符，它必须调用countMatches一次。每次调用countMatches都必须再次遍历字符串的每个字符以对它们进行计数。
其他操作(确定字符串的长度、添加到 HashSet、按索引从字符串中检索字符、检查空格、打印答案(假定为常量时间，无关紧要。
某些字符将被跳过的事实(因为它们是空格或已经在 HashSet 中(并不能降低不受限制字符串的复杂性。您可以假设所有字符都不同的最坏情况。
这就是 O(n^2(，其中 n 是字符串的长度。
您可以通过将 HashSet 更改为计数器的 HashMap 来将其改进为 O(n(。然后，您只需要在 String 上进行一次传递，而不是两次嵌套传递。