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