Tentando entender o 2N lnN se compara ao quicksort

Eu estava passando pela análise do quicksort no livro de Algoritmos de Sedgewick. Ele cria a seguinte relação de recorrência para o número de comparações no quicksort enquanto classifica uma matriz de N itens distintos.

Estou tendo dificuldades para entender isso ... Eu sei que é preciso 1 / N de probabilidade para qualquer elemento se tornar o pivô e que, se k se tornar o pivô, o sub-array esquerdo terá k-1 elementos e o sub-direito matriz terá elementos Nk.

1.Como o custo do particionamento se torna N + 1? É necessário o comparador N + 1 para fazer o particionamento?

2.Sedgewick diz que, para cada valor de k, se você somar esses valores, a probabilidade de que o elemento de particionamento seja k + o custo para as duas sub-matrizes que você obtém a equação acima.

• Alguém pode explicar isso para que aqueles com menos conhecimento de matemática (eu) possam entender?
• Especificamente, como você obtém o segundo termo na equação?
• O que exatamente esse termo significa?

A função de custo Cdo quicksort consiste em duas partes. A primeira parte é o custo de particionar o array em duas 'metades' (as metades não precisam ter o mesmo tamanho, daí as aspas). A segunda parte é o custo da classificação dessas duas metades.

1. O (N + 1)termo é na verdade um termo condensado e vem dos termos

   (N - 1) + 2
   

   Esse é o custo do particionamento no quicksort: N-1compara com o valor de pivô e 2 compara adicionais devido a algumas condições de contorno no particionamento.

2. A segunda parte da equação consiste nos custos para classificar as duas 'metades' em ambos os lados do valor do pivô k.

   Depois de escolher um valor de pivô, você terá duas 'metades' não ordenadas. O custo da classificação dessas 'metades' depende do tamanho e é mais fácil descrito como uma aplicação recursiva da função de custo C. Se o pivô for o menor dos Nvalores, os custos para classificar cada uma das duas 'metades' serão respectivamente C(0)e C(N-1)(o custo para classificar uma matriz com 0 elementos e o custo para classificar uma com N-1elementos). Se o pivô for o quinto menor, o custo para classificar cada uma das duas 'metades' será respectivamente C(5)e C(N-6)(o custo para classificar uma matriz com 5 elementos e o custo para classificar uma com N-6elementos). E da mesma forma para todos os outros valores de pivô.

   Mas quanto custa classificar essas duas 'metades' se você não souber o valor do pivô? Isso é feito considerando o custo de cada valor possível do pivô e multiplicando-o pela chance de esse valor específico aparecer.

   Como cada valor de pivô é igualmente provável, a chance de escolher um valor de pivô específico é 1/Nse você tiver Nelementos. Para entender isso, pense em rolar um dado. Com um dado adequado, a chance de cada lado acabar voltada para cima é igual, então a chance de rolar um 1 é 1/6.

   Combinado, isso fornece o termo de soma onde, para cada valor possível k do pivô, o custo ( C(k-1) + C(N-k)) é multiplicado pela chance ( 1/N)

3. A derivação adicional da fórmula de somatória na pergunta para 2N lnNno título exige muita matemática para explicar detalhes aqui, mas é baseada no entendimento de que o custo para classificar uma matriz de Nelementos ( C(N)) pode ser expresso em termos de classificação de um matriz de N-1elementos ( C(N-1)) e um fator diretamente proporcional a N.

1. Parece que N + 1 como o número de comparações para a etapa da partição é um erro no livro. Você precisa descobrir para cada um dos elementos não dinâmicos N – 1 se é menor ou maior que o dinâmico, o que requer uma comparação; portanto, comparações N-1 no total, não N + 1. (Considere o caso mais simples, N = 2, ou seja, um pivô e outro elemento: não há absolutamente nenhum espaço para fazer três comparações entre dois elementos.)

2. Considere o caso em que o pivô escolhido é o menor elemento (k = 1). Isso significa que a matriz é dividida em uma parte vazia à esquerda (não há elementos menores que o pivô) e uma parte à direita que contém todos os elementos, exceto o pivô (todos os outros elementos são maiores que o pivô ) Isso significa que os subproblemas que agora você deseja resolver recursivamente têm os tamanhos 0 e N – 1 (k – 1 e N – k), respectivamente, e requerem comparações C (0) e C (N – 1); assim, C (0) + C (N – 1) no total.

   Se o pivô for o segundo menor elemento (k = 2), os tamanhos dos subproblemas serão 1 e N – 2 (k – 1 e N – k; um elemento à esquerda, porque é o único menor que o pivô). Portanto, a solução recursiva desses subproblemas requer comparações C (1) + C (N – 2). E assim por diante, se o pivô for o terceiro menor elemento, o quarto etc. Essas são as expressões nos numeradores.

   Como o pivô é escolhido aleatoriamente dentre os elementos N, cada caso (o pivô é o menor, o pivô é o segundo menor etc.) ocorre com a mesma probabilidade 1 / N. É daí que vem o N nos denominadores.