#algorithm #sorting #time #complexity-theory
#алгоритм #сортировка #время #теория сложности
Вопрос:
Я читаю учебник по алгоритмам. В учебнике говорится, что операция сравнения является доминирующей стоимостью в любой разумной реализации. Почему это так? Что делает его таким медленным?
Комментарии:
1. Вы имеете в виду в контексте сортировки?
2. Я прочитал это предложение в контексте быстрой сортировки, но я полагаю, что автор подразумевает, что оно более общее, чем это.
3. Я бы сказал, что на большинстве машин обмен массивами обходится дороже, чем сравнение. Дело в том, что сравнение используется гораздо чаще по сравнению с другими операциями. Другая операция, используемая столько же раз, сколько и сравнение, — это приращение, которое является менее дорогостоящим.
4. Дело не столько в том, что операция сравнения является доминирующей стоимостью — сравнения часто относятся к числу более быстрых инструкций, — но в том, что сравнения часто оказывают управляющее влияние на циклы, определяя, сколько раз выполняются другие операции. Таким образом, вы часто подсчитываете вычислительную сложность путем подсчета сравнений.
5. @twalberg Ваше объяснение имеет смысл. Однако в учебнике явно используется слово «стоимость». Я попрошу своего профессора подробнее обсудить это.
Ответ №1:
Я думаю, вы привыкли к примерам из учебников, таким как сортировка массивов целых чисел или около того, где сравнения дешевы. Что ж, добро пожаловать в реальный мир, здесь все немного сложнее. Во многих случаях операция сравнения — это больше, чем просто одно « if «, обычно это довольно сложная функция обратного вызова. Он начинается с вычисления фактического ключа для сравнения как функции объекта. Простым примером может быть сравнение строк независимо от регистра. Здесь вам сначала нужно нормализовать регистр каждой строки. Затем вам нужно сравнить строки посимвольно. Это большая работа, гораздо больше работы, чем, скажем, замена двух char* . Или подумайте о сравнении деревьев: в рамках одной операции сравнения вам, возможно, придется следовать многим ветвям обоих деревьев.
И даже если у вас есть структура данных, где само сравнение очень простое, за ним всегда следует условный переход. Условные переходы дороги, они занимают около 15 ..25 тактов в современных процессорах, предполагая, что аппаратное обеспечение не может легко предсказать результат. Это очень долгое время, обычно процессор может выполнить одну операцию за один такт.