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

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

Answer 2

Но что именно O (log n)

Это означает, что «когда n стремится к infinity, time стремится к a*log(n), где a - постоянный коэффициент масштабирования».

Или на самом деле, это не совсем так; более вероятно, что это означает что-то вроде «time, деленное на a*log(n), стремится к 1».

«Стремится к» имеет обычный математический смысл из «анализа»: например, что «если вы выберете любую произвольно небольшую ненулевую константу k, тогда я могу найти соответствующее значение X так, что ((time/(a*log(n))) - 1) меньше k для всех значений n больше X. "

---

Проще говоря, это означает, что уравнение для времени может иметь некоторые другие компоненты: например, может иметь некоторое постоянное время запуска; но эти другие компоненты бледнеют к незначительности для больших значений n, и a * log (n) является доминирующим термином для больших n.

Обратите внимание, что если бы уравнение было, например ...

время (n) = a + b log (n) + c n + d n n

... тогда это будет O (n в квадрате), потому что, независимо от значений констант a, b, c и ненулевого d, термин d*n*n всегда будет доминировать над остальными для любого достаточно большое значение n.

Это означает, что обозначение бита O означает: «каков порядок доминирующего члена для любого достаточно большого n».

Answer 3

Я могу привести пример для цикла for и, возможно, однажды поняв концепцию, возможно, будет проще понять ее в других контекстах.

Это означает, что в цикле шаг растет в геометрической прогрессии. Например.

for (i=1; i<=n; i=i*2) {;}

Сложность в O-нотации этой программы O (log (n)). Давайте попробуем перебрать его вручную (n между 512 и 1023 (исключая 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Хотя n где-то между 512 и 1023, имеет место только 10 итераций. Это связано с тем, что шаг в цикле растет в геометрической прогрессии и, таким образом, для достижения завершения требуется всего 10 итераций.

Логарифм x (к основанию a) является обратной функцией от ^ x.

Это все равно, что сказать, что логарифм - это обратная экспонента.

Теперь попытайтесь увидеть это таким образом: если экспонента растет очень быстро, тогда логарифм растет (обратно) очень медленно.

Разница между O (n) и O (log (n)) огромна, аналогична разнице между O (n) и O (a ^ n) (a является константой).

Answer 4

В информационных технологиях это означает, что:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Похоже, что эти обозначения в основном взяты из математики.

В этой статье есть цитата: D.E. Кнут, "БОЛЬШОЕ ОМИКРОН И БОЛЬШАЯ ОМЕГА И БОЛЬШАЯ ТЕТА", 1976 :

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

Сегодня 2016, но мы используем его до сих пор.

---

В математическом анализе это означает, что:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Но даже в математическом анализе иногда этот символ использовался в значении "C * g (n)> f (n)> 0".

Как я знаю из университета, этот символ был введен немецким математиком Ландау (1877-1938)

Answer 5

log x to base b = y является обратной величиной b^y = x

Если у вас M-арное дерево глубины d и размера n, то:

• обход всего дерева ~ O (M ^ d) = O (n)

• Пройдя по одному пути в дереве ~ O (d) = O (войти n в базу M)

Answer 6

Каждый раз, когда мы пишем алгоритм или код, мы пытаемся проанализировать его асимптотическую сложность. Он отличается от сложности времени .

Асимптотическая сложность - это поведение времени выполнения алгоритма, тогда как временная сложность - это фактическое время выполнения. Но некоторые люди используют эти термины взаимозаменяемо.

Поскольку сложность времени зависит от различных параметров, а именно.
1. Физическая система
2. Язык программирования
3. Стиль кодирования
4. И многое другое ......

Фактическое время выполнения не является хорошей мерой для анализа.

Вместо этого мы принимаем входной размер в качестве параметра, потому что, какой бы ни был код, входные данные одинаковы. Таким образом, время выполнения является функцией размера ввода.

Ниже приведен пример алгоритма линейного времени

Линейный поиск
Учитывая n входных элементов, для поиска элемента в массиве вам нужно не более 'n' сравнений . Другими словами, независимо от того, какой язык программирования вы используете, какой стиль кодирования вы предпочитаете, в какой системе вы его выполняете. В худшем случае требуется только n сравнений. Время выполнения линейно пропорционально размеру ввода.

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

Так что, когда вы говорите, что любой алгоритм - это O это означает, что время выполнения - это лог, умноженное на размер ввода n

По мере увеличения размера ввода увеличивается количество выполненных работ (здесь время выполнения) (отсюда и пропорциональность)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Смотрите, как увеличивается размер входного сигнала, увеличивается объем работы, и он не зависит от какой-либо машины. И если вы попытаетесь выяснить стоимость единиц работы Это на самом деле зависит от указанных выше параметров. Он будет меняться в зависимости от систем и всего.

Answer 7

На самом деле, если у вас есть список из n элементов и вы создаете двоичное дерево из этого списка (как в алгоритме «разделяй и властвуй»), вы будете делить на 2, пока не достигнете списков размера 1 (листья).

На первом шаге вы делите на 2. Затем у вас есть 2 списка (2 ^ 1), вы делите каждый на 2, поэтому у вас есть 4 списка (2 ^ 2), вы делите снова, у вас есть 8 списков ( 2 ^ 3) и так до тех пор, пока размер вашего списка не станет 1

Это дает вам уравнение:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(берете lg с каждой стороны, lg - основание журнала 2)

Answer 8

Если вы ищете ответ, основанный на интуиции, я бы хотел предложить вам две интерпретации.

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

2. Представьте себе алгоритм, который принимает целое число n в качестве входных данных и завершает его во времени, пропорциональном n, тогда это O (n) или theta (n), но если он работает во времени, пропорциональном number of digits or the number of bits in the binary representation on number тогда алгоритм выполняется за O (log n) или тета (log n) время.

Answer 9

Полный бинарный пример - O (ln n), потому что поиск выглядит так:

1 2 3 4 5 6 7 8 9 10 11 12

Поиск 4 дает 3 попадания: 6, 3, а затем 4. И log2 12 = 3, что является хорошим приблизительным значением для количества попаданий, где это необходимо.

Answer 10

Алгоритмы в парадигме «разделяй и властвуй» имеют сложность O (logn). Один из примеров: вычислите свою собственную степенную функцию,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

из http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/