在一个Java应用程序中，我有以下算法用于"具有K个不同字符的最长子串"，如下所示：
输入：字符串="araaci"，K = 2输出：4说明：不超过"2"个不同字符的最长子字符串是"araa"。
输入：字符串="cbbebi"，K = 3输出：5说明：不超过'3'个不同字符的最长子字符串是"cbbeb"和"bbebi"。
下面是代码：
public static int longestSubstring(String str, int k) {
Map<Character, Integer> map = new HashMap<>();
int maxLength = 0;
int l = 0;
for (int r = 0; r < str.length(); r++) {
char cRight = str.charAt(r);
map.put(cRight, map.getOrDefault(cRight, 0) + 1);
while (map.size() > k) {
char cLeft = str.charAt(l);
map.put(cLeft, map.getOrDefault(cLeft, 0) - 1);
if (map.get(cLeft) == 0) {
map.remove(cLeft);
}
l++;
}
maxLength = Math.max(maxLength, r - l + 1);
}
return maxLength;
}我无法理解以下定义的时间复杂度：
- 时间复杂度**上述算法的时间复杂度为O（N），其中"N"是输入字符串中的字符数。外部for循环对所有字符运行，内部while循环对每个字符只处理一次，因此算法的时间复杂度为O（N + N），这与O（N）渐近等价。
所以，我认为当while循环在另一个for循环中时，我认为时间复杂度是O（n^2），但这里我无法理解"内部while循环只处理每个字符一次"，如果它是正确的，你能解释一下这种状态吗？
1条答案
按热度按时间fnx2tebb1#
为了分析一个算法的复杂性，大多数时候你需要详细了解代码的功能（你不需要了解它的功能是否正确）。使用代码的结构（例如，循环是否嵌套）或仅仅着眼于全局通常是一个坏主意。换句话说，计算一个算法的复杂性需要花费大量的时间。
正如您所说的，"内部while循环只处理每个字符一次"，这确实值得注意，但在我看来这还不够。
循环本身并不重要，重要的是你的程序根据输入大小运行的指令总数，你可以把"指令"读作"在恒定时间内运行的函数"（与输入大小无关）。
确保所有函数调用都在O（1）中
让我们先看看所有函数调用的复杂性：
map.getOrDefault(cLeft, 0)map.put(cRight, ...)map.put(cLeft, ...)map.remove(cLeft)，也是在O（1）中+1，-1，都是O（1）。好了，现在我们可以有把握地说所有外部函数都是"指令"（或者更准确地说，所有这些函数都使用"固定大小的指令数"）。注意所有哈希Map复杂度并不完全准确，但这是a detail you can look at separately
这意味着我们现在只需要调用这些函数中的多少个。
分析函数调用的数量
注解中的论点是准确的，但使用
char cLeft = str.charAt(l)将崩溃的程序，如果l > N在我看来不是很令人满意，但这是一个有效的观点，它的内部循环不可能被执行超过l次的总和（这直接导致预期的O(N)的时间复杂度）.如果这是一个练习，我怀疑这是否是预期的答案，让我们分析这个程序，就像它是用
char cLeft = str.charAt(l % str.length())编写的一样，这样会更有趣一些。我觉得主参数应该基于存储在
map（字符到计数器对的Map）中的"字符计数总数"。1.* * outter循环总是将单个计数器增加1。
1.* * 内部循环总是将单个计数器减少1。
还有：
1.内部循环确保所有计数器为正（当计数器等于0时移除计数器）。
1.只要（正）计数器的数量为
> k，内部循环就会运行。C次，并且内循环至少被执行C + 1次，这意味着存在外循环的迭代r，其中内循环被执行r + 1次。在外循环的该迭代r期间，在某个时刻（通过1.和2.）map中所有字符计数器的总和将等于0。根据事实3.，这意味着没有剩余的计数器（map.size()等于0）.由于k > 0，在r迭代期间，不可能进入内循环r + 1次，因为4 ..证明引理为真的矛盾.不太正式的说法是，如果计数器之和为0，则内部循环将永远不会执行，因为
k（> 0）个正计数器的总和大于0。换句话说，消费者（内部循环）消费的东西不能超过（外部循环）产生的东西。因为这个引理，并且因为外循环正好执行N次，所以内循环最多执行
N次。总的来说，我们将在外循环中最多执行A * N次函数调用，在内循环中最多执行B * N次函数调用，A和B都是常数，并且所有函数都在O(1)中。因此(A + B) * N ∈ O(N)。还要注意，写
O(N + N)是一种重复语句（或没有意义），因为大O应该忽略所有常数因子（乘法和加法）。通常人们不会用大O符号写方程，因为很难写出正确和正式的东西（除了像O(log N) ∈ O(N)这样明显的集合包含）。通常你会说这样的话"所有的操作都在O(N)中，因此算法在O(N)中"。