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

Question

Я знаю, что есть довольно много вопросов по поводу больших обозначений O, я уже проверил:

• Простое английское объяснение Big O
• Большой O, как вы рассчитываете / приближаете его?
• Большая O нотация Домашнее задание - анализ алгоритма фрагмента кода?

чтобы назвать несколько.

По «интуиции» я знаю, как рассчитать его для n, n^2, n! и так, однако я совершенно заблудился, как рассчитать его для алгоритмов, log n, n log n, n log log n и т. Д.

Я имею в виду, что я знаю, что быстрая сортировка n log n (в среднем) .. но почему ? То же самое для слияния / расчески и т. Д.

Может ли кто-нибудь объяснить мне не слишком математически, как вы рассчитываете это?

Основная причина в том, что у меня будет большое интервью, и я уверен, что они будут просить такого рода вещи. Я проводил исследования в течение нескольких дней, и у всех, похоже, есть либо объяснение, почему сортировка пузырьков - n ^ 2, либо нечитаемое объяснение (для меня) в Wikipedia

Answer 1

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

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

Обычно такие проблемы можно выявить, представив их в виде сбалансированного двоичного дерева. Например, вот сортировка слиянием:

 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

Вверху находится вход, как листья дерева. Алгоритм создает новый узел путем сортировки двух узлов над ним. Мы знаем, что высота сбалансированного бинарного дерева равна 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 / что-то) и (n - n / что-то), все в порядке. Если оно разбито на (k) и (n-k), тогда высота дерева будет O (n), а не O (log n).

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

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

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

Answer 5

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

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

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

Теперь, когда у нас есть все эти n разделов, которые необходимо объединить, то после их объединения необходимо объединить следующий уровень, пока у нас снова не появится список длины n. Обратитесь к графике Википедии для простого примера этого процесса 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).

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

Answer 6

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