#algorithm #sorting #time-complexity
#алгоритм #сортировка #сложность по времени
Вопрос:
Пусть A и B — два алгоритма, которые решают одну и ту же проблему. Утверждение: если A быстрее, чем B, как в наихудшем, так и в среднем случае, то, обязательно, A быстрее, чем B, и в лучшем случае.
Ответ №1:
Нет. Рассмотрим сортировку слиянием и сортировку вставкой. Сортировка слиянием всегда O(n log n) выполняется в лучшем, среднем и наихудшем случаях. Сортировка по вставке выполняется O(n^2) в среднем и худшем случаях; однако это O(n) в лучшем случае.