Алгоритмы c сложность против реальных ситуаций?

Question

Мой вопрос касается теории и практики.
Скажем, например, что я хочу отсортировать список чисел. Сорт Mergesort имеет сложность O (n * logn), в то время как сортировка пузырьков имеет сложность O (n ^ 2). Это означает, что слияние происходит быстрее. Но сложность не учитывает всего происходящего на компьютере. Под этим я подразумеваю то, что сортировка слиянием, например, является алгоритмом «разделяй и властвуй», и ему нужно больше места, чем пузырьковой сортировке. Так разве не возможно, что создание этого дополнительного пространства и использование ресурсов (время для передачи данных, заполнения инструкций кода и т. Д. c) займет больше времени, чем пузырьковая сортировка, которая не использует никакого дополнительного пространства? Разве нельзя было бы более эффективно использовать алгоритм с меньшей («большей») сложностью, чем другой, для определенной длины входных данных (возможно, небольших)?

Answer 1

Ответ ясен: да.

Классицистический c пример - сортировка вставки O(n^2). Однако реализации эффективной сортировки часто переключаются на сортировку вставкой с примерно 100 оставшимися элементами, потому что сортировка вставкой действительно эффективно использует кэш и избегает остановок конвейера в ЦП. Нет, сортировка вставок не будет масштабироваться, но она превосходит.

Я бы сказал, что масштабируемость похожа на Mack Truck. Вы хотите его для большой нагрузки, но это может быть не лучшим вариантом для похода по магазинам в местном продуктовом магазине.

Answer 2

Algorithmi c Сложность говорит только о том, как два алгоритма будут сравниваться при увеличении их входных данных, т.е. Это ничего не говорит вам о том, как они будут сравниваться на меньших входах. Единственный способ узнать это наверняка - это сравнить данные и оборудование, которое представляет типичную ситуацию.