Но оценка алгоритмической
Но оценка алгоритмической трудоемкости это не учитывает.
Пример #2.
Найти сумму натуральных чисел от 1 до заданного n.
Если воспользоваться известной формулой для суммы арифметической прогрессии, то вычисления также потребуют лишь 3 шага: сложение, умножение и деление. Если же реализовать вычислительный процесс как циклический: цикл с параметром, управляющая переменная "пробежит" значения от 1 до n, - то придется выполнить n шагов алгоритма. Сомнений, какой из алгоритмов более эффективен, кажется, не возникает. Однако вспомните о "худших случаях": при небольших значениях n (скажем, от 2 до 4), "медленный" алгоритм, вероятно, предпочтительнее.
Для алгоритмов, подобных только что рассмотренному, - n шагов для обработки n входных значений, - очевидно, что количество шагов является функцией от числа обрабатываемых элементов. Можно считать, что количество шагов является функцией от количества элементов - f(n).
В математике существует специальный
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
