сложность help..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) х О (п).

---

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

Это потому, что, когда он проходит вокруг цикла, он делит число?

-Спасибо

Answer 1

См анализ on Wikipedia.

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

На самом деле quicksort - это 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 6

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

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

Вы можете реализовать quicksort для работы в худшем случае 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 7

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