Как определить, является ли нотация Big-O фрагмента кода логарифмическим временем O (logn)? - PullRequest
Новая
       58

Как определить, является ли нотация Big-O фрагмента кода логарифмическим временем O (logn)?

0 голосов
/ 11 февраля 2019

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

- Пример был бы великолепен.

Ответы [ 3 ]

0 голосов
/ 11 февраля 2019

Временная сложность алгоритма равна O(log(n)), когда он «разрезает» входные данные пополам на каждой итерации.
Классическим примером, конечно же, является бинарный поиск.на каждом шаге вы делите «размер задачи» пополам, что означает, что после одной итерации размер будет n / 2, после 2 шагов n / 2 ^ 2 и так после i шагов - n / 2 ^ i.Алгоритм завершится, когда размер будет 1, так что i, которое удовлетворяет условию n / 2 ^ i = 1, является временем выполнения.
Решая это уравнение, мы получим n = 2 ^ i => i = log(n), таким образом даваянам сложность времени O(i) = O(log(n)).

Редактировать:

Чтобы быть более точным, я отмечаю, что нет необходимости сокращать ровно половину, так как время выполнения должно быть только O(log(n)), но не log(n) операций точно (и поэтому также допускается O(1) временных затрат на каждую итерацию).
Кроме того, мой пример демонстрирует только случай log_2, но алгоритм может (например) "сократить "входные данные до 1/3 от исходного размера, что дает нам n / 3 ^ i.
Итак, почему бы нам не указать основание журнала?
Мы обычно ссылаемся на log2 в этом контексте,но здесь это даже не имеет значения, поскольку O(log_i(n)) = O(log_j(n)) как log_i(n) = log_j(n) * log_i(j) и log_i(j) - это константа.

0 голосов
/ 11 февраля 2019

Как правило, вы найдете код со временем logN в алгоритмах типа «разделяй и властвуй».Это означает, что мы разбиваем проблему на более мелкие части и затем решаем для результата.

Например, что-то вроде двоичного поиска: 

mid = (hi + lo) / 2
if element == arr[mid]: element found, return
if element > arr[mid]: search(mid, hi)
else: search(lo, mid)

Этот код делит ваше пространство поиска на меньшие именьшие подзадачи.Каждый раз, когда вы сокращаете пространство поиска пополам, и вы можете делить целое число только пополам logN раз.

Нечто похожее наблюдается в алгоритмах типа mergesort, которые рекурсивно делят массив на две половины для сортировки.Слияние по существу: 

a = mergesort(arr[:len(arr)/2]) #left side
b = mergesort(arr[len(arr)/2:]) #right side
merge(a, b)

Это создает дерево подзадач, например, так: 

         4
        / \
       2   2    #mergesort left and right
      / \ / \
      1 1 1 1   #cannot break problem down further
      \ / \ /
       2   2    #merge
        \ /
         4      #merge

Каждое слияние происходит в O(N), а высота дерева подзадачи строится с помощью слиянияLogN (каждый следующий уровень делится на два, вы можете делить только на два logN раз).Это дает O(N) за время слияния LogN слияния для сложности времени O(NlogN).

Другим примером может быть что-то вроде операции кучи, такой как percolate_up или percolate_down.Если у вас есть структуры данных, такие как двоичные деревья, где у каждого узла есть два дочерних элемента, высота дерева равна logN.

0 голосов
/ 11 февраля 2019

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

Пример:

  1. Бинарный поиск в отсортированном массиве: здесь вы разбиваете входной массив на два и продолжаете поиск только в части.Сложность O (Log 2 (n)).

  2. Поиск m-way дерева: Здесь у вашего узла есть m-path.Вы можете выбрать один из этих m путей и продолжить поиск по дереву.Сложность O (Log m (n)).

...