1

Se construir um algoritmo com complexidade de pior caso teta de n^2 posso ter como contrapartida uma complexidade de melhor caso para esse algoritmo com big O n^2?

1 Resposta 1

3

Sim. Mas eu usaria uma notação diferente para falar do melhor caso.

Quando escrevemos que o pior caso é O(f) queremos dizer que o tempo gasto no pior caso é assintóticamente menor ou igual a essa função. Mas o "menor ou igual" não serve pra se discutir sobre melhor caso.

O que queremos na verdade é uma notação que signifique "maior ou igual". A notação convencional pra isso é o Ω(f) (big-omega).

Voltando à pergunta original: se o pior caso é O(n^2), o melhor caso pode, sim, ser Ω(n^2). Basta que o seu algorítmo seja um cujo tempo de execução dependa apenas do tamanho da entrada, mas não de seu valor específico.

4
  • A complexidade de pior caso do algoritmo da questão é teta de n^2 (ele já tem um limite superior assintoticamente justo), não é big O de n^2. Quero saber se no algoritmo em questão a complexidade de melhor caso pode ser big O de n^2. 26/02/2016 às 23:08
  • Pode sim. Pegue o caso do quicksort: o pior caso é Θ(n^2) e o melhor caso é Θ(n log n)
    – hugomg
    26/02/2016 às 23:19
  • Desculpe mais vou insistir. Vc mostrou um caso em que tenho um algoritmo em que o pior caso é teta de n^2 mas o melhor caso não é big O do mesmo n^2 e sim de (nlogn). 26/02/2016 às 23:30
  • 1
    @MarcosAntonio E quanto ao algoritmo da seleção (selection sort)? Ele executa o mesmo número de passos não importa se a lista está ordenada, se não está, nem há qualquer caso particular que o faça executar mais rápido ou mais lento. Ou seja, ele é O(n^2) e Ω(n^2) - e portanto Θ(n^2) - tanto no melhor caso quanto no pior.
    – mgibsonbr
    27/02/2016 às 2:12

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .