Почему список сортировки nlogn

Question

Я пытался погуглить, но был сбит с толку. Поскольку это начало онлайн-курса, и мы не знакомы с такими понятиями, как сортировка слиянием.

Нам дан псевдокод ниже и сказано, что в нем есть операции nlogn.

MaxPairwiseProductBySorting(A[1 . . . n]): 
Sort(A)
return A[n − 1] · A[n]

Я понимаю, почему что-то подобное ниже может иметь n ^ 2 операций. Но я полностью заблудился в том месте, откуда пришёл nlogn.

MaxPairwiseProductNaive(A[1 . . . n]): product ← 0
    fori from1ton:
        forj fromi+1ton: 
            product←max(product,A[i]·A[j])
return product

Answer 1

Предположение в этом коде состоит в том, что вы имеете дело с так называемой сортировкой сравнения, которая упорядочивает элементы массива путем сравнения двух одновременно.

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

Например, для n = 3:

                   -------------1:2-----------------
                  <=                               >
          --------2:3-------                ------2:3-----
         <=                >               <=            >
      {1,2,3}         ----1:3----       ---1:3---      {3,2,1}
                     <=         >      <=       >
                    {1,3,2}  {3,1,2}  {2,1,3} {2,3,1}

Очевидно, что дерево решений должно содержать все возможные перестановки значений n в виде листьев. В противном случае существовали бы входные перестановки, которые наш алгоритм не мог бы правильно отсортировать. Это означает, что дерево должно иметь не менее n! листьев. Итак, у нас есть

n! <= nleafs <= 2^h

, где h - высота нашего дерева. Взяв логарифм обеих сторон, получим

n lg n >= lg 1 + lg 2 + ... + lg n = lg n! >= h

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

Answer 2

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

• Разбейте задачу сортировки списка на две меньшие задачи сортировки
• Повторите

... с некоторым способом обработки очень маленьких сортировок.

Журнал (n) происходит из-за неоднократного разделения проблемы. N исходит из того факта, что мы должны отсортировать все части, что составит n, так как мы ничего не избавились.

Это поможет вам прочитать спецификацию c вроде, чтобы понять это лучше. Mergesort и quicksort - это два общих вида, и в Википедии есть хорошие статьи по обоим видам.