Поиск по сайту.

Другие алгоритмы.

Разное.

Оценки времени исполнения. Cимвол O().

     Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n).

     Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.

n
log n
n*log n
n2
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( n2 ) - более 12 дней.

Если оба алгоритма, например, O ( n*log n ), то это отнюдь не значит, что они одинаково эффективны.

Символ О не учитывает константу, то есть первый может быть, скажем в 1000 раз эффективнее. O() значит лишь то, что их время возрастает приблизительно как функция n*log n.

За функцию берется количество операций, возрастающее быстрее всего.

То есть, если в программе одна функция выполняется O(n) раз - например, умножение, а сложение - O(n2) раз, то общая сложность программы - O(n2), так как в конце концов при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут влиять на быстродействие куда больше, нежели медленные, но редкие умножения. O() показывает исключительно асимптотику !

Основание логарифма не пишется.

Причина этого весьма проста. Пусть у нас есть O( log2n). Но log2n=log3n/log32, а log32, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O( log2n) = O( log3n).
     К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла.




Вверх по странице, к оглавлению и навигации.