Na maioria das aulas introdutórias de algoritmo, são apresentadas notações como (Big O) e , e um aluno geralmente aprende a usar uma delas para encontrar a complexidade do tempo.OOΘΘ
No entanto, existem outras notações, como , e . Existem cenários específicos em que uma notação seria preferível a outra?Ω ωooΩΩωω
não é muito preferível como aplicável ...
Você está se referindo à notação Landau . Eles não são símbolos diferentes para a mesma coisa, mas têm significados totalmente diferentes. Qual é "preferível" depende inteiramente da afirmação desejada.
f g ≤ f ∈ o ( g ) <f∈ O ( g)f∈O(g) significa que cresce no máximo tão rápido quanto , assintoticamente e até um fator constante; pense nisso como um . é a forma mais rígida, ou seja, .ffgg≤≤f∈ o ( g)f∈o(g)<<
f g ω f ∈ Ω ( g ) g ∈ O ( f )f∈ ohms ( g)f∈Ω(g) tem o significado simétrico: cresce pelo menos tão rápido quanto . é seu primo mais rígido. Você pode ver que é equivalente a .ffggωωf∈ ohms ( g)f∈Ω(g)g∈ O ( f)g∈O(f)
f g f ∈ S ( g ) ∩ ohms ( g ) f ~ g Θ óf∈ q ( g)f∈Θ(g) significa que cresce tão rápido quanto ; formalmente . (igualdade assintótica) é sua forma mais forte. Geralmente queremos dizer quando usamos .ffggf∈ O ( g) ∩ Ω ( g)f∈O(g)∩Ω(g)f∼ gf∼gΘΘOO
Observe como e seus irmãos são classes de função . É importante estar ciente disso e de suas definições precisas - que podem diferir dependendo de quem está falando - ao fazer "aritmética" com eles.O (g)O(g)
Ao provar as coisas, trabalhe com sua definição precisa. Existem muitas definições para os símbolos Landau (todas com a mesma intuição básica), algumas das quais equivalentes em alguns conjuntos de funções, mas não em outras.
Quais são as regras para sinais de igual com big-O e little-o?
Classificando funções por crescimento assintótico
Como O e Ω se relacionam com o pior e o melhor caso?
Notação O grande aninhada
Definição de para funções negativasΘΘ
Qual é o significado de ? O ( m + n )O(m+n)
O (mn) é considerado crescimento "linear" ou "quadrático"?
Soma dos termos do Landau revisitados
O que big O significa como termo de uma razão de aproximação?
Qualquer outra pergunta sobre assintóticos e notação landau como exercício.
Se você estiver interessado em usar a notação Landau de maneira rigorosa e sólida, poderá estar interessado em trabalhos recentes de Rutanen et al. [1] Eles formulam critérios necessários e suficientes para a notação assintótica à medida que os usamos em algoritmos, mostram que a definição comum falha em atendê-los e fornece uma (na verdade) definição viável.
Uma definição geral da notação O para análise de algoritmos por K. Rutanen et al. (2015)
Eu só quero ressaltar que, embora atue como e atue como , existem diferenças; não é difícil encontrar funções e tal que e . ≤ Ω ≥ g f f ∉ O ( g ) f ∉ Ω ( g )OO≤≤ΩΩ≥≥ggfff∉ O ( g)f∉O(g)f∉ ohms ( g)f∉Ω(g)
— Zach Langley
+1 para a menção das classes de função. Coisas como e aparecem em todos os lugares em papéis e livros, o que pode ser confuso para as pessoas que enfrentam essas notações pela primeira vez. Ω ( 2 n )o ( 1 )o(1)Ω ( 2n)Ω(2n)
@ZachLangley O que você diz é muito verdadeiro. Não há pedido total aqui. Provavelmente é perigoso criar , mas acho que serve ao propósito de criar intuição. ≤≤
Big O: limite superior
"Big O" ( ) é de longe o mais comum. Quando você analisa a complexidade de um algoritmo, na maioria das vezes, o que importa é ter um limite superior sobre a rapidez com que o tempo de execução cresce quando o tamanho da entrada aumenta. Basicamente, queremos saber que a execução do algoritmo não vai demorar "muito tempo". Não podemos expressar isso em unidades de tempo reais (segundos), porque isso dependeria da implementação precisa (da maneira como o programa é escrito, da qualidade do compilador, da rapidez com que o processador da máquina é ...). Portanto, avaliamos o que não depende de tais detalhes, que é quanto tempo leva para executar o algoritmo quando alimentamos uma entrada maior. E nos preocupamos principalmente quando podemos ter certeza de que o programa está concluído, por isso geralmente queremos saber que isso levará uma quantidade tão grande de tempo ou menos.OO
Dizer que um algoritmo tem um tempo de execução de para um tamanho de entrada significa que existe alguma constante modo que o algoritmo é concluído na maioria das etapas de , ou seja, o tempo de execução do algoritmo cresce no máximo tão rápido quanto (até um fator de escala). Observando o tempo de execução do algoritmo para o tamanho de entrada , informalmente significa que até algum fator de escala.n K KO ( f( N ) )O(f(n))nnKKf T ( n ) n O ( n ) T ( n ) ≤ f ( n )Kf( N )Kf(n)ffT( N )T(n)nnO ( n )O(n)T( n ) ≤ f( N )T(n)≤f(n)
Às vezes, é útil ter mais informações que um limite superior. é o inverso de : expressa que uma função cresce pelo menos tão rápido quanto outra. significa que para uma constante , ou, para ser informal, acima a algum fator de escala.O T ( n ) = Ω ( g ( n ) ) T ( N ) ≥ K ′ g ( n ) K ′ T ( n ) ≥ g ( n )ΩΩOOT( n ) = Ω ( g( N ) )T(n)=Ω(g(n))T( N) ≥ K′g( N )T(N)≥K′g(n)T( n ) ≥ g( N )T(n)≥g(n)
Quando o tempo de execução do algoritmo pode ser determinado com precisão, combina e : ele expressa que a taxa de crescimento de uma função é conhecida, até um fator de escala. significa que para algumas constantes e . Informalmente, até algum fator de escala.O Ω T ( n ) = Θ ( h ( n ) ) K h ( n ) ≥ T ( n ) ≥ K ′ h ( n ) K K ′ T ( n ) ≈ h ( n )ΘΘOOΩΩT( n ) = Θ ( h ( n ) )T(n)=Θ(h(n))Kh ( n ) ≥ T( n ) ≥ K′h ( n )Kh(n)≥T(n)≥K′h(n)T( n ) ≈ h ( n )T(n)≈h(n)
O "pequeno" e são usados ​​com muito menos frequência na análise de complexidade. Pouco é mais forte que grande ; onde indica um crescimento que não é mais rápido, indica que o crescimento é estritamente mais lento. Por outro lado, indica um crescimento estritamente mais rápido.ω ó ó ó ó ωooωωooOOOOooωω
Eu fui um pouco informal na discussão acima. A Wikipedia possui definições formall e uma abordagem mais matemática.
Lembre-se de que o uso do sinal de igual em e similares é um nome impróprio. A rigor, é um conjunto de funções da variável , e devemos escrever .O ( f ( n ) ) n T ∈ O ( f )T( n ) = O ( f( N ) )T(n)=O(f(n))O ( f( N ) )O(f(n))nnT∈ O ( f)T∈O(f)
Exemplo: alguns algoritmos de classificação
Como isso é bastante seco, deixe-me dar um exemplo. A maioria dos algoritmos de classificação possui um tempo de execução quadrático no pior caso, ou seja, para uma entrada do tamanho , o tempo de execução do algoritmo é . Por exemplo, a classificação de seleção tem um tempo de execução , porque a seleção do ésimo elemento requer comparações , para um total de comparações. De fato, o número de comparações é sempre exatamente , que cresce como . Portanto, podemos ser mais precisos sobre a complexidade temporal da classificação: é Θ ( n 2 ) .O ( n 2 ) O ( n 2 ) k n - k n ( n - 1 ) / 2 n ( n - 1 ) / 2 n 2nnO ( n2)O(n2)O ( n2)O(n2)kkn - kn−kn ( n - 1 ) / 2n(n−1)/2n ( n - 1 ) / 2n(n−1)/2n2n2Θ ( n2)Θ(n2)
Agora faça a classificação por mesclagem . A classificação de mesclagem também é quadrática ( ). Isso é verdade, mas não muito preciso. A classificação de mesclagem na verdade tem um tempo de execução de O ( nO ( n2)O(n2) no pior dos casos. Como a classificação por seleção, o fluxo de trabalho da classificação por mesclagem é essencialmente independente da forma da entrada e seu tempo de execução é sempre nO ( nl g ( n ) )O(nlg(n)) até um fator multiplicativo constante, ou seja, é.nl g (n)nlg(n)Θ ( nl g ( n ) )Θ(nlg(n))
Em seguida, considere o quicksort . Quicksort é mais complexo. Certamente é . Além disso, o pior caso de quicksort é quadrático: o pior caso é . No entanto, o melhor caso de quicksort (quando a entrada já está classificada) é linear: o melhor que podemos dizer para um limite inferior ao quicksort em geral é . Não repetirei a prova aqui, mas a complexidade média do quicksort (a média obtida de todas as permutações possíveis da entrada) é .Θ ( n 2 ) Ω ( n ) Θ ( nO ( n2)O(n2)Θ ( n2)Θ(n2)Ω ( n )Ω(n)Θ ( nl g ( n ) )Θ(nlg(n))
Há resultados gerais sobre a complexidade dos algoritmos de classificação em configurações comuns. Suponha que um algoritmo de classificação possa comparar apenas dois elementos por vez, com um resultado sim ou não ( ou x > y ). Então é óbvio que o tempo de execução de qualquer algoritmo de classificação é sempre Ω ( n ) (onde n é o número de elementos a serem classificados), porque o algoritmo precisa comparar todos os elementos pelo menos uma vez para saber onde ele se encaixará. Esse limite inferior pode ser atingido, por exemplo, se a entrada já estiver classificada e o algoritmo apenas comparar cada elemento com o próximo e mantê-los em ordem (ou seja, n - 1x ≤ yx≤yx > yx>yΩ ( n )Ω(n)nnn - 1n−1comparações). O que é menos óbvio é que o tempo máximo de execução é necessariamente . É possível que o algoritmo às vezes faça menos comparações, mas deve haver um K constante, demodo que, para qualquer tamanho de entrada n , haja pelo menos uma entrada na qual o algoritmo faça mais do quecomparaçõesde K n l g ( n ) . A idéia da prova é construir a árvore de decisão do algoritmo, ou seja, seguir as decisões que o algoritmo toma do resultado de cada comparação. Como cada comparação retorna um resultado sim ou não, a árvore de decisão é uma árvore binária. Existem n !Ω ( nl g ( n ) )Ω(nlg(n))KKnnKn l g ( n )Knlg(n)n !n!possíveis permutações da entrada, e o algoritmo precisa distinguir entre todas elas; portanto, o tamanho da árvore de decisão é . Como a árvore é uma árvore binária, é necessária uma profundidade de Θ ( l g ( n ! ) ) = Θ ( nn !n! para ajustar todos esses nós. A profundidade é o número máximo de decisões que o algoritmo toma, portanto, a execução do algoritmo envolve pelo menos tantas comparações: o tempo máximo de execução é Ω ( nΘ ( l g ( n ! ) ) = Θ ( nl g ( n ) )Θ(lg(n!))=Θ(nlg(n)) .Ω ( nl g ( n ) )Ω(nlg(n))
¹ Ou outro consumo de recursos, como espaço na memória. Nesta resposta, considero apenas o tempo de execução.
"No entanto, o melhor caso de quicksort (quando a entrada já está classificada) é linear" este é o pior caso !!
@ user5507: Na verdade, isso depende da estratégia de pivô. Se o primeiro (ou último) elemento for escolhido como pivô, você estará certo; mas se você escolher o elemento do meio ou a mediana da primeira, do meio e do último, a entrada classificada será o melhor caso.
— chirlu
"O pequeno o e ω são usados ​​com muito menos frequência na análise de complexidade." Isso não é verdade na análise de complexidade espacial. Na análise da complexidade do tempo, você normalmente usa o e ω ao contar operações específicas (comparações, pesquisas de disco, falhas de cache, o que você tem). Mas como você sempre pode esperar e comprar um computador mais rápido, o "tempo na parede" é sempre "um fator constante", então o grande O é muito mais comum. Na análise espacial, geralmente existem limites inferiores rígidos por causa da teoria da informação, por isso é extremamente comum ver o tamanho relatado como "bits f (n) + o (f (n))" em que f (n) é o limite inferior.
Enquanto penso nisso: se f (n) é um limite inferior teórico do tamanho de alguma estrutura de dados, então um que usa f (n) + O (1) (sobrecarga constante) é chamado "implícito", um que usa f (n) + O (f (n)) (sobrecarga relativa constante) é chamado de "compacto", e aquele que usa f (n) + o (f (n)) (a sobrecarga relativa se torna eventualmente insignificante) é chamado de "sucinto" " Bons termos para saber se você precisa trabalhar nesse espaço.
OOΩΩΘΘΘΘ
"Tipicamente"? Eles podem ser usados ​​para outra coisa?
P=DTime(nO(1))P=DTime(nO(1))f=O(g)f=O(g)ff
P=DTime(nO(1))P=DTime(nO(1))P=DTime(nΘ(1))P=DTime(nΘ(1))
@ Jeff, eu penso nisso como uma igualdade entre conjuntos de funções, mas você está certo, também podemos pensar nisso como um limite superior em um sentido mais geral.
P≠DTIME(nΘ(1))P≠DTIME(nΘ(1))DTIME(Θ(nlogn))⊂PDTIME(Θ(nlog⁡n))⊂PDTIME(Θ(nlogn))∩DTIME(nΘ(1))=∅DTIME(Θ(nlog⁡n))∩DTIME(nΘ(1))=∅