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

Question

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

vage205 · Answer

Вычислительная сложность алгоритма сортировки вставками в среднем оценивается как O_1=O(N^2)

, а сортировки слиянием - в среднем оценивается как $O_2=N\times logN$
Нужно определить, при каком N первая оценка превысит вторую.
$N^2N*logN; \ NlogN \to N0$
Получается, что в среднем сортировка слиянием всегда будет лучше сортировки вставками.

Популярные вопросы