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

8

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Θ(n2)
  • Melhor caso: ; quando a entrada já estiver classificadaΘ(n)
  • Nº de comparações: no pior caso & no melhor casoΘ(n2)Θ(n)
  • No. de swaps: no pior / caso médio e no melhor casoΘ(n2)0

Classificação da seleção:

  • Caso médio / pior caso / melhor caso:Θ(n2)
  • Nº de comparações: Θ(n2)
  • Nº de swaps: Θ(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: Θ(nlgn); não importa se a entrada é classificada ou não
  • Nº de comparações: Θ(n+m) no pior dos casos & Θ(n)no melhor dos casos; assumindo que estamos mesclando duas matrizes de tamanho n & m onden<m
  • Nº de swaps: sem swaps! [mas requer memória extra, não classificação no local]

Ordenação rápida:

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

Tipo de bolha:

  • Pior caso : Θ(n2)
  • Melhor caso : Θ(n); já classificado
  • Nº de comparações: Θ(n2) no pior dos casos e no melhor caso
  • Nº de swaps: Θ(n2) no pior dos casos & 0 no melhor dos casos

Pesquisa linear:

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

Pesquisa binária:

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

  1. Eu considerei apenas algoritmos básicos de pesquisa e classificação.
  2. Supõe-se acima que os algoritmos de classificação produzem saída em ordem crescente
  3. Fontes: O incrível CLRS e este Wiki
avi
fonte
Para discutir os méritos dessa (espécie de) pergunta, junte-se a nós no chat .
Raphael
1
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 Θ(n2)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ãon não 0.

Para a classificação Rápida, você mencionou que as trocas de pior caso são n2. 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
1
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áΘ(n2)swaps, mesmo com a detecção "sem troca". O Quicksort normalmente é executado no tempoO(nlogn) então o melhor caso não pode ser n2swaps.
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(nlogn). Portanto, o melhor caso também éO(nlogn) etapas de tempo (pode ser mais rápido, mas O()dá apenas um limite superior). NoO(nlogn) etapas, você não pode fazer nada n2times - comparações, swaps ou qualquer outra coisa. Você não pode usar mais do queO(nlogn)memória também. O melhor caso para qualquer medida de complexidade não pode ser superior aO(nlogn).
precisa saber é o seguinte
Você está correto, editei minha resposta para Classificação rápida.
Nikhil Mahajan