Каковы характеристики

Иногда легко определить временную сложность алгоритма, если внимательно его изучить. Алгоритмы с двумя вложенными циклами , очевидно, N 2 . Алгоритмы , которые исследуют все возможные комбинации N групп из двух значений, очевидно , 2 N .$N$$N^2$$N$$2^N$

Однако я не знаю, как «определить» алгоритм со сложностью . Например, рекурсивная реализация сортировки слиянием - одна. Каковы общие характеристики или другая слияние thetas ; ( N журнал N ) алгоритмы , которые дали бы мне ключ , если я анализировал один?$\Theta(N \log N)$$\Theta(N \log N)$

Я уверен, что существует более одного способа, с помощью которых алгоритм может иметь сложность , поэтому любые ответы приветствуются. Кстати, я ищу общие характеристики и советы, а не строгие доказательства.$\Theta(N \log N)$

Ваш архетипический - это алгоритм « разделяй и властвуй» , который делит (и рекомбинирует) работу за линейное время и повторяет ее по частям. Сортировка слиянием работает следующим образом: тратьте O ( n ) времени, разбивая входные данные на две примерно равные части, рекурсивно сортируйте каждый фрагмент и тратите Θ ( n ) времени на объединение двух отсортированных половин.$\Theta(n \log n)$$O(n)$$\Theta(n)$

Интуитивно, продолжая идею «разделяй и властвуй», каждый этап деления занимает в целом линейное время, потому что увеличение количества частей, подлежащих разделению, точно соответствует уменьшению размера частей, поскольку время, затрачиваемое на деление, является линейным. Общее время выполнения - это произведение общей стоимости этапа деления, умноженное на количество этапов деления. Поскольку размер кусков уменьшается вдвое, есть этапов деления, поэтому общее время выполнения составляет n ⋅ log ( n ) . (До мультипликативной константы основание логарифма не имеет значения.)$\log_2(n)$$n \cdot \log(n)$

Подставляя его в уравнения (), один из способов оценки времени работы такого алгоритма состоит в том, чтобы выразить его рекурсивно: T ( n ) = 2 T ( n / 2 ) + Θ ( n ) . Понятно, что этот алгоритм занимает больше, чем линейное время, и мы можем увидеть, насколько больше, разделив на n : T ( n $T(n)$$T(n) = 2 T(n/2) + \Theta(n)$$n$ Когдаnудваивается,T(n)/nувеличивается на постоянную величину:T(n)/nувеличивается логарифмически, или, другими словами,T(n)=Θ(nlogn).

Это пример более общего паттерна: основная теорема . Для любого рекурсивного алгоритма , который делит его ввод размера в течение кусков размера п / б и занимает время п ( п ) для выполнения разделения и рекомбинации, время работы удовлетворяет условие Т ( п ) = а ⋅ Т ( п / б ) + f ( n ) . Это приводит к закрытой форме, которая зависит от значений a и b и формы$n$$a$$n/b$$f(n)$$T(n) = a \cdot T(n/b) + f(n)$$a$$b$ . Если a = b и f ( n ) = Θ ( n ) , основная теорема утверждает, что T ( n ) = Θ ( n log n ) .$f$$a = b$$f(n) = \Theta(n)$$T(n) = \Theta(n \log n)$

Две другие категории алгоритмов, которые занимают времени:$\Theta(n \log n)$

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

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

Другая категория: Алгоритмы , в которых выходной сигнал имеет размер & , и , следовательно , Θ ( п войти п ) время работы является линейной в выходном размере .$\Theta(n \log n)$$\Theta(n \log n)$

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

Это происходит в структурах данных, которые основаны на расширенном бинарном дереве поиска, где каждый узел хранит структуру данных линейного размера для поиска по листьям в поддереве этого узла. Такие структуры данных часто встречаются при поиске геометрического диапазона и часто основаны на схеме декомпозиции . Смотрите обзор Агарвала .

$O(n \log n)$$O(\log n)$

$O(n\log n)$$k$$O(n)$$O(n)$$O(n)$

Это, как правило, алгоритмы типа «разделяй и властвуй», где затраты на деление и объединение подрешений не являются «слишком большими». Посмотрите этот FAQ, чтобы увидеть, какие виды рецидивов приводят к такому поведению.

Как правило, алгоритмы «разделяй и властвуй» приведут к сложности O (N log N).

$O(n \log n)$

for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

$O(n^2)$

Я не могу привести конкретный пример алгоритма, который использует этот цикл, но он часто возникает при кодировании пользовательских алгоритмов.