- Сколько сравнений потребует алгоритм сортировки при упорядочении списка из N величин по возрастанию?
- Сколько арифметических операций нужно для умножения двух матриц размером N x N?
Следующие два алгоритма имеют одинаковый уровень сложности, в каждом делается три сравнения. По временным затратам эти алгоритмы одинаковы, но первый требует больше памяти из-за временной переменной. Размещение временной переменной может потребовать много места.
function getLargest(a, b, c, d) { largest = a; if (b > largest) // 1 сравнение largest = b; if (c > largest) // 2 сравнение largest = c; if (d > largest) // 3 сравнение largest = d; return largest; }
function getLargest(a, b, c, d) { if (a > b) // 1 сравнение if (a > c) // 2 сравнение if (a > d) // 3 сравнение return a; else return d; else if (c > d) // 3 сравнение return c; else return d; else if (b > c) // 2 сравнение if (b > d) // 3 сравнение return b; else return d; else if (c > d) // 3 сравнение return c; else return d; }
При анализе эффективности алгоритмов в первую очередь интересен вопрос времени - время выполнения. Но память тоже может играть существенную роль - объём памяти.
Сравнение эффективности двух разных алгоритмов допустимо только если они решают одну задачу. Нельзя сравнивать между собой алгоритм умножения матриц и алгоритм сортировки.
Условия влияющие на скорость программы, реализующей алгоритм:
- тип компьютера;
- процессор и тактовая частота;
- полный или редуцированный набор команд на чипе процессора;
- насколько хорошо компилятор оптимизирует выполняемый код.
Разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим. Нет нужды точно считать количество выполненных операций как функцию от размера входных данных N.
Алгоритм для решения задачи подсчета числа вхождений различных символов в файл:
for all 256 символов do
обнулить счетчик
end for
while в файле еще остались символы do
ввести очередной символ
увеличить счетчик вхождений прочитанного символа на единицу
end while
Всего операций:
- 256 проходов в цикле инициализации;
- 257 присваиваний в цикле инициализации (одно для инициализации переменной цикла и 256 для счетчика);
- 256 приращений переменной цикла в цикле инициализации;
- 257 проверок переменной цикла в цикле инициализации для того, что эта переменная находится в границах цикла (одна дополнительная для остановки цикла);
- если во входном файле N символов, то во втором цикле N проходов;
- во втором цикле нужно сделать N + 1 раз проверку условия (+1 для последней проверки, когда файл пуст) и N приращений счетчика.
- приращения: 256 + N;
- присваивания: 257;
- проверка условий: 257 + N + 1.
При увеличении N число операций инициализации не изменяется, но в процентном соотношении их становится значительно меньше. Вес инициализации по отношению ко времени выполнения алгоритма незначителен. При увеличении объема входных данных стоимость инициализации становится пренебрежимо малой.
