Наихудший, средний и лучший анализ алгоритмов

В предыдущем посте мы обсуждали, как асимптотический анализ преодолевает проблемы наивного способа анализа алгоритмов. Но давайте рассмотрим асимптотическую нотацию и узнаем, что такое наихудший, средний и лучший случаи алгоритма:

Популярные обозначения в анализе сложности алгоритмов

1. Обозначение большого O

Мы определяем временную сложность алгоритма в наихудшем случае , используя нотацию Big-O, которая определяет, что набор функций растет медленнее или с той же скоростью, что и выражение. Кроме того, это объясняет максимальное количество времени, которое требуется алгоритму для рассмотрения всех входных значений.

2. Обозначение омега

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

3. Обозначение тета

Он определяет средний случай временной сложности алгоритма, нотация Theta определяет, когда набор функций лежит как в O(выражение), так и в Omega(выражение) , тогда используется нотация Theta. Вот как мы определяем случай средней временной сложности для алгоритма.

Измерение сложности алгоритма

Основываясь на приведенных выше трех обозначениях временной сложности, можно проанализировать алгоритм в трех случаях:

1. Анализ наихудшего случая (чаще всего используется)

В анализе наихудшего случая мы вычисляем верхнюю границу времени работы алгоритма. Мы должны знать случай, при котором выполняется максимальное количество операций. Для линейного поиска наихудший случай возникает, когда искомый элемент (x) отсутствует в массиве. Когда x отсутствует, search() функция сравнивает его со всеми элементами arr[] один за другим. Следовательно, временная сложность линейного поиска в наихудшем случае будет O(n) .

2. Анализ наилучшего случая (используется очень редко)

В анализе наилучшего случая мы вычисляем нижнюю границу времени работы алгоритма. Мы должны знать случай, при котором должно быть выполнено минимальное количество операций. В задаче линейного поиска наилучший случай имеет место, когда x присутствует в первом месте. Количество операций в лучшем случае постоянно (не зависит от n). Таким образом, временная сложность в лучшем случае будет Ω(1)

3. Анализ среднего случая (используется редко)

При анализе среднего случая мы берем все возможные входные данные и рассчитываем время вычислений для всех входных данных. Суммируйте все рассчитанные значения и разделите сумму на общее количество входов. Мы должны знать (или предсказывать) распределение случаев. Для задачи линейного поиска предположим, что все случаи распределены равномерно (включая случай, когда x отсутствует в массиве). Таким образом, мы суммируем все случаи и делим сумму на (n+1). Ниже приведено значение временной сложности в среднем случае.

Average Case Time = sum_{i=1}^{n}frac{ heta (i)}{(n+1)} = frac{ heta (frac{(n+1)*(n+2)}{2})}{(n+1)} = heta (n)

Какой анализ сложности обычно используется?

Ниже приведено ранжированное упоминание нотации анализа сложности в зависимости от популярности:

1. Анализ наихудшего случая:

Большую часть времени мы проводим анализ наихудшего случая для анализа алгоритмов. В наихудшем анализе мы гарантируем верхнюю границу времени работы алгоритма, которая является достоверной информацией.

2. Анализ среднего случая

Анализ среднего случая в большинстве практических случаев провести непросто, и он проводится редко. В анализе среднего случая мы должны знать (или предсказывать) математическое распределение всех возможных входных данных.

3. Анализ наилучшего случая

Анализ наилучшего случая является фиктивным. Гарантия нижней границы алгоритма не дает никакой информации, так как в худшем случае на выполнение алгоритма могут уйти годы.

Интересная информация об асимптотических обозначениях:

A) For some algorithms, all the cases (worst, best, average) are asymptotically the same. i.e., there are no worst and best cases. 

• Example:  Merge Sort does Θ(n log(n)) operations in all cases.

B) Where as most of the other sorting algorithms have worst and best cases. 

• Example 1: In the typical implementation of Quick Sort(where pivot is chosen as a corner element), the worst occurs when the input array is already sorted and the best occurs when the pivot elements always divide the array into two halves.
• Example 2: For insertion sort, the worst case occurs when the array is reverse sorted and the best case occurs when the array is sorted in the same order as output.

Примеры с анализом их сложности:

1. Алгоритм линейного поиска:

Анализ временной сложности: (в нотации Big-O)

• Лучший случай: O(1), Это произойдет, если искомый элемент находится в первом индексе данного списка. Таким образом, количество сравнений в данном случае равно 1.
• Средний случай: O (n). Это произойдет, если искомый элемент находится в среднем индексе данного списка.
• Наихудший случай: O(n). Это произойдет, если:
  • Элемент для поиска находится в последнем индексе
  • Элемент для поиска отсутствует в списке

2. В этом примере мы возьмем массив длины (n) и рассмотрим следующие случаи:

• Если (n) четно, наш вывод будет 0
• Если (n) нечетно, то наш вывод будет суммой элементов массива.

Ниже приведена реализация данной задачи:

Анализ временной сложности:

• Лучший случай: порядок роста будет постоянным , потому что в лучшем случае мы предполагаем, что (n) четно.
• Средний случай: в этом случае мы будем Предположим, что четные и нечетные равновероятны, поэтому Порядок роста будет линейным
• Наихудший случай: порядок роста будет линейным , потому что в этом случае мы предполагаем, что (n) всегда нечетно.

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