Лучшее, худшее и среднее время выполнения

Question

Может ли кто-нибудь просто объяснить мне, что подразумевается под временем выполнения алгоритма в лучшем, худшем и среднем случаях ??? 1001 *

Answer 1

Проще говоря, для задачи, где размер ввода n :

• Лучший случай = самое быстрое время для завершения,с выбранными оптимальными входными данными.
  Например, лучшим вариантом для алгоритма сортировки будут уже отсортированные данные.

• Наихудший случай = самое медленное время для завершенияс выбранными пессимальными входами.
  Например, наихудшим случаем для алгоритма сортировки могут быть данные, отсортированные в обратном порядке (но это зависит от конкретного алгоритма).

• Средний регистр = среднее арифметическое.Запустите алгоритм много раз, используя множество различных входных данных размером n , которые поступают из некоторого распределения, которое генерирует эти входные данные (в простейшем случае все возможные входные значения одинаково вероятны), вычисляют общее время выполнения (подобавив отдельные времена), и разделите на количество испытаний.Вам также может потребоваться нормализовать результаты в зависимости от размера входных наборов.

Сложность и время выполнения часто выражаются в «Большой O нотации», которая используется для описания приблизительногоколичество времени, которое требуется алгоритму для завершения, исходя из размера его входных данных.Роб Белл написал превосходный обзор с очень наглядными примерами.

Наиболее часто используемые описания Big O:

• O (1) всегда завершается примерно в одно и то же время независимо от размера ввода.
• O (logN) * ​​1041 * занимает фиксированное дополнительное время каждый раз, когда размер ввода удваивается.
• O (N) занимает вдвое больше времени для завершения, если размер ввода удваивается.
• O (N ² ) занимает четыре разадо тех пор, пока размер ввода удваивается.
• O (2 ^N ) увеличивается экспоненциально с увеличением размера ввода.

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

Input Size              Time to Complete
               O(1)  O(logN)   O(N)   O(N<sup>2</sup>)   O(2<sup>N</sup>)
     1           1       1      1       1       1
     2           1       2      2       4       4
     4           1       3      4      16      16
     8           1       4      8      64     256
    16           1       5     16     254   65536

Answer 2

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

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

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

Answer 3

Думайте об алгоритме как о программе.Эта программа берет некоторые данные, некоторое время откатывает их, а затем выдает ответ.Конечно, мы заботимся о том, как долго программа обрабатывает данные, прежде чем дать ответ.

Но есть одна загвоздка: для многих алгоритмов время выполнения зависит от самих данных.Например, многие алгоритмы сортировки быстрее для уже отсортированных данных, а некоторые медленнее для данных, отсортированных в обратном порядке.

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

Answer 4

наихудший случай обычно обозначается асимптотическими обозначениями, т. Е. Большой (O)

лучший случай обозначается асимптотическим обозначением, т. Е. Большим (OMEGA)

Answer 5

Время работы алгоритма зависит от размера и «сложности» ввода.

Например, лучший случай время выполнения сортировки вставки на входе некоторого размера n пропорционально n , т.е. c * n единицы времени для некоторой постоянной c , которая зависит от стоимости (времени) сравнения, арифметики, ... вашей вычислительной модели. наихудший случай время выполнения этого алгоритма (сортировка вставки) пропорционально n * n .Чтобы сделать утверждение для среднего времени , нам нужно некоторое предположение о распределении входных данных: Например, если входные данные являются случайными данными (и, следовательно, вероятно, не отсортированы), среднее время выполнения снова пропорционально n *п.

Если вам известно больше о входных данных, например, о том, что они сортируются по убыванию значений (а мы сортируем по возрастанию значений), среднее время выполнения все равно пропорционально n * n, но постоянный коэффициент выше(потому что среднее время поиска минимума (которое будет вставлено в конец отсортированного подсписка) занимает больше времени).

Другой, более сложный пример - быстрая сортировка: его среднее и лучшее время выполнения для случайногоданные пропорциональны n * log n .Худшее время каста по-прежнему составляет n * n (часто для уже отсортированного ввода, но это зависит от алгоритма нахождения элемента поворота на шаге деления).

Answer 6

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