Как доказать, что равномерное разбиение является лучшим случаем для алгоритма быстрой сортировки?

Question

Почему мы говорим, что лучший вариант для быстрой сортировки - это то, что «каждый раз, когда мы выполняем разбиение, мы делим список на две почти равные части»?И как доказать это именно так называемый «лучший случай»?

Answer 1

Я создал программу, а не пытался провести анализ.Я сравнил случай разделения 1/2, 1/2 (50% 50%) и разделения 1/4, 3/4 (25% 75%), которое, по-видимому, подходит для выполнения на 22% больше операций при увеличении n.Код установлен для разделения 1 / 4,3 / 4: для разделения 1 / 2,1 / 2 измените строку слева = (n + 3) / 4 влево = (n + 1) / 2.Точка округления влево - убедиться, что слева> = 1, чтобы избежать бесконечной рекурсии.

#include <stdio.h>
typedef unsigned long long uint64_t;
static uint64_t sum;

void qsa(uint64_t n)
{
uint64_t left, right;
    if(n < 2)
        return;
    sum += n;
    left = (n+3)/4;         /* or left = (n+1)/2  */
    right = n - left;
    qsa(left);
    qsa(right);
}

int main()
{
    qsa(1024*1024);
    printf("%llu\n", sum);
    return(0);
}

результаты

n = 1024*1024
20971520     1/2 1/2   n log2(n)
25331387     1/4 3/4   ~1.208 n log2(n)

n = 16*1024*1024

402653184    1/2 1/2   n log2(n)
488049677    1/4 3/4   ~1.212 n log2(n)

n = 1024*1024*1024

32212254720  1/2 1/2   n log2(n)
39180282211  1/4 3/4   ~1.216 n log2(n)

n = 16*1024*1024*1024

584115552256 1/2 1/2   n log2(n)
711608157825 1/4 3/4   ~1.218 n log2(n)

Answer 2

Взять массив длины 2^N (для простоты).

Сравнить количество операций для случая идеальных разбиений на каждом этапе (N в N/2+N/2) и для случая делениядлина сегмента N в 1 и N-1