Что не так с этим индуктивным доказательством того, что mergesort равен O (n)?

Question

Сортировка на основе сравнения - большая омега nlog (n) , поэтому мы знаем, что сортировка слиянием не может быть O (n) .Тем не менее, я не могу найти проблему со следующим доказательством:

Предложение P (n) : для списка длины n, сортировка слиянием занимает O (n) время.

P (0) :сортировка слиянием в пустом списке просто возвращает пустой список.

Сильная индукция: предположим, P (1), ..., P (n-1) ипопробуйте доказать P (n) .Мы знаем, что на каждом шаге рекурсивной сортировки слиянием два примерно «полусписка» объединяются, а затем «архивируются».Объединение каждой половины списка занимает по индукции O (n / 2) времени .Застегивание занимает O (n) времени.Таким образом, алгоритм имеет рекуррентное соотношение M (n) = 2M (n / 2) + O (n) , что составляет 2O (n / 2)+ O (n) , что составляет O (n) .

Answer 1

Сравните «доказательство» того, что линейный поиск равен O (1).

1. Линейный поиск по пустому массиву - O (1).
2. Линейный поиск по непустому массивусравнивает первый элемент (O (1)) и затем ищет остальную часть массива (O (1)).O (1) + O (1) = O (1).

Проблема здесь в том, что для того, чтобы индукция работала, должна быть одна константа big-O, которая работает как для гипотезыи заключение.Это невозможно здесь и невозможно для вашего доказательства.

Answer 2

«Доказательство» охватывает только один проход, оно не распространяется на log n количество проходов.

Повторение показывает только стоимость пропуска по сравнению со стоимостью предыдущего пропуска.Чтобы быть точным, рекуррентное отношение должно иметь совокупную стоимость, а не дополнительные затраты.

Вы можете увидеть, где доказательство падает, просмотрев пример сортировки слиянием в http://en.wikipedia.org/wiki/Merge_sort

Answer 3

Вот суть: все шаги индукции, которые относятся к определенным значениям из n, должны относиться к конкретной функции T (n), а не к записи O ()!

Обозначение

O (M (n)) - это утверждение о поведении всей функции от размера задачи до гарантии производительности (асимптотически, когда n увеличивается без ограничения). Цель вашей индукции состоит в том, чтобы определить предел производительности T (n), который затем можно упростить (уменьшив постоянные и коэффициенты более низкого порядка) до O (M (n)).

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

Вы все еще можете использовать нотацию O (), чтобы упростить доказательство, продемонстрировав:

T(n) = F(n) + O(something less significant than F(n))

и распространение этого предиката обычным индуктивным способом. Но вам нужно сохранить постоянный коэффициент F (): этот постоянный фактор имеет прямое отношение к решению вашей рецидива «разделяй и властвуй»!