Как большие уравнения нотации O назначаются в алгоритмах поиска?
Для линейного поиска имеет смысл, чтобы время выполнения было большим O из N, поскольку это всегда будет один шаг. Что касается моего понимания пузырьковой сортировки, ее время выполнения составляет O из n ^ 2, это имеет смысл для меня, потому что вы будете перебирать количество элементов в массиве и каждый раз сравнивать два значения до конца указанного массива.
Но для сортировки слиянием данные всегда разбиваются пополам, поэтому я не понимаю, почему время выполнения равно n log n. Кроме того, я хочу прояснить свое понимание сортировки вставками во время выполнения большого O из n ^ 2. Поскольку сортировка вставками ищет наименьшее число, а затем сравнивает его с каждым отдельным числом массива, это будет n ^ 2, потому что он будет перебирать содержимое массива для каждой итерации.
Если бы мне дали несколько советов о сортировке слиянием и общем понимании времени выполнения, я был бы признателен. Я абсолютный новичок и хотел бросить этот отказ от ответственности.
Сортировка слиянием объединяет n элементов log n раз. Поскольку это вечный вопрос (это сложно!), здесь есть ответ на него: softwareengineering.stackexchange.com/questions/297160/…
Я согласен, но не лучший ответ, этот: softwareengineering.stackexchange.com/a/297203/3673
Я также согласен с @PresidentJamesK.Polk - именно так я делал это в старшей школе, чтобы прочувствовать это - я взял колоду игральных карт, перетасовал их, а затем сделал с ними все что угодно. Становится ясно, когда приходится делать это вручную, что принципиально быстрее.
Ответы 1
Предположим, что сортировка массива из N элементов занимает T(N) времени. В сортировке слиянием мы знаем, что нам нужно отсортировать два массива из N/2 элементов (то есть 2*T(N/2)), а затем объединить их (в O(N) временной сложности, то есть c*N для некоторой константы c). Итак, T(N) = 2T(N/2) + c*N. Мы могли бы остановиться здесь, так как это в основном «уравнение», о котором вы спрашиваете. Но пойдем немного дальше.
Чтобы упростить ситуацию, мы можем показать, что T(N) = kN log N следующим образом (для некоторой константы k):
Подставим T в обе части полученного уравнения:
KN log N = 2 * k*(N/2) log (N/2) + c*N
И разверните правую часть (при условии, что log с основанием 2): = k*N *(log N - log 2) + c*N = k*N *(log N - 1) + c*N = kNlog N + (c-k)N
То есть для c=k выполняется равенство, и оно доказывает, что T(N) если формы kN log N, то есть O(N log N)
Большое спасибо после просмотра диаграммы с математикой выше от Хогана, это щелкнуло!
Просто сделайте это вручную для нескольких примеров и посчитайте.