求含N、M双参数的指定算法的最优与最差运行时间

别慌！我来帮你一步步拆解这段代码，搞清楚它的最优和最差运行时间～

首先，我们先把代码里的核心执行步骤拆出来分析：

• 第一步：调用std::sort(a, a+N)对数组a排序，题目已经明确说明这一步的时间复杂度是O(N log N)，这部分的时间是固定的，不管最优还是最差情况都不会变化。
• 第二步：遍历hash数组的for循环，这部分的时间取决于数组a的最大值（也就是排序后的a[N-1]，我们记它为max_a）。

最差运行时间分析 #

当max_a等于M-1的时候（也就是数组a的最大值刚好是hash数组的最后一个索引），循环会完整执行M次：因为i的范围是0到M-1，每次执行完hash[i] = 1后，判断i > max_a（也就是i > M-1）永远不成立，所以不会触发break，循环会一直走到i = M才终止。这时候循环的时间复杂度是O(M)。

把排序和循环的时间加起来，最差运行时间就是：
O(N log N + M)

最优运行时间分析 #

注意题目里提到数组a的元素是**distinct（互不相同）**的，所以N个不同的数中，最小的可能最大值是N-1（比如取0,1,2,...,N-1这N个连续的数）。这时候循环的执行次数会非常少：

• 当i从0到N-1时，每次判断i > max_a（也就是i > N-1）都不成立，会继续循环；
• 当i = N时，执行完hash[N] = 1后，判断N > N-1成立，直接触发break终止循环。

这时候循环一共执行了N+1次，时间复杂度是O(N)。

因为排序的时间O(N log N)比O(N)的量级更大（当N足够大时，N log N增长得比N快得多），所以最终最优运行时间由排序步骤主导，也就是：
O(N log N)

补充一点：如果M远小于N log N，那最差情况的实际运行时间主要由排序决定，但我们还是要写成O(N log N + M)，因为当M远大于N log N时，M会成为主导项。

内容的提问来源于stack exchange，提问作者shinichi