Что O (log n) означает точно?

Question

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

Например, следующая функция: O (n) , поскольку алгоритм растет пропорционально его вводу n :

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Аналогично, если бы был вложенный цикл, время было бы равно O (n ² ).

Но что именно это O (log n) ? Например, что значит сказать, что высота полного двоичного дерева равна O (log n) ?

Я знаю (возможно, не очень подробно), что такое логарифм, в том смысле, что: log ₁₀ 100 = 2, но я не могу понять, как определить функцию с логарифмическим временем.

Answer 1

O (logn) - это одна из полиномиальных временных сложностей для измерения производительности во время выполнения любого кода.

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

Предположим, вам нужно найти элемент в массиве размера N.

В основном, выполнение кода похоже на N N / 2 N / 4 N / 8 .... и т.д.

Если вы сложите всю работу, проделанную на каждом уровне, вы получите n (1 + 1/2 + 1/4 ....), что равно O (logn)

Answer 2

Я хотел бы добавить, что высота дерева - это длина самого длинного пути от корня до листа, и что высота узла - это длина самого длинного пути от этого узла до листа. Путь означает количество узлов, с которыми мы сталкиваемся при прохождении дерева между двумя узлами. Чтобы достичь O (log n) временной сложности, дерево должно быть сбалансировано, а это означает, что разница высоты между дочерними элементами любого узла должна быть меньше или равна 1. Поэтому деревья не всегда гарантируют временную сложность O (log n), если они не сбалансированы. На самом деле в некоторых случаях временная сложность поиска в дереве может быть O (n) в худшем случае.

Вы можете взглянуть на деревья баланса, такие как AVL tree. Этот работает для балансировки дерева при вставке данных, чтобы сохранить сложность времени (log n) при поиске в дереве.