Explicação de grande teta e notação assintótica
Big Omega nos diz o limite inferior do tempo de execução de uma função e Big O nos diz o limite superior.
Muitas vezes, eles são diferentes e não podemos garantir o tempo de execução - ele varia entre os dois limites e as entradas. Mas o que acontece quando eles são iguais? Então, podemos dar um limite theta (Θ) - nossa função será executada nesse tempo, não importa qual entrada dermos a ela.
Em geral, sempre queremos dar um limite theta, se possível, porque é o limite mais preciso e restrito. Se não podemos dar um limite teta, a próxima melhor coisa é o limite O mais estreito possível.
Tome, por exemplo, uma função que pesquisa uma matriz para o valor 0:
def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false- Qual é o melhor caso? Bem, se o array que fornecemos tiver 0 como o primeiro valor, levará um tempo constante: Ω (1)
- Qual é o pior caso? Se a matriz não contiver 0, teremos iterado por toda a matriz: O (n)
Demos a ele um limite de ômega e O, então e quanto a teta? Não podemos dar um! Dependendo da matriz que fornecemos, o tempo de execução estará em algum lugar entre constante e linear.
Vamos mudar nosso código um pouco.
def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)Você consegue pensar no melhor e no pior caso ?? Eu não posso! Não importa o array que fornecermos, temos que iterar por meio de cada valor no array. Portanto, a função levará PELO MENOS n tempo (Ω (n)), mas também sabemos que não demorará mais do que n tempo (O (n)). O que isto significa? Nossa função levará exatamente n tempo: Θ (n).
Se os limites são confusos, pense assim. Temos 2 números, x e y. Temos que x <= y e y <= x. Se x for menor ou igual ay, ey for menor ou igual a x, então x deve ser igual a y!
Se você estiver familiarizado com listas vinculadas, teste-se e pense nos tempos de execução de cada uma dessas funções!
- pegue
- retirar
- adicionar
As coisas ficam ainda mais interessantes quando você considera uma lista duplamente vinculada!
Notação Assintótica
Como medimos o valor de desempenho dos algoritmos?
Considere como o tempo é um de nossos recursos mais valiosos. Na computação, podemos medir o desempenho com a quantidade de tempo que um processo leva para ser concluído. Se os dados processados por dois algoritmos forem iguais, podemos decidir sobre a melhor implementação para resolver um problema.
Fazemos isso definindo os limites matemáticos de um algoritmo. Estes são big-O, big-omega e big-theta, ou as notações assintóticas de um algoritmo. Em um gráfico, o big-O seria o máximo que um algoritmo poderia levar para qualquer conjunto de dados, ou o “limite superior”. Big-omega é como o oposto de big-O, o “limite inferior”. É aí que o algoritmo atinge sua velocidade máxima para qualquer conjunto de dados. Big theta é o valor de desempenho exato do algoritmo ou um intervalo útil entre os limites superior e inferior estreitos.
Alguns exemplos:
- “A entrega estará lá dentro de sua vida.” (big-O, limite superior)
- "Posso pagar a você pelo menos um dólar." (grande-ômega, limite inferior)
- “A máxima hoje será de 25ºC e a mínima de 19ºC.” (teta grande, estreito)
- “É uma caminhada de um quilômetro até a praia.” (grande-teta, exato)
Mais Informações:
//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/
