Оценки времени исполнения. Cимвол O(). Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения через символ O(n) (читается так: о большое от n). n здесь - обычно количество обрабатываемых элементов данных (например, сортируемых чисел). Также такую оценку называют 'асимптотикой', так как она обозначает асимптотическое поведение алгоритма ( n -> беск. ) Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n^2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций. n log n n*log n n^2 1 0 0 1 16 4 64 256 256 8 2,048 65,536 4,096 12 49,152 16,777,216 65,536 16 1,048,565 4,294,967,296 1,048,476 20 20,969,520 1,099,301,922,576 16,775,616 24 402,614,784 281,421,292,179,456 Если считать, что числа в таблице соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму с временем работы O(log n) потребуется 20 микросекунд, а алгоритму с временем работы O(n^2) - более 12 дней. Если оба алгоритма, например, O ( n*log n ), то это отнюдь не значит, что они одинаково эффективны. Символ О не учитывает константу, то есть первый может быть, скажем в 1000 раз эффективнее. Это значит лишь то, что время (или требуемая память или что-либо еще, что надо оценить) возрастает приблизительно c такой же скоростью, как функция n*log n. За функцию берется количество операций, возрастающее быстрее всего. То есть если в программе одна функция выполняется O(n) раз - например, умножение, а сложение - O(n^2) раз, то общая сложность - O(n^2), так как n^2 возрастает быстрее. Практический смысл этого в нашем случае такой: при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут влиять на производительность много сильнее, нежели медленные, но редкие умножения. Основание логарифма не пишется. Причина этого весьма проста. Пусть у нас есть O( log2 n ). Перейдем к основанию 3: log2n = log3n / log32. Hо 1/log3 2, как и любую константу, асимптотика - символ O() не учитывает. Таким образом, O(log2n) = O(log3n). К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла. В заключение, привожу формальную трактовку обозначения O(g(n)) для положительных функций f(n), g(n): Опp.1 O(g(n)) - множество функций f(n), для котоpых существуют положительные константы c, n0, такие что f(n) <= c*g(n) для всех n>=n0 Опp.2 Запись f(n) = O(g(n)) означает, что f(n) - элемент множества O(g(n)) Иногда символ O() используют в более широком смысле, подразумевая не только верхнюю, но и нижнюю оценку Theta(): существуют c1, c2, n0 > 0: 0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0 Кроме символа O() используются также оценки Omega(g(n)) - нижняя оценка: множество f(n): существуют c, n0>0: c*g(n) <= f(n) Theta(g(n)) - комбинация O() и Omega(): точная оценка асимптотики. Theta(g(n) - множество f(n): существуют c1, c2, n0>0: 0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0 Все описанные свойства оценки O() также верны для Omega() и Theta(). Интуитивный смысл оценок: f = O(g) - f растет не быстрее g } f = Omega(g) - f растет не медленнее g } при n->00 f = Theta(g) - f растет так же, как g }  8  Комментарии к статье  8 8  Обсудить в чате