Por que o Big O é ensinado em vez do Big Theta?

21

A notação Big O fornece um limite superior para uma função, enquanto Big Theta fornece um limite rígido. No entanto, acho que a notação Big O é tipicamente (e informalmente) ensinada e usada quando realmente significa Big Theta.

por exemplo, "Quicksort é O (N ^ 2)" pode se transformar na afirmação mais forte "Quicksort é Θ (N ^ 2)"

Embora o uso do Big O seja tecnicamente correto, um uso mais predominante do Big Theta não seria mais expressivo e levaria a menos confusão? Existe alguma razão histórica pela qual esse Big O é mais comumente usado?

Notas da Wikipedia :

Informalmente, especialmente na ciência da computação, a notação Big O geralmente pode ser um pouco abusada para descrever um vínculo estreito assintótico, onde o uso da notação Big Theta pode ser mais factualmente apropriado em um determinado contexto.

notation big-o big-theta tskuzzy
fonte
3
Eu sei que isso realmente não se refere à questão, mas quicksort não é teta (N ^ 2). É O (N ^ 2).
jsternberg
Big O é o que os iniciantes / pessoas que não são de CS precisam saber. Big Theta é o que é abordado em uma introdução a algoritmos, que não será adotada por todos os principais. Aqueles que tiveram uma classe de algoritmos podem ler a notação Big O mais profundamente, se assim o desejarem. Não sei ao que a citação da Wikipedia se refere. Com publicações acadêmicas, você terá uma garganta cortada em uma conferência se confundir Big O e Big Theta. Algumas pessoas passam a vida inteira perseguindo o Theta e esses são problemas DUROS DUROS.
Job
@jsternberg Tecnicamente, você está correto. Isso também é verdade, mas não faz sentido: "De qualquer forma, o quicksort (pior, o melhor, ...) é O (n ^ 100). Mas eu concordo com o OP, que deve ser mais preciso: o pior caso do QuickSort é Theta (N ^ 2), o melhor caso do QuickSort é Theta (NlogN), porque em cada caso teremos funções diferentes.
Eldar

Respostas:

26

Porque você geralmente está apenas interessado no pior caso ao analisar o desempenho. Assim, conhecer o limite superior é suficiente.

Quando é executado mais rápido do que o esperado para uma determinada entrada - tudo bem, não é o ponto crítico. É principalmente informações insignificantes.

Alguns algoritmos, como observou Peter Taylor, não têm uma ligação rígida. Veja quicksort, por exemplo, que é O (n ^ 2) e Omega (n).

Além disso, limites apertados costumam ser mais difíceis de calcular.

Veja também:

Falcão
fonte
6
Mas Big O não corresponde necessariamente ao pior desempenho. Eu poderia dizer que o quicksort é executado em O (2 ^ n) e estar 100% correto. Seria muito mais significativo se eu dissesse que o algoritmo X é executado em Theta (N ^ 2) em vez de O (N ^ 2).
tskuzzy
Além disso, limites apertados são quase sempre calculados ao analisar algoritmos, em vez de apenas um limite superior. Estou perguntando por que as pessoas não usam apenas a notação teta muito mais expressiva quando podem.
tskuzzy
9
Eu lhe disse por que a maioria dos programadores não o usa. Somos preguiçosos e não precisamos de tanta precisão. Ninguém o impede de usar big theta, se quiser. Vá em frente, faça. Sua escolha de algoritmo provavelmente não se beneficiará muito disso. Nunca ouvi falar de um programador confuso com a grande notação O. Eu também não acho nada confuso.
Falcon
9

Uma razão é que há muitos casos em que simplesmente não é conhecido. Por exemplo, a multiplicação da matriz é O (n ^ 2.376), mas não há um limite restrito conhecido. Claro, tanto quanto eu posso dizer, não é um apertado com destino a multiplicação de matrizes, mas não sabemos o seu valor.

MSalters
fonte
Mas esses seriam os limites para o tempo de execução de um problema, não um algoritmo específico. Embora a multiplicação de matrizes em geral possa ser resolvida mais rapidamente que o tempo cúbico, o algoritmo ingênuo é Θ (n ^ 3), não importa o quê.
tskuzzy
5
@tskuzzy, tome quicksort. Ele não tem um limite Theta, porque é O (n ^ 2) e Ômega (n).
Peter Taylor