Вы когда-нибудь пытались разработать алгоритм для решения проблемы на входе произвольной длины n, и приходили к нему всего за O (n ) время работы?
Иногда это просто, например: «Найти минимум в следующем списке из n целых чисел».
Неудобная правда
В большинстве случаев вы на самом деле получаете не истинное O (n), а скорее O (n log n).
Подумайте об этом: если вы не можете просто «посмотреть на предмет и сразу же выбросить его», вы обречены. Вам нужен произвольный доступ к данным n или, по крайней мере, возможность обращаться к каждому элементу в отдельности. Чтобы ссылаться на элементы n, вам потребуются индексы или указатели размера (log n). QED.
Ну и что?
Вышеупомянутое понимание ничего не меняет в реальной производительности ваших любимых строк кода. Однако он проливает свет на два аспекта логарифмических факторов.
- Полезное эмпирическое правило: (log n) растет настолько медленно, что вы можете рассматривать его как постоянный коэффициент и стереть его из теоретического уравнения. На реальных компьютерах мы используем 32-битные или 64-битные указатели. Иногда вам может понадобиться проиндексировать до 2⁶⁴ элементов, хранящихся где-то на Земле. Если вы работаете в компании, занимающейся большими данными, вы можете проиндексировать более 2⁶⁴ физических объектов. Но вы никогда не захотите индексировать реальные объекты размером до 2²⁵⁶, несмотря ни на что. Считайте 256 как константу верхней границы.
- Анализ Big-O является фундаментальным, но не раскрывает всей картины. Он игнорирует все постоянные факторы, точнее все факторы, имеющие верхнюю границу, не зависящую от размера входных данных. Как будто числа Джеффа Дина имеют одинаковую ценность! В реальной жизни эти скрытые факторы имеют большое значение. Учтите их. Фактор (log n) является лишь одним из них в том смысле, что значение его скрытого множителя имеет гораздо большее значение, чем страх перед (log n) очень высоко растет. Не будет.
