Сводный индекс и сбалансированные разделы (Java)
Для big-O для быстрой сортировки,
что это значит, когда сводный индекс создает сбалансированные разделы.
Я знаю, что сводный индекс - это индекс, в котором сумма чисел слева от индекса равна сумме чисел справа от индекса.
Как это влияет на сложность, когда создает сбалансированные разделы, а когда нет?
Ответы 1
Основная идея быстрой сортировки - рекурсивно разделить массив с помощью точки поворота.
В лучшем случае выбранная точка поворота всегда делит массив поровну на 2. Например, если у вас есть несортированный массив с [1, 3, 2, 6, 4, 7, 5], точка поворота, которая делит array на два равно 4. Это связано с тем, что, используя эту точку поворота для разделения массива, вы получаете [1, 2, 3, 4, 5, 6, 7] с 3 элементами на каждой стороне оси.
Записав соотношение повторения для этого случая, вы получите: T(n) = 2 T(n/2) + O(n), поскольку массив размера n теперь можно рассматривать как массивы размера 2 n / 2, а процесс разделения занимает O (n) времени. Используя основную теорему / какой-либо другой способ развернуть повторение, вы получите O (nlogn) в качестве среды выполнения для быстрой сортировки.
К сожалению, такой идеальный случай не всегда возможен в реальной жизни, потому что выбранная вами точка поворота может оказаться не такой уж и хорошей. В целом, однако, если вы выберете случайную точку поворота, у вас все равно будет хороший шанс разделить массив на 2 части разумного размера. В частности, если вы можете добиться разделения 1: 9, математически можно доказать, что время выполнения для быстрой сортировки по-прежнему будет O (nlogn). Это называется рандомизированной быстрой сортировкой, и в Интернете есть много ресурсов, которые объясняют стоящий за ней вероятностный анализ. Вот один такой ресурс.
Что вы имеете в виду под «сводным индексом - это индекс, в котором сумма чисел слева от индекса равна сумме чисел справа от индекса»? Вы уверены, что это быстрая сортировка?