Вопрос по complexity-theory, algorithm – Интуитивно понятное объяснение, почему QuickSort это n log n?

40

Кто-нибудь может дать «простой английский»? Интуитивно понятное, но формальное объяснение того, что делает QuickSort n log n? Насколько я понимаю, он должен пройти через n элементов, и он делает этот журнал n раз ... Я не уверен, как выразить это словами, почему он делает этот журнал n раз.

Ваш Ответ

4   ответа
105

log n Частично это происходит из-за того, что он (по крайней мере, в идеале) разбивает входные данные пополам на каждой итерации. Начиная с N элементов и разбивая их пополам каждый раз, вы получаете до 1 элемента после журнала.2(N) итераций, в этот момент вы, очевидно, больше не можете его подразделить. Например, начиная с, скажем, 128 элементов, вы делите на группы по 64, 32, 16, 8, 4, 2, 1 элемента - 7 итераций (и журнал2(128) = 7).

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

Между этими двумя действиями вы получите O (log N) операций, каждая из которых имеет O (n) сложность, для O (n log n) общей сложности.

Чтобы быть технически правильным, Big-O Quicksort на самом деле O (N2) хоть. Это связано с тем, что достаточно неудачный выбор элемента разбиения мог бы разбить массив на один элемент с одной стороны и весь остальной массив с другой. Если это происходит на каждой итерации, потребуется N итераций, чтобы разбить его на части по одному элементу на каждый, так что вы получите N операций, каждая со сложностью O (N), для O (N * N) в целом.

В реальной реализации вы обычно останавливаетесь перед этим, но это самое дальнее, что вы можете сделать.

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

но максимальное число сравнений составляет logN для каждого элемента (первое - N, второй свод - N / 2,3rd N / 4.. Предполагается, что сводка средний элемент)

2

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

Чтобы визуализировать «n log n», можно предположить, что ось является элементом, ближайшим к среднему значению всех элементов в массиве, который должен быть отсортирован. Это разделит массив на 2 части примерно одинаковой длины. В обоих случаях вы применяете процедуру быстрой сортировки.

Так как на каждом шаге вы вдвое уменьшаете длину массива, вы будете делать это для log n (base 2) раз, пока не достигнете length = 1, т.е. отсортированный массив из 1 элемента.

Вы & APOS; ре & # x200B; верно, но не смешивать среднее и среднее. Медиана - это то, что позволяет разделить на две части одинаковой длины (+ -1).
Среднее не даст среднего элемента. Медиана даст средний элемент / с. Ответ требует исправления для этой части. В остальном хорошо.
42

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

То есть в среднем журнале n операций разбиения, и каждое разбиение занимает O (n) операций.

Похожие вопросы