Предположим, на одной и той же машине проводится сравнительный - вопрос №2992233 от serega5152 28.03.2020 10:49

Question

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

serega5152 · Answer

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

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