|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 03 Jan 2002 22:52:02
To : All
Subject : O() o()
--------------------------------------------------------------------------------
Всем спасибо. После попpавки (выделена)
=== Cut ===
====================================================================
> 1. Ликбез для понимания важной информации: Что означает символ O(n) ?
> Почему _не пишется_ основание логарифма: O ( log n ) ?
====================================================================
Оценки времени исполнения. 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( f(n) ) по Кнуту:
>N Величина Xn , представленная в виде O( f(n) ), удовлетворяет условию
>N | Xn | <= M |f(n)|
>N для некоторой константы M>0 и всех n, начиная с некоторого номера No.
>N
>N Запись O( f(n) ) обозначает множество всех функций от натуральных
>N чисел, для которых существуют константы M и No, такие, что
>N | g(n) | <= M |f(n)| для всех n >= No.
я === Cut ===
Здесь был я. [Team Гитара][Team MUD][Team Chinese][Team NLP]
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
