|
====================================================================
> 1. Ликбез для понимания важной информации:
> Что означает символ O(n) ? Оценки Omega() и Theta()
> Почему _не пишется_ основание логарифма: O(logn) ?
====================================================================
Оценки времени исполнения. 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( log n ). Перейдем к основанию 3: log n = log n / log 2.
2 2 3 3
Hо 1/log 2, как и любую константу, асимптотика - символ O()
3
не учитывает. Таким образом, O(log n) = O(log n).
2 3
К любому основанию мы можем перейти аналогично, а, значит, и писать
его не имеет смысла.
В заключение, привожу формальную трактовку обозначения 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 }
|
