我正在查看方法实现的时间复杂度，该方法确定 String 是否包含所有唯一字符 .
基本的暴力方法是一次迭代 String 一个字符，保持所见的字符 HashSet . 对于迭代中的每个字符，我们检查 Set 是否已包含它，如果是，则返回 false . 如果搜索了整个 String ，我们返回 true . 这将是 O(n) 作为最坏情况的复杂性 . 平均情况是什么？ O(n/2) ？
如果我们尝试通过将 String 排序为 char 数组来优化它，那么效率会更高或更低吗？排序通常需要 O(n log n) ，这比 O(n) 更差，但排序 String 允许更早检测到重复字符（特别是对于长字符串） .
我们说最坏的情况是 O(n^2 log n) ，但平均情况更好吗？如果是这样，它是什么？
1 回答
在未排序的情况下，平均情况完全取决于字符串！在不知道/假设任何分布的情况下，很难做出任何假设 .
一个简单的例子，对于一个随机放置字符的字符串，其中一个字符重复一次：
重复字符排列的可能性是
n*(n-1)/2在
k步骤中重复检测到的概率是(k-1)/(n-1)在最多
k步骤中检测到它的概率是(k*(k-1))/(n*(n-1))，这意味着平均而言你将检测到它（对于大n）约0.7071*n... [不完整]对于以不同频率出现的多个字符，或者您对字符串中字符的分布方式做出不同的假设，您将获得不同的概率 .
希望有人可以延伸我的答案！ :)
如果字符串已排序，则您不需要HashSet .
但是，平均情况仍然取决于字符串中字符的分布：如果在开始时得到两个
aa，则它非常有效;如果你得到两个zz，那么你没有赢得任何东西 .最糟糕的情况是排序 plus detection-duplicatelicates，所以
O(n log n + n)，或只是O(n log n).因此，由于平均情况和最差情况下的复杂性增加，预计对字符串进行排序似乎是不利的 .