Как рассчитать порядок (большой O) для более сложных алгоритмов (например, quicksort)

Ответ 1

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

Для многих алгоритмов требуется логарифмическое число больших шагов, но для каждого большого шага требуется O (n) единиц работы. Mergesort попадает в эту категорию.

Обычно вы можете идентифицировать эти проблемы, визуализируя их как сбалансированное двоичное дерево. Например, здесь merge sort:

 6   2    0   4    1   3     7   5
  2 6      0 4      1 3       5 7
    0 2 4 6            1 3 5 7
         0 1 2 3 4 5 6 7

В верхней части находится вход, как листья дерева. Алгоритм создает новый node путем сортировки двух узлов над ним. Мы знаем, что высота сбалансированного двоичного дерева равна O (log n), поэтому существуют большие шаги O (log n). Однако создание каждой новой строки приводит к работе O (n). O (log n) большие шаги O (n) работают каждый означает, что mergesort O (n log n) в целом.

Как правило, алгоритмы O (log n) выглядят как функция ниже. Они могут отбросить половину данных на каждом шаге.

def function(data, n):
    if n <= constant:
       return do_simple_case(data, n)
    if some_condition():
       function(data[:n/2], n / 2) # Recurse on first half of data
    else:
       function(data[n/2:], n - n / 2) # Recurse on second half of data

В то время как алгоритмы O (n log n) выглядят как функция ниже. Они также разделяют данные пополам, но они должны учитывать обе половины.

def function(data, n):
    if n <= constant:
       return do_simple_case(data, n)
    part1 = function(data[n/2:], n / 2)      # Recurse on first half of data
    part2 = function(data[:n/2], n - n / 2)  # Recurse on second half of data
    return combine(part1, part2)

Где do_simple_case() принимает время O (1), а комбинация() занимает не более O (n) времени.

Алгоритмы не должны разделить данные ровно пополам. Они могли разбить его на треть и две трети, и все было бы хорошо. Для среднесрочных показателей достаточно разделить его пополам в среднем (например, QuickSort). Пока рекурсия выполняется на кусках (n/something) и (n - n/something), все в порядке. Если он разбивает его на (k) и (n-k), то высота дерева будет O (n), а не O (log n).

Ответ 2

Обычно вы можете требовать log n для алгоритмов, где каждый раз он пробегает пространство/время. Хорошим примером этого является любой двоичный алгоритм (например, двоичный поиск). Вы выбираете либо левый, либо правый, который затем осей пространства, которое вы ищете пополам. Шаблон повторного выполнения половины - log n.

Ответ 3

Для некоторых алгоритмов получение жесткой привязки к времени выполнения через интуицию почти невозможно (я не думаю, что когда-нибудь смогу использовать время O(n log log n), например, и я сомневаюсь, что кто-то будет когда-либо ожидал от вас). Если вы можете воспользоваться текстом CLRS Introduction to Algorithms, вы найдете довольно тщательную трактовку асимптотической нотации, которая является надлежащим образом строгой, не будучи полностью непрозрачный.

Если алгоритм является рекурсивным, один простой способ получить оценку состоит в том, чтобы выписать повторение и затем решить его решить, либо итеративно, либо используя Мастер-теорема или каким-то другим способом. Например, если вы не хотите быть строгим в этом отношении, самый простой способ получить время работы QuickSort - через Мастер-теорему. QuickSort влечет за собой разделение массива на два относительно равных подмассива. (Должно быть достаточно интуитивно понятно, что это O(n)), а затем вызывать QuickSort рекурсивно на этих двух подмассивах. Тогда, если обозначить T(n) время работы, мы имеем T(n) = 2T(n/2) + O(n), который по методу мастера O(n log n).

Ответ 4

Обратите внимание на приведенный здесь пример "телефонной книги": Что такое простое английское объяснение" Big O " обозначения?

Помните, что Big-O относится к шкале: насколько больше будет выполняться этот алгоритм по мере роста набора данных?

O (log n) означает, что вы можете сократить набор данных пополам с каждой итерацией (например, двоичный поиск)

O (n log n) означает, что вы выполняете операцию O (log n) для каждого элемента в вашем наборе данных

Я уверен, что 'O (n log log n)' не имеет никакого смысла. Или, если это так, оно упрощается до O (n log n).

Ответ 5

Я попытаюсь сделать интуитивный анализ того, почему Mergesort является n log n, и если вы можете дать мне пример алгоритма n log log n, я тоже смогу его проработать.

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

Вместо этого подумайте, как будет вести себя Mergesort, мы собираемся взять список и разбить его, а затем взять эти половинки и разбить его снова, пока у нас не будет n разделов длины 1. Надеюсь, что легко увидеть, что эта рекурсия будет идти только log (n) до тех пор, пока мы не разделим список на наши n разделов.

Теперь, когда у нас есть, что каждый из этих n разделов нужно будет объединить, то, как только они будут объединены, следующий уровень необходимо будет объединить, пока мы снова не увидим список длины n. Обратитесь к графику wikipedia для простого примера этого процесса http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg.

Теперь рассмотрим, сколько времени займет этот процесс, у нас будут уровни log (n), и на каждом уровне нам придется объединить все списки. Как оказалось, каждый уровень займет n раз, чтобы объединиться, потому что каждый раз мы будем объединять в общей сложности n элементов. Тогда вы можете довольно легко увидеть, что для сортировки массива с mergesort потребуется n log (n), если вы выполняете операцию сравнения как наиболее важную операцию.

Если что-то неясно или я что-то пропустил, дайте мне знать, и я могу попытаться быть более подробным.

Изменить второе Объяснение:

Позвольте мне подумать, могу ли я объяснить это лучше.

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

Когда вы разбиваете проблемы, у вас есть несколько разных уровней размера, сначала у вас будет два списка размера: n/2, n/2, тогда на следующем уровне у вас будет четыре списка размера: n/4, n/4, n/4, n/4 на следующем уровне вы будете иметь n/8, n/8, n/8, n/8, n/8, n/8, n/8, n/8 это продолжается до тех пор, пока n/2 ^ k не станет равным 1 (каждое подразделение представляет собой длину, деленную на мощность 2, а не все длины будут делиться на четыре, так что это будет не совсем так). Это повторное деление на два и может продолжаться не более log_2 (n) раз, потому что 2 ^ (log_2 (n)) = n, поэтому любое большее деление на 2 даст список нулевого размера.

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

Извините, если это тоже не полезно.

Ответ 6

Применяя алгоритм разделения и покоя, где вы разбиваете проблему на субъекты до тех пор, пока она не станет настолько простой, что тривиально, если разбиение будет хорошо, размер каждой подзадачи равен n/2 или около нее, Это часто является источником log(n), который возникает в сложной сложности: O(log(n)) - это количество рекурсивных вызовов, необходимых при правильном разделении.