Как рассчитать среднюю сложность алгоритма, который находит наибольшее и второе по величине число? - PullRequest
Новая
       23

Как рассчитать среднюю сложность алгоритма, который находит наибольшее и второе по величине число?

0 голосов
/ 07 апреля 2020

Я все еще пытаюсь понять, как вычислить сложность моих алгоритмов в среднем случае - возможно, из-за того, что мне не хватает некоторых основ вероятности.

У меня есть алгоритм, который должен найти наибольшее и второе самый большой номер. Пример, записанный в 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 - для назначения (i = 0);
  • 1(n - 1) - Общее количество проверок первого условия if в течение для l oop.

Поскольку мы игнорируем константы, мы можем сказать, что в лучшем случае это O (n) (линейная сложность).

Наихудший сценарий

В то же время, я полагаю, что наихудшим сценарием будет список в порядке возрастания ( например, [1, 2, 3, 4, 5]), поскольку нам пришлось бы вводить первое условие N-1 раз.

С учетом каждой инструкции стоимость будет 2 + 1 + 3(n - 1), то есть:

  • 2 - The первые два назначения (biggest и biggest2);
  • 1 - для назначения (i = 0);
  • 3(n - 1) - с учетом проверки if и два назначения внутри него.

Поскольку мы игнорируем константы, мы можем сказать, что наихудший сценарий - O (n) (линейная сложность).

Пожалуйста, не стесняйтесь поправлять меня, если оба рассуждения выше неверны. Я также изо всех сил пытаюсь понять сценарий для лучших и худших случаев ios в некоторых случаях.

Однако я не знаю, как приступить к вычислению среднего случая. Я даже не представляю, что будет входом для сценария среднего случая. Я знаю, что для этого может потребоваться некоторая теория вероятностей, но я не знаю, как вообще начать ее рассматривать.

  1. Какой вклад можно считать действительным для сценария среднего случая?
  2. Как рассчитать среднюю сложность по времени?

1 Ответ

0 голосов
/ 07 апреля 2020

Средний случай здесь не требует расчета; это также линейное время, O (n), потому что среднее значение всегда должно быть между лучшим и наихудшим случаями.

Если бы среднее значение было лучше, чем O (n), то оно было бы лучше, чем в лучшем случае. и если бы среднее было хуже, чем O (n), то это было бы хуже, чем в худшем случае. Оба будут противоречиями.

...