Как мы можем доказать, что время выполнения алгоритма является жестким?

Question

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

Я хочу доказать, что это временное ограничение работает. Два вопроса:

1. Не достаточно ли ввести специальный ввод и показать, что время работы составляет не менее f(n)?
2. Я читал, что одна возможность доказать герметичность - «уменьшить сортировку». Я понятия не имею, что подразумевается под этой

Answer 1

Не было бы достаточно, чтобы дать специальный вход и показать, что работает время, по крайней мере е (п)?

Да, предполагается, что вы говорите о худшем случае сложности.
Если вы говорите о сложности наихудшего случая - и вы доказали, что он работает в O(f(n)), если вы найдете вход, который «хуже», чем C*f(n)) для некоторой константы C - вы эффективно доказали, что алгоритм (в худшем случае - производительность) в Ω(f(n)), и с O(f(n)) [intersection] Ω(f(n)) = Theta(f(n)), это означает, что ваш алгоритм работает в Theta(f(n)) в худшем случае анализа.
Примечание, что он должен быть на самом деле «семья» примеров, так как если я требую «да, но это верно только для малых n значений, а не для n>N (для некоторых N), вы можете показать мне, что это семейство примеров охватывает также случай, когда n>N, и по-прежнему в силе.

Симметрично, если вы доказали алгоритм имеет лучшую производительность случае Ω(f(n)), и вы нашли некоторый вклад, который работает «лучше» (быстрее), чем C*f(n)) для некоторых константа C, вы эффективно доказали, что алгоритм Theta(f(n)) при наилучшем анализе случаев.

Этот трюк НЕ работает для анализа среднего случая - где вы должны рассчитать ожидаемое время выполнения, а особый пример не поможет.

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

Это сделано, чтобы доказать более сильное утверждение, что нет алгоритма (вообще), который может решить некоторые проблемы в нужное время.
Общее использование этого заключается в том, чтобы предположить, что существует алгоритм черного квадрата A, который запускается в некотором o(g(n)) времени, а затем используется A для построения алгоритма сортировки, который работает в o(nlogn) времени. Однако, поскольку сортировка является проблемой Ω(nlogn), у нас есть противоречие, и мы можем заключить, что предположения о A ошибочны и не могут работать в нужное время.

Это помогает нам доказать более сильное требование: не только алгоритм OUR имеет эту нижнюю границу, но алгоритмы ALL, которые решают конкретную проблему, имеют эту нижнюю границу.

Answer 2

ad 1 .: Да, но вы должны иметь возможность находить такой ввод размера n для любого n. Пример размера 3, который обрабатывается в 9 шагов, на самом деле ничего не доказывает.

ad 2 .: Если вы можете изменить последовательность элементов, чтобы ваш алгоритм эффективно сортировал ее (вы получаете отсортированную последовательность после некоторой обработки вывода), вы уменьшили ее сортировку. И поскольку сортировка (по сравнению) не может быть быстрее O (n log (n)), это может быть использовано для доказательства того, что ваш алгоритм не может быть быстрее O (n log (n)).

Конечно, функции обработки ввода и вывода не могут быть медленнее или равны O (n log (n)), чтобы этот аргумент был действительным, иначе вы могли бы отсортировать массив и доказать, что алгоритм O (1) что просто возвращает входной массив, на самом деле, по крайней мере, O (n log (n)) :).