Откуда log (n) в обозначении O (N)

Question

Я знаю, что такое обозначение O (n), и я также понимаю, как получить нотации, такие как O (n), O (n ² ), ....

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

как я могу получить журнал (N)?

PS: Я знаю API Коллекций и некоторые классы, которые имеют время обхода O (n log n).Мне нужно простое объяснение.

Answer 1

lg N применяется в алгоритмах «разделяй и властвуй», где вы итеративно или рекурсивно пропускаете половину данных в наборе из N элементов. Двоичный поиск является типичным примером. Операции вставки, поиска и удаления в двоичных деревьях поиска также выполняются за O (lg N ).

Итеративное отбрасывание половины элементов в интуитивном смысле является обратным к итеративному удвоению количества элементов. Удвоение дало бы O (2 ^ N ) элементов за N итераций. Обратите внимание, что двоичный логарифм N является обратной величиной возведения двух в степень N .

Сортировка массива может быть выполнена в O ( N lg N ) с помощью таких алгоритмов, как mergesort, но также концептуально проще: перебрать массив и поместить элементы в двоичный дерево поиска. Каждая вставка занимает O (LG N ), и их N , поэтому алгоритм работает в O ( N LG N ) .

(Сортировка по BST даже имеет сложность O ( N lg N ) в худшем случае, если дерево сбалансировано .)

Answer 2

Лучший пример N * log (N) , на мой взгляд, будет выглядеть на основе сравнения поиска:

Давайте возьмем сортировку слиянием в качестве примера.

Алгоритм принимает массив элементов, рекурсивно разбивает его на 2, пока не получит массив длины 2, затем объединяет части в O (n), каждое объединение отсортированных массивов проще.

Хорошо, это было краткое описание, теперь давайте посмотрим, как это выглядит:

  [ 1 2 3 4 5 6 7 8 ]  
           |  
           /\  
  [1 2 3 4]  [ 5 6 7 8 ]
      |             |
      /\            /\
[1 2 ] [ 3 4]   [5 6] [7 8]

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

Итак, здесь сложность N * log (N) .

Большинство алгоритмов, имеющих сложность Log (N), получают это издревовидный алгоритм.
Некоторые из них являются просто вероятностным log (n) (что означает, что после долгих математических вычислений вы получитев среднем это будет что-то вроде log (n))

Answer 3

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