re:re:actable
Урок 052 минуты чтения

Что такое best average и worst case?

На этой странице
Кратко

Best, average и worst case описывают поведение алгоритма при разных входных данных. На собеседовании чаще всего называют worst case, но полезно понимать, когда best или average объясняют реальное поведение лучше.

Вопрос

Что такое best, average и worst case и какой случай указывать на собеседовании?

Best case

Лучший случай - когда алгоритм завершился максимально быстро.

function linearSearch(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i
  }
 
  return -1
}

Если target в первом элементе:

O(1)

Worst case

Худший случай - самый тяжелый допустимый input.

Для linearSearch:

  • элемента нет;
  • элемент в конце.

Сложность:

O(n)

Average case

Средний случай описывает ожидаемое поведение при некотором распределении input.

Для поиска по массиву, если элемент равновероятно может быть где угодно, в среднем проверим примерно половину массива:

O(n)

Константа меньше, но рост все равно линейный.

Почему чаще говорят worst case?

Worst case важен, потому что:

  • дает гарантию;
  • проще сравнивать решения;
  • показывает риск на плохих данных;
  • полезен для production и security.

Но иногда average case тоже важен. Например, quicksort в среднем O(n log n), но в худшем случае может стать O(n^2).

Что отвечать на собеседовании?

Best case - лучший вход, average case - ожидаемое поведение на типичных данных, worst case - самый плохой допустимый вход. На собеседовании обычно называют worst-case complexity, потому что она дает гарантию, но можно дополнительно упомянуть average case, если он важен для алгоритма.

Что важно помнить: частые ошибки

  • Называть best case вместо worst case.
  • Говорить "в среднем быстро" без модели данных.
  • Забывать worst case quicksort.
  • Не понимать, что O(n / 2) все равно O(n).
  • Считать ранний return гарантией O(1).

Мини-шпаргалка

  • Best case - повезло.
  • Worst case - не повезло.
  • Average case - ожидаемо при модели input.
  • На интервью чаще говорят worst case.
  • Ранний выход улучшает best, но не worst.
  • Average требует предположений.

Документация

Wikipedia: Best, worst and average case.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам