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
  1. Qual é o melhor caso? Bem, se o array que fornecemos tiver 0 como o primeiro valor, levará um tempo constante: Ω (1)
  2. 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!

  1. pegue
  2. retirar
  3. 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/