Алгоритмическая интуиция для логарифмической сложности

Я считаю, что у меня есть разумное представление о сложностях, таких как , Θ ( n ) и Θ ( n 2$\mathcal{O}(1)$$\Theta(n)$$\Theta(n^2)$ .

С точки зрения списка, - это постоянный поиск, поэтому он просто получает заголовок списка. Θ ( n ) - это место, где я прошёл бы весь список, а Θ ( n 2 ) - список по одному разу для каждого элемента в списке.$\mathcal{O}(1)$$\Theta(n)$$\Theta(n^2)$

Есть подобный интуитивный способ понять , кроме просто зная , что лежит где - то между O ( 1 ) и & thetas ( п ) ?$\Theta(\log n)$$\mathcal{O}(1)$$\Theta(n)$

сложность, как правило , связаны с подразделением. При использовании списков в качестве примера представьте список, элементы которого отсортированы. Вы можете искать в этом списке в O ( log n $\Theta(\log n)$$\mathcal{O}(\log n)$ - вам не нужно просматривать каждый элемент из-за отсортированной природы списка.

Если вы посмотрите на элемент в середине списка и сравните его с элементом, который вы ищете, вы можете сразу сказать, находится ли он в левой или правой половине массива. Затем вы можете просто взять эту половину и повторять процедуру, пока не найдете ее или не достигнете списка с 1 элементом, который вы тривиально сравниваете.

Вы можете видеть, что список фактически делит пополам каждый шаг. Это означает, что если вы получите список длиной , то максимальное количество шагов, которое вам нужно для достижения списка из одного элемента, равно 5 . Если у вас список 128 = 2 7 элементов, вам нужно всего 7 шагов, для списка 1024 = 2 10 вам нужно всего 10 шагов и т. Д.$32$$5$$128 = 2^7$$7$$1024 = 2^{10}$$10$

Как вы можете видеть, показатель степени в 2 n всегда показывает количество необходимых шагов. Логарифм используется для «извлечения» именно этого числа экспоненты, например, log 2 2 10 = 10 . Он также обобщает список длин, которые не являются степенями двух длин.$n$$2^n$$\log_2 2^{10} = 10$

В терминах (сбалансированных) деревьев (скажем, двоичного дерева, так что все - это база 2):$\log$

• получает корень дерева$\Theta(1)$
• - это путь от корня к листу$\Theta(\log n)$
• пересекает все узлы дерева$\Theta(n)$
• - действия на всех подмножествах двух узлов в дереве, например, количество различных путей между любыми двумя узлами.$\Theta(n^2)$
• - обобщение приведенного выше для любого подмножества k узлов (для константы k )$\Theta(n^k)$$k$$k$
• - действия над всеми возможными подмножествами узлов (подмножествами всех возможных размеров, т. Е. K = 1 , 2 , … , n .). Например, количество различныхподдеревьевдерева.$\Theta(2^n)$$k=1,2, \ldots, n$

Чтобы было возможно, вам нужно уметь пропорционально сократить размер задачи на некоторую произвольную величину по отношению к n с помощью операции с постоянным временем.$O(\log n)$$n$

Например, в случае бинарного поиска вы можете сократить размер задачи вдвое при каждой операции сравнения.

Теперь вы должны сократить размер проблемы вдвое, на самом деле нет. Алгоритм - это даже если он может сократить пространство поиска проблемы на 0,0001%, при условии, что процент и операция, используемая для сокращения размера проблемы, остаются постоянными, это O ( log $O(\log n)$алгоритм ) , это не будет быстрый алгоритм, но он все равно O ( log n ) с очень большой константой. (Предполагается, что мы говорим о log n с журналом base 2)$O(\log n)$$O(\log n)$$\log n$

Подумайте об алгоритме преобразования десятичного числа в двоичное$n$

while n != 0:
   print n%2, 
   n = n/2

Этот whileцикл запускает раз.$\log(n)$

Да, находится между 1 и n , но ближе к 1, чем n . Что такое log ( n ) ? Лог-функция является обратной функцией экспоненты. Позвольте мне начать с экспоненты, и вы должны лучше понять, что такое логарифм.$\log(n)$$1$$n$$1$$n$$\log(n)$

Рассмотрим два числа, и 2 100 . 2 100 - это 2, умноженные на себя в 100 раз. Вы можете с некоторым усилием сосчитать 100 чисел, но можете ли вы сосчитать 2 100 ? Бьюсь об заклад, вы не можете. Почему? 2 100 такое большое число, что оно больше, чем число всех атомов во вселенной. Задумайтесь об этом на мгновение. Это настолько большое число, что оно позволяет дать каждому атому имя (число). А количество атомов в ногтях у вас, вероятно, порядка миллиардов. 2 $100$$2^{100}$$2^{100}$$2$$100$$100$$2^{100}$$2^{100}$$2^{100}$ должно быть достаточно для всех (каламбур предназначен).

Теперь между двумя числами, и 2 100 , 100 - логарифм 2 100 (в базе 2 ). 100 сравнительно такое небольшое число, чем 2 100 . У кого угодно должно быть 100 разных предметов в своем доме. Но 2 100 достаточно хорошо для вселенной. Думай домой против вселенной, думая о журнале ( n $100$$2^{100}$$100$$2^{100}$$2$$100$$2^{100}$$100$$2^{100}$$\log(n)$ и $n$ .

Откуда взялись экспонента и логарифмы? Почему они так интересуются информатикой? Вы можете не заметить, но экспонента повсюду. Вы платили проценты по кредитной карте? Вы только что заплатили вселенную за свой дом (не так уж плохо, но кривая подходит). Мне нравится думать, что экспонента исходит из правила продукта, но другие могут привести больше примеров. Вы можете спросить, какое правило продукта? И я отвечу.

Скажем, у вас есть два города и B , и между ними есть два пути. Какое количество путей между ними? Два. Это тривиально. Теперь, скажем, есть другой город C , и вы можете перейти от B к C тремя способами. Сколько сейчас путей между А и С ? Шесть, верно? Как ты это получил? Вы их посчитали? Или ты их умножил? В любом случае, легко увидеть, что оба способа дают одинаковый результат. Теперь, если вы добавите город D, до которого можно добраться из C четырьмя способами, сколько будет путей между A ? Посчитайте, если вы мне не доверяете, но оно равно 2 $A$$B$$C$$B$$C$$A$$C$$D$$C$$A$ и $D$ есть 24 . Теперь, если есть десять городов и есть два пути из одного города в другой, и они расположены так, как будто они находятся на прямой линии. Сколько путей существует от начала до конца? Умножьте их, если вы мне не доверяете, но я скажу вам, что есть 2 10 , то есть 1024 . Смотрите, что 2 10 - это экспоненциальный результат 10 , а 10 - логарифм 2 10 . 10 - небольшое число по сравнению с 1024 .$2\cdot 3\cdot 4$$24$$2^{10}$$1024$$2^{10}$$10$$10$$2^{10}$$10$$1024$

Функция логарифма равна n, что n равно 2 n (обратите внимание, что 2 - это основание логарифма). Если вы умножаете log b ( n ) на себя b раз (обратите внимание, что b - это основание логарифма), вы получите n . log ( n ) настолько мал, настолько мал по сравнению с n , что это размер вашего дома, где n - это размер вселенной.$\log_2(n)$$n$$n$$2^n$$2$$\log_b(n)$$b$$b$$n$$\log(n)$$n$$n$

На практике заметим, что функции очень похожи на функции констант. Они растут с п , но они растут очень медленно. Если вы оптимизировали программу для выполнения в логарифмическом времени, которое занимало день раньше, вы, вероятно, запустите ее в течение нескольких минут. Проверьте сами проблемы с Project Euler.$\log(n)$$n$

Чтобы продолжить вашу тему, равно что гадать где $O(\log n)$$x$ лежит в списке, и ему говорят «выше» или «ниже» (в терминах индекса).

Он по-прежнему зависит от размера списка, но вам нужно посетить только часть элементов.

Если у нас есть алгоритм «разделяй и властвуй» , и мы делаем только один рекурсивный вызов для подзадачи, и это второй случай в теореме Мастера , т. Е. Временная сложность нерекурсивной части равна , то сложность алгоритма составит Θ ( lg k + 1 n $\Theta(\lg^k n)$$\Theta(\lg^{k+1} n)$ .

Другими словами, когда у нас есть алгоритм «разделяй и властвуй» с одним рекурсивным вызовом к себе для задачи с размером, постоянным множителем текущей задачи, и время в нерекурсивной части равно (постоянная), тогда время работы алгоритма будет lg $\Theta(1)$$\lg n$ .

Бинарный поиск алгоритм является классическим примером.

Интуиция заключается в том, сколько раз вы можете вдвое уменьшить число, скажем, n, прежде чем оно уменьшится до 1 - O (lg n).

Для визуализации попробуйте нарисовать его в виде бинарного дерева и подсчитать количество уровней, решив эту геометрическую прогрессию.

2^0+2^1+...+2^h = n