Что 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

Что такое журнал _b (n)?

Это количество раз, которое вы можете несколько раз разрезать бревно длиной n на b равных частей, прежде чем достигнете участка размером 1.

Answer 2

Сначала я рекомендую вам прочитать следующую книгу;

Алгоритмы (4-е издание)

Вот некоторые функции и их ожидаемые сложности. Числа указывают частоты выполнения операторов .

После Диаграмма сложности Big-O также взята из bigocheatsheet

Наконец, очень простая витрина показывает, как она рассчитывается;

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

Анализ времени выполнения программы (пример).

Answer 3

Алгоритмы «разделяй и властвуй» обычно имеют logn компонент времени работы. Это происходит из-за многократного деления входа на два.

В случае бинарного поиска, каждую итерацию вы отбрасываете половину ввода. Следует отметить, что в нотации Big-O log - это база журнала 2.

Редактировать: Как уже отмечалось, база журналов не имеет значения, но при вычислении производительности алгоритма Big-O логарифм будет получаться в два раза, поэтому я и считаю его базой 2.

Answer 4

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

Я бы перефразировал это так: «высота полного двоичного дерева равна log n». Вычисление высоты полного двоичного дерева было бы O (log n), если вы переходите вниз шаг за шагом.

Я не могу понять, как определить функцию с логарифмической время.

Логарифм по сути является обратным возведению в степень. Итак, если каждый «шаг» вашей функции исключает фактор элементов из исходного набора элементов, то это алгоритм логарифмического времени.

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

Answer 5

Эти 2 случая займут O (log n) время

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

Answer 6

O (log n) немного вводит в заблуждение, точнее, O (log ₂ n), т. Е. (Логарифм с основанием 2).

Высота сбалансированного бинарного дерева равна O (log ₂ n), поскольку каждый узел имеет два (обратите внимание на «два», как в log ₂ n) дочерних узлов. Итак, дерево с n узлами имеет высоту log ₂ n.

Другим примером является бинарный поиск, который имеет время выполнения O (log ₂ n), потому что на каждом шаге вы делите пространство поиска на 2.

Answer 7

O(log n) относится к функции (или алгоритму, или шагу в алгоритме), работающей в течение времени, пропорционального логарифму (обычно основание 2 в большинстве случаев, но не всегда, и в любом случае это незначительно по big-O обозначение *) размера ввода.

Логарифмическая функция является инверсией экспоненциальной функции. Иными словами, если ваш вклад растет экспоненциально (а не линейно, как вы обычно это считаете), ваша функция растет линейно.

O(log n) время выполнения очень распространено в любом приложении типа «разделяй и властвуй», потому что вы (в идеале) сокращаете работу пополам каждый раз. Если на каждом из этапов деления или завоевания вы выполняете работу с постоянным временем (или работу, которая не является постоянной, но со временем, растущим медленнее, чем O(log n)), тогда вся ваша функция равна O(log n). Довольно часто каждый шаг требует линейного времени на входе; это составит общую сложность времени O(n log n).

Сложность времени выполнения бинарного поиска является примером O(log n). Это связано с тем, что в бинарном поиске вы всегда игнорируете половину своего ввода на каждом последующем шаге, разделяя массив пополам и фокусируясь только на одной половине с каждым шагом. Каждый шаг является постоянным временем, потому что в бинарном поиске вам нужно сравнить только один элемент с вашим ключом, чтобы выяснить, что делать дальше, независимо от того, насколько большой массив вы рассматриваете в любой момент. Таким образом, вы делаете примерно log (n) / log (2) шагов.

Сложность времени выполнения сортировки слиянием является примером O(n log n). Это связано с тем, что вы делите массив пополам с каждым шагом, в результате чего получается примерно log (n) / log (2) шагов. Однако на каждом шаге необходимо выполнять операции слияния для всех элементов (будь то одна операция слияния на двух подсписках из n / 2 элементов или две операции слияния на четырех подсписках из n / 4 элементов) не имеет значения, поскольку она добавляет к необходимости сделать это для п элементов в каждом шаге). Таким образом, общая сложность составляет O(n log n).

* Помните, что обозначение big-O, по определению , константы не имеют значения. Также с помощью изменения базового правила для логарифмов единственное различие между логарифмами разных оснований - постоянный коэффициент.

Answer 8

Это просто означает, что время, необходимое для этой задачи, увеличивается с log (n) (пример: 2s для n = 10, 4s для n = 100, ...). Прочитайте статьи Википедии о Алгоритме двоичного поиска и Обозначение Big O для большей точности.

Answer 9

Проще говоря: на каждом шаге вашего алгоритма вы можете сократить работу пополам. (Асимптотически эквивалентно третьему, четвертому, ...)

Answer 10

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

Именно поэтому алгоритмы с логарифмической сложностью по времени так востребованы: даже для действительно больших n (скажем, n = 10 ^ 8) они работают более чем приемлемо.