Что в действительности означает сложность Log N?

Question

Я знаю, что такое лог n сложность, что обычно влечет за собой на практике (бинарный поиск, поиск человека в телефонной книге и разбиение его на мелкие и меньшие, вместо того, чтобы проходить от А до Я, разделяй и властвуй), но я все еще не точно с математической / вычислительной точки зрения что и почему говорят, что определенный процесс имеет временную сложность log n.

Answer 1

Один яркий пример сложности log(n) - это обход корневого дерева от root до одного из его листьев (как, например, бинарный поиск, как вы упомянули). Если у вас есть n объектов, из которых вы хотите создать сбалансированное корневое дерево, высота этого дерева будет log(n). Поскольку бинарное сбалансированное дерево имеет максимум 2^h узлов (h - это высота дерева), и если вы решите n = 2^h, вы обнаружите, что высота дерева, h, должна быть log(n) .

В целом, в большинстве обычных алгоритмов происхождение сложности log(n) происходит из обхода сбалансированного корневого дерева (или вообще корневого дерева) от его root до одного из его лист в подходе сверху вниз.

Answer 2

Я предлагаю вам прочитать большие обозначения O на других веб-сайтах, которые хорошо это объясняют, вместо того, чтобы спрашивать о StackOverflow.

Отказ от ответственности - это очень упрощенное объяснение, для общего объяснения вы должны посмотреть на большое O определение.

Что касается того, почему бинарный поиск O(log n). Это сводится к количеству операций, которые вы выполняете. Для массивов длин необходимо выполнить:

len: 0, ops: 1
len: 1, ops: 1
len: 2, ops: 2
len: 3, ops: 2
len: 4, ops: 3
len: 5, ops: 3
len: 6, ops: 3
len: 7, ops: 3
len: 8, ops: 4
...
len: 16, ops: 5
...

В каждой итерации вы можете выполнять 1 операцию и повторите двоичный поиск по массиву с длиной, равной половине размера. Вот откуда взялся логарифм. Для массива длиной 2^n требуется максимум log_2 n операций.