Решение вопроса о том, что считать, состоит из двух шагов:
- выбирается значимая операция или группа операций;
- выбирается какие из этих операций содержатся в теле алгоритма, а какие составляют накладные расходы или уходят на регистрацию и учёт данных.
Значимые операции:
- Сравнение. Все операторы сравнения (C/C++) считаются эквивалентными, и их учитывают в алгоритмах поиска и сортировки.
- a == b
- a != b
- a < b
- a > b
- a <= b
- a >= b
- Арифметические операции (C/C++)
- Аддитивные операции (сложения)
- a + b
- a - b
- a++ (увеличение счетчика)
- a-- (уменьшение счетчика)
- Мультипликативные операции (умножения). Умножения работают дольше чем сложения. Алгоритмы считаются предпочтительнее других, если в них меньше умножений, даже если число сложений при этом пропорционально возрастает.
- a * b
- a / b
- a % b (взятие остатка по модулю)
- Целочисленное умножение или деление на степень двойки образуют специальный случай. Эта операция сводится к сдвигу, а последний по скорости эквивалентен сложению. Однако случаев, где эта разница существенна, совсем немного, поскольку умножение и деление на 2 встречается в первую очередь в алгоритмах типа "разделяй и властвуй", где значимую роль зачастую играют операторы сравнения.
- Логарифмы и тригонометрические функции, образуют еще одну, даже более времяёмкую, чем умножения, группу операций (обычно компьютеры вычисляют их значения с помощью разложения в ряд).
См. также:
