# механизм оценки

механизм оценки скорости роста интересующей исследователя величины: ее сравнивают с какой-нибудь функцией, чье поведение хорошо исследовано. При этом используется обозначение g(n)=O(f(n)), - читается: О-большое, - которое мы будем относить к интересующим нас дискретным функциям f(n) натурального n и ко всем функциям g(n), растущим не быстрее f(n). Формулировка &quot;растущим не быстрее&quot; означает, что существует такая пара положительных значений M и n0, что ?g(n)? ? M?f(n0)? для n?n0. Еще говорят, что функция g(n) - &quot;порядка f(n) для больших n&quot;. Такая O-нотация дает нам верхнюю оценку временнОй трудоемкости алгоритма - его асимптотическую сложность. Обратите внимание, что использование констант M и n0, фигурирующих в определении, фактически связано с &quot;большими&quot; значениями аргумента n, и мало что дает при его малых значениях. Укажем несколько важных свойств O-операций: * f(n)=O(f(n)) * c?O(f(n))=O(f(n)), где c - некоторая константа * O(f(n))+O(f(n))=O(f(n))

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа