Предмет: Информатика
Автор: gdima2395
Вопрос задан 9 лет назад

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

Я так понимаю надо составить неравенство или что?

Ответы

Ответ дал: Аноним

Вычислительная сложность алгоритма сортировки вставками в среднем оценивается как $O_1=O(N^2)$ , а сортировки слиянием - в среднем оценивается как $O_2=Ntimes logN$
Нужно определить, при каком N первая оценка превысит вторую.
$N^2>N*logN; N>logN to N>0$
Получается, что в среднем сортировка слиянием всегда будет лучше сортировки вставками.

Похожие вопросы

Русский язык

2 года назад

Прилагательное-омоним: таким бывает слово или число.

Русский язык

2 года назад

Сочинение-описание на тему:Дождь.Только в разные время суток:Утро,День,Вечер.(Или можно на другую тему например Радуга)Только что бы было в разное время и описание.Плиззз!!!

Геометрия

7 лет назад

Две стороны треугольника равны по 7 см. Третья сторона имеет целое число сантиметров. Какой наибольший периметр в сантиметрах может иметь этот треугольник?

Алгебра

7 лет назад