Big Oh for (n log n)

В настоящее время я изучаю основные алгоритмы для Big Oh. Мне было интересно, может ли кто-нибудь показать мне, какой код для (n log n) в Java с помощью Big Oh будет похож или направить меня на любую страницу SO, где она существует.

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

Ответ 1

int n = 100
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n)
{
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times
    {

    }
}

Объяснение: Внешний цикл должен быть ясным. Выполняется n раз. Теперь во внутренний цикл. Во внутреннем цикле вы просто берете n и всегда делите его на 2. поэтому вы спрашиваете себя: сколько раз я могу разделить n на 2.

Оказывается, что это в O (log n). (на самом деле база log равна 2, но в примечаниях Big-Oh мы оставляем базу, так как она добавит только некоторые факторы в наш журнал, который нам неинтересен).

Таким образом, вы выполняете цикл n раз, и в этом цикле вы выполняете другой log(n) цикла log(n) чтобы вы имели O(n) * O(log n) = O(n log n).

Ответ 2

Очень популярным алгоритмом O (n log n) является сортировка слияния. http://en.wikipedia.org/wiki/Merge_sort, например, алгоритм и псевдокод. Логарифмическая часть алгоритма достигается путем разбиения проблемы на более мелкие подзадачи, в которых высота дерева рекурсии равна log n.

Множество сортировочных алгоритмов имеет время работы O (n log n). Дополнительную информацию см. В http://en.wikipedia.org/wiki/Sorting_algorithm.

Ответ 3

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

Например, в MergeSort список уменьшается в два раза, каждая часть отдельно сортируется по объему, а затем две половины объединяются вместе. Каждый список сокращен вдвое.

Всякий раз, когда вы сокращаете или уменьшаете объем на определенный фиксированный коэффициент, вы обычно получаете компонент log n из O(.).

В терминах кода взгляните на алгоритм MergeSort. Важной особенностью типичных реализаций является то, что она рекурсивна (обратите внимание, что TopDownSplitMerge дважды вызывает себя в коде, указанном в Википедии).

Все хорошие стандартные алгоритмы сортировки имеют временную сложность O(n log n) и в худшем случае невозможно сделать лучше, см. Сравнение Сортировка.

Чтобы увидеть, как это выглядит в Java-коде, просто выполните поиск ! Вот один пример.

Ответ 4

http://en.wikipedia.org/wiki/Heapsort

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