O Quicksort sempre tem tempo de execução quadrático se você escolher um elemento máximo como pivô?

9

Se você possui um algoritmo de classificação rápida e sempre seleciona o menor (ou maior) elemento como seu pivô; estou certo ao supor que, se você fornecer um conjunto de dados já classificado, sempre obterá o pior desempenho possível, independentemente de sua lista 'já classificada' estar em ordem crescente ou decrescente?

Meu pensamento é que, se você sempre escolher o menor elemento para o seu pivô, se a entrada 'já classificada' é classificada por crescente ou decrescente, não importa, porque o subconjunto escolhido para ser classificado em relação ao seu pivô sempre será o mesmo tamanho?

algorithms time-complexity algorithm-analysis runtime-analysis sorting yoonsi
fonte

2

Seu pensamento está correto, mas você também pode argumentar diretamente e calcular o tempo de execução do quicksort nesse caso - você receberá

.

O (n^{2})

$O(n^2)$

Yuval Filmus

15

$\Theta(n^2)$

walrii
fonte

2

Era melhor escrever: "... Isso é conseguido escolhendo pivôs que dividem o conjunto, de modo que um grupo tenha apenas um membro O (1)"

@Saeed Amiri: Está certo, mas é melhor ser preciso.

MMS

11

@SaeedAmiri: O (1) indica que é proporcional a 1, o que significa que pode ser k * 1. O pior caso real é alcançado quando é exatamente 1. Concordo que O (1) ainda pode levar a O (n ^ 2).

walrii

O (1)

$O(1)$

Θ (n^{2})

$\Theta (n^2)$

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta (n^2)$

5

$\Theta(n^2)$

n0nChun
fonte

3

$0$ $1$ $(n-1)$ $O(n^2)$

t (n) = t (n - 1) + t (0) + O (n) = O (n^{2})

$t(n)=t(n-1)+t(0)+O(n)= O(n^2)$

sulava
fonte

O Quicksort sempre tem tempo de execução quadrático se você escolher um elemento máximo como pivô?

Respostas: