Complexidades das operações básicas dos algoritmos de busca e classificação [fechado]

O Wiki tem uma boa folha de dicas, mas não envolve não. de comparações ou swaps. (embora o número de swaps geralmente decida sua complexidade). Então eu criei o seguinte. As informações a seguir estão corretas? Informe-me se houver algum erro, eu o corrigirei.

Classificação de inserção:

Caso médio / pior caso: ; acontece quando a entrada já está classificada em ordem decrescente $\Theta(n^2)$
Melhor caso: ; quando a entrada já estiver classificada $\Theta(n)$
Nº de comparações: no pior caso & no melhor caso $\Theta(n^2)$ $\Theta(n)$
No. de swaps: no pior / caso médio e no melhor caso $\Theta(n^2)$ $0$

Classificação da seleção:

Caso médio / pior caso / melhor caso: $\Theta(n^2)$
Nº de comparações: $\Theta(n^2)$
Nº de swaps: $\Theta(n)$ no pior / caso médio e $0$ na melhor das hipóteses No máximo, o algoritmo exige N swaps, depois que você troca um elemento no lugar, nunca o toca novamente.

Mesclar Classificação:

Caso médio / pior caso / melhor caso: $\Theta(nlgn)$ ; não importa se a entrada é classificada ou não
Nº de comparações: $\Theta(n+m)$ no pior dos casos & $\Theta(n)$ no melhor dos casos; assumindo que estamos mesclando duas matrizes de tamanho n & m onde $n<m$
Nº de swaps: sem swaps! [mas requer memória extra, não classificação no local]

Ordenação rápida:

Pior caso : $\Theta(n^2)$ ; acontece entrada já está classificada
Melhor caso : $\Theta(nlogn)$ ; quando o pivô divide o array exatamente pela metade
Nº de comparações: $\Theta(n^2)$ no pior dos casos & $\Theta(nlogn)$ no melhor dos casos
Nº de swaps: $\Theta(n^2)$ no pior dos casos & $0$ no melhor dos casos

Tipo de bolha:

Pior caso : $\Theta(n^2)$
Melhor caso : $\Theta(n)$ ; já classificado
Nº de comparações: $\Theta(n^2)$ no pior dos casos e no melhor caso
Nº de swaps: $\Theta(n^2)$ no pior dos casos & $0$ no melhor dos casos

Pesquisa linear:

Pior caso : $\Theta(n)$ ; chave de pesquisa ausente ou último elemento
Melhor caso : $\Theta(1)$ ; primeiro elemento
Nº de comparações: $\Theta(n)$ no pior dos casos & $1$ no melhor dos casos

Pesquisa binária:

Pior / Média: $\Theta(logn)$
Melhor caso : $\Theta(1)$ ; quando chave é elemento do meio
Nº de comparações: $\Theta(logn)$ no pior / caso médio e $1$ no melhor dos casos

Eu considerei apenas algoritmos básicos de pesquisa e classificação.
Supõe-se acima que os algoritmos de classificação produzem saída em ordem crescente
Fontes: O incrível CLRS e este Wiki

algorithm-analysis asymptotics runtime-analysis sorting searching avi
fonte

Para discutir os méritos dessa (espécie de) pergunta, junte-se a nós no chat .

Raphael

Esta não é uma pergunta, portanto está fora de tópico.

David Richerby

Eu votei para fechar também. Esta é, talvez, um desafio para salvar também porque a "questão" é bastante amplo (que são a pesquisa básica e algoritmos de ordenação, exatamente?)

Juho

Respostas:

-2

Para algoritmos gerais de classificação por bolhas, as piores comparações são $\Theta(n^2)$ Mas para o algoritmo de caso especial em que você adiciona um sinalizador para indicar que houve uma troca no passe anterior. Se não houver swaps, sairemos do loop, pois o array já está classificado. Nesse caso, as comparações são $n$ não 0.

Para a classificação Rápida, você mencionou que as trocas de pior caso são $n^2$ . O pior cenário para a classificação rápida é quando todos os elementos estão na ordem de classificação, portanto não haverá swaps, portanto, deve ser zero.

Nikhil Mahajan
fonte

Eu não entendo sua resposta. A detecção de "sem trocas" no tipo de bolha certamente o torna mais rápido, mas, se a entrada estiver na ordem oposta à saída, você ainda precisará

Θ (n^{2})

$\Theta(n^2)$ swaps, mesmo com a detecção "sem troca". O Quicksort normalmente é executado no tempo

O (n \log n)

$O(n\log n)$ então o melhor caso não pode ser

n^{2}

$n^2$ swaps.

David Richerby

Obrigado por editar o meu comentário, eu sou novo no SE. Bem, eu deveria ter sido mais claro sobre isso. Acabei de editar meu comentário acima. Eu estava tentando dizer que as melhores comparações de casos não podem ser 0 no caso do tipo Bubble, ele tem que n. quando a matriz é classificada e você está usando o sinalizador para indicar a troca no passe anterior. se não houver troca na passagem anterior, o array já estará classificado; portanto, não será necessário avançar mais na primeira passagem, estamos fazendo n comparações. Para a ordenação rápida, estou falando de comparações e swaps, e não de complexidade de tempo; no pior dos casos, todos os elementos são classificados, portanto, não é necessário trocar swaps.

Nikhil Mahajan

No caso normal, o quicksort é executado no tempo

O (n \log n)

$O(n\log n)$ . Portanto, o melhor caso também é

O (n \log n)

$O(n\log n)$ etapas de tempo (pode ser mais rápido, mas

O (-)

$O(-)$ dá apenas um limite superior). No

O (n \log n)

$O(n\log n)$ etapas, você não pode fazer nada

n^{2}

$n^2$ times - comparações, swaps ou qualquer outra coisa. Você não pode usar mais do que

O (n \log n)

$O(n\log n)$ memória também. O melhor caso para qualquer medida de complexidade não pode ser superior a

O (n \log n)

$O(n\log n)$ .

precisa saber é o seguinte

Você está correto, editei minha resposta para Classificação rápida.

Nikhil Mahajan