сложность помочь .. O (n ^ 2), 0 (nlog) и т. д.

Question

эй, может, кто-нибудь поможет мне определить сложность? Пример, приведенный в моем классе, был

пузырьковая сортировка

int main() {
   int a[10] = {10,9,8,7,6,5,4,3,2,1};
   int i,j,temp;

   for (j=0;j<10;j++) {
      for (i=0;i<9;i++) {
         if (a[i] > a[i+1]) {
            temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
         }
      }
   }
   for (i=0;i<10;i++) {
      printf("%d ",a[i]);
   }
}

, который имел сложность O (n ^ 2), поскольку имел две петли O (n), следовательно, O (n) x O (n).

---

и они сказали, что быстрая сортировка имеет сложность O (nlog (n)) .. почему это так?

это потому, что, проходя цикл, он делит число?

-Спасибо

Answer 1

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

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

С другой стороны, другие алгоритмы сортировки, такие как сортировка слиянием и сортировка кучи, всегда имеют значение O ( n log n ). У них нет патологических случаев, когда их производительность ухудшается до O ( n ² ). Это делает их предпочтительными, если то, что вы хотите, является стабильной, предсказуемой производительностью во все времена. Преимущество быстрой сортировки в том, что в целом алгоритм работает быстрее, но не всегда так.

Редактировать : Действительно, как говорит @ pst , сортировка слиянием требует O ( n ) пространства при сортировке массивов (пустое пространство для слияний), что меньше, чем идеал. Это против этого. Но есть еще один момент против быстрой сортировки - это нестабильная сортировка. Элементы, равные друг другу, могут перемешиваться после сортировки.

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

Answer 2

Нотация Big-O - это просто отношение между входным значением (количество элементов в вашем случае) и сложностью (сложность времени в вашем случае, также может быть сложность пространства).

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

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

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

Сочетание двух дает O (n log n).

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

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

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

Answer 3

Предыдущие ответы довольно хорошо описывают быструю сортировку и время ее выполнения, но я хочу прокомментировать время выполнения наихудшего случая.

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

Вы можете реализовать быструю сортировку для запуска в наихудшем случае O (n log n), мудро выбрав опору. Один из способов - найти медиану за O (n) времени. (См. http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22) Тогда, если вы всегда разбиваете по медиане, количество проверок любого элемента не превышает O (log n), так что общее время работы O (n log n).

Answer 4

На самом деле быстрой сортировкой является O (n log (n)) в среднем случае. В худшем случае вы выбираете самый большой или самый маленький элемент в качестве раздела каждый раз и делаете n + (n -1) + ... 1 = O (n ^ 2).

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

Как сказал Тон, вы можете получить тот же результат, применив теорему Учителя, но, вероятно, стоит потратить время на то, чтобы сделать некоторые примеры вручную.

Answer 5

См. Анализ в Википедии .

Answer 6

Вопреки мнению всех здесь присутствующих, сложность вашей программы O (1). Вы не определили, что такое n. Я знаю, что мой ответ кажется немного глупым, но на практике часто важнее найти границы вашей проблемы, чем сложность алгоритма. Если ваш набор данных никогда не будет больше заданного размера, вам лучше использовать более простой метод с достаточно хорошей производительностью / поведением.

Answer 7

Быстрая сортировка рекурсивная. Просто напишите псевдокод, и вы сможете легко вывести рекурсивную формулу для времени выполнения каждого повторения, а затем использовать основную теорему для получения окончательного ответа.