如何计算找到最大和第二大数字的算法的平均情况复杂度？

Question

我仍在努力理解如何计算我的算法的平均情况复杂度 - 可能是因为我缺乏一些概率基础知识。

我有一个算法可以找到最大和第二大的数字。用 JavaScript:

编写的示例

/**
 * @param nums - array of numbers
 * @param n - array length
 */
function findBiggest(nums, n) {
  let biggest = nums[0], biggest2 = nums[1];

  for (let i = 1; i < n; i++) {
    /* Whenever biggest is changed, biggest2 is also 
     * automatically updated.
     */
    if (nums[i] > biggest) {
      biggest2 = biggest;
      biggest = nums[i];
    }

    else if (nums[i] > biggest2 && nums[i] < biggest)
      biggest2 = nums[i];
  }

  return [biggest, biggest2];
}

/**
 * Input: [5, 2, 4, 3, 1]
 * Output: [5, 4]
 */

最佳情况

我认为最好的情况是按降序排列的列表（例如 [5, 4, 3, 2, 1]），因为我们不会必须跳入任何条件。

因此，考虑到每条指令，成本将为 2 + 1 + 1(n - 1)，即：

2 - 前两个赋值（biggest 和 biggest2）；
1 - for 赋值 (i = 0);
1(n - 1) - 在 for 循环中检查第一个 if 条件的总次数。

由于我们忽略常量，我们可以说最好的情况是 O(n)（线性复杂度）。

最坏情况

同时，我认为最坏的情况是列表按升序排列（例如 [1, 2, 3, 4, 5]），因为我们会必须进入第一个条件N-1次。

考虑到每条指令，成本将是 2 + 1 + 3(n - 1)，即：

2 - 前两个赋值（biggest 和 biggest2）；
1 - for 赋值 (i = 0);
3(n - 1) - 考虑 if 检查和其中的两个赋值。

由于我们忽略常量，我们可以说最坏的情况是 O(n)（线性复杂度）。

如果以上两种推理都不正确，请随时纠正我。在某些情况下，我也很难理解最好情况和最坏情况。

但是，我不知道如何继续计算平均情况。我什至无法想象平均情况下的输入是什么。我知道这可能需要一些概率论，但我什至不知道如何开始考虑它。

什么输入可以被认为对平均情况有效？
如何计算平均情况下的时间复杂度？

Answer 1

平均情况这里不用计算；它也是线性时间 O(n)，因为平均情况必须始终介于最好和最坏情况之间。

如果平均值比 O(n) 好，那么它会比最好的情况好，如果平均值比 O(n) 差，那么它会比最坏的情况更糟。两者都是矛盾的。

如何计算找到最大和第二大数字的算法的平均情况复杂度？

How to calculate the average-case complexity of an algorithm that finds the biggest and second-biggest number?

algorithm

complexity-theory

time-complexity