Разное.

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

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

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

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

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

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

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

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

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

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

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