Время выполнения: границы против дела

Question

Примечание: Пожалуйста, не отмечайте это как домашнее задание! Я не студент, и это не задание. Я - инженер-программист, стряхивающий свой старый учебник по структурам данных и алгоритмам, и пытаюсь вспомнить то, что я выучил много лет назад и чего я нигде не могу найти в Интернете.

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

Для меня, если какой-либо алгоритм имеет O (n) наихудший случай, то он может выполнять любую хуже, чем некоторая линейная функция, такая как f(n) = cn + k. Поскольку нам гарантировано это в худшем случае, мне кажется, что его верхняя граница также линейна.

Я знаю, что ошибаюсь, просто не могу понять, почему.

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

Спасибо за ясность!

Answer 1

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

В лучшем случае равен O (n)если массив уже отсортирован.Это верхняя граница для поведения в лучшем случае, которая имеет смысл, если не интересна.

* Средний случай по случайным входам равен O (n ^3/2 ) и Ω (n).Хорошо, я немного обманул, потому что это также Theta (n log n), но идея в том, что границы не всегда тесны, и это отсутствие тесноты может проявиться, когда я описываю границы среднего случая.

худший случай - это тэта (n ² ), если массив отсортирован в обратном порядке, потому что подзадачи не сбалансированы (каждый раз мы поворачиваемся с максимальным элементом, что приводит к подзадачам размеров0 и n - 1 вместо примерно n / 2 и примерно n / 2).Это жесткий предел для худшего случая и показывает, что алгоритм действительно может быть настолько плохим, но не хуже.Быстрая сортировка также O (n ³ ), но не Theta (n ³ ), потому что быстрая сортировка не имеет семейства входных данных, которое приводит к кубическому поведению.

Answer 2

Случай относится к исследуемому типу времени выполнения, тогда как bound относится к функции для этого времени выполнения.

То, что алгоритм имеетВремя выполнения в наихудшем случае O (f (n)) эквивалентно тому, что f (n) представляет собой асимптотическую верхнюю границу для времени выполнения алгоритма в худшем случае.

3 случая (лучший случай, средний случай и наихудший случай) и 5 ​​асимптотических границ (верхняя (O), жесткая верхняя (o), нижняя (Ω), жесткая нижняя (ω) и плотная (Θ))дать 15 различных способов сделать заявление о времени выполнения.

Может возникнуть путаница или бедствие, если граница указана без учета кейса.Например, нижняя граница алгоритма сортировки может быть как Θ (n), так и Θ (n lg n), в зависимости от того, говорим ли мы о лучшем или худшем случае.Среднее время работы в Θ (1) не годится, если время работы в худшем случае Θ (n ³ ) останавливает заводскую работу.

Answer 3

Говоря о случае означает, что вы рассматриваете производительность алгоритма для какого-то определенного ввода. Наихудший случай означает «для того, что мы собираемся обсудить, рассмотрите возможность прохождения всего через все возможные входы и сделайте утверждение для применения к самому медленному запуску» и т. Д.

Ограничениеэто неравенство, утверждение, что что-то меньше или больше, чем что-то еще.Граница сложности говорит о том, что какой бы ни была ее функция сложности, она больше или меньше указанной.Big-O, little-o, Omega, все записи, указывающие на границы.Если что-то есть O (n), это означает, что прогоны описанного алгоритма по входу, удовлетворяющему параметру n, никогда не будут хуже, чем некоторая линейная функция, асимптотически (или, что еще более мучительно, что существуют некоторые N и c,st для всех n> N, cn превосходит время работы алгоритма).

Это не так уж и плохо: O, o, Omega, просто расскажу вам об оценках проблемы.Затем вы можете говорить о границах для лучшего или худшего случая и так далее.Например, большинство алгоритмов сортировки будут в лучшем случае O (n).Вы можете установить границы для наихудшего случая, которые также являются границами для всех случаев.Тета - это специальное обозначение: Тета (f) означает O (f) и Омега (f), что означает, что граница жесткая и не может быть улучшена.Это точное утверждение.

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

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

Answer 4

Рассмотрим функцию, которая принимает список из N + 1 целых чисел.Предположим, что если первый элемент равен 0, функция вызывает функцию Th (log n) или Th (n) для обработки данных, и определение происходит равномерно наугад.Аналогично, если первый элемент равен 1, вызовите Th (n ^ 2) для обработки данных.Для всех других значений первого элемента, вызовите функцию Th (n ^ 1.5) или Th (n log n).Мы можем сказать следующее о сложности этой функции:

1. Наилучший регистр: Omega (log n), Omicron (n)
2. Средний регистр *: Omega (n log n), Omicron(n ^ 1.5)

3. Наихудший случай: Омега / Омикрон / Тета (n ^ 2)

   • Предполагая, что число возможных значений для первого элемента достаточно велико.

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

Answer 5

Описание: Выше экстракт из здесь .

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

for my $i (0 .. $#array) {
    for my $j (0 .. $#array) {
        next if $j == $i;
        # Compare $i, $j
    }
}

Это O (N ^ 2). После небольшого тестирования мы решили, что это слишком медленно, поэтому проведем небольшую оптимизацию.

for my $i (0 .. $#array - 1) {
    for my $j ($i + 1 .. $#array) {
        # Compare $i, $j
    }
}

Мы только что сократили наше время выполнения пополам - ДА! Угадайте, что Big-O остался прежним O (N ^ 2). Это потому, что N ^ 2/2 имеет только одну переменную часть.

Эта часть была от здесь .

Answer 6

Наивный алгоритм для суммы, например, находится в O (n), O (n ^ 2), O (n ^ 3) и всех более высоких классах, когда O обозначает верхнюю границу наихудшего случая. Это также в Theta (n), но не в Theta (n ^ 2) или Theta (n ^ 0), когда Theta является строгой границей. Это Омега (n), Омега (n ^ 0) и все низшие классы, когда Омега является нижней границей.

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