Como já foi dito, análise de algoritmos tem como objetivo verificar e estudar um algoritmo, de forma a encontrar situações em que ele agirá da pior ou pior forma (alé do caso médio) e assim definirmos a complexidade do mesmo, podendo indicar o grau de qualidade do mesmo. Porém, essa análise pode ser expandida no quesito de comparação com outros algoritmos, afinal, é muito comum no mundo da programação, existirem N diferentes códigos e algoritmos que a pesar da sua diferença de script, realizam um mesmo objetivo. Diante disso, a ordem de complexidade tem como objetivo comparar dois ou mais algoritmos, de forma a identificar os casos em que um domina o outro (em que o algoritmo é melhor que outro).
Essa questão se aplica e se firma bastante sobre o quesito de tempo de execução que o algoitmo levaá para sua execução, a partir de uma variável de entrada N. Já estudamos também que ao bater o olho em um algoritmo, podemos definir logo de cara que aqueles que apresentem uma análise assintóica com variáveis superiores, são mais exigentes que os demais, como por exemplo: N^2 > N ou N^n > N^n. Diante disso, podemos julgar um algoritmo mais "pesado" e trabalhoso do que outro a partir de suan apresentação de variaveis. Como no exemplo:
Tendo 2 algoritmos A e B para a solução de um problema. Se a complexidade de um é expressa por Fa(n) = n^2 e Fb(n) = 100n, qual o mais custoso?
Aqui podemos peceber que independente do valor de n, a primeira função terá um desempenho muito mais custoso em algum momento de seu intervalo, de forma escalar em um gráfico. Aconselhando a isso, é indicado o site https://www.wolframalpha.com/input/?i=plot+x+%2C+x%5E2, onde é possível colocar várias funções e observar o seu comportamento, nesse site, as funções são postas em um gráfico e podemos observer em que instante de variável uma irá se opor a outra. Para isso, devemos inserir dados como:
plot função 1, função 2, x=0 to valor máximo de alcance
Assim podemos ter uma visão bem melhor e real do comportamento e sobreposição de 2 ou mais funções. Essa quesão de dominação de uma função sobre outra, é chamada de dominação assintótica e é um argumento muito usado nas análises de algoritmos e comparações de algoritmos. Logo, no caso do exemplo citado acima, podemos dizer que a primeira função domina a segunda, devido ao seu maior custo de execução. Para que isso esteja fixo em seus estudos, seguiremos com outro exemplo de dominação entre2 funções:
Dadas as funções:
𝑓(𝑛) = 5 ∗ 𝑛^2 + 10
g(𝑛) = 0.5 ∗ 𝑛^3 − 20
Qual função domina a outra?
Aqui, logo de cara, podemos indicar que em algum momento de variável, a função g(n) possui dominação, devido a sua característica de custo n^3, ou seja, em dado instante, colocado em um gráfico, a primeira função terá um custo exponencialmente maior do que a outra.
Diante destas questões, entraremos nas
Ou também chamado de Big-O, onde define um limite superior para a função, por um fator constane, ou seja, indica de forma direta que uma função será sempre dominada por outra função.
Sua fórmula de complexidade é: 𝑓(𝑛) = Ο(𝑔(𝑛)), representada como a função F(n) pertence ao conjunto em que a função G(n) domina, ou seja, G(n) domina F(n) em algum momento de instante de execução.
𝑔(𝑛) = 𝑛^2 + 1 -> Ο(𝑓(𝑛) = 𝑛^2)
𝑔(𝑛) = 𝑛^2 + 1 -> Ο(𝑛^2)
𝑔(𝑛) = 𝑛^3 + 5𝑛^2 − 3 -> Ο(𝑛^3)
𝑔(𝑛) = 517 -> Ο(1)
É bom ressaltar que 𝑔(𝑛) = n^2 será sempre O(n^3), de O(n^4) e assim por diante, devido a grandeza exponencial.
A notação ômega define um limite inferior para a função, por um fato contante, ou seja, indica de forma direta que uma função será sempre domimada por outra função (o exato contrário do ômicron).
Sua fórmula de complexidade é: 𝑓(𝑛) = Ω(𝑔(𝑛)), representada como a função F(n) pertence ao conjunto dominante da função G(n) , ou seja, F(n) domina G(n) em algum momento de instante de execução.
𝑔(𝑛) = 𝑛^2 -> Ω(𝑓(𝑛) = 𝑛^2 + 1)
𝑔(𝑛) = 𝑛^2 -> Ω(𝑛^2 + 1)
𝑔(𝑛) = 𝑛^3 -> Ω(𝑛^3 + 5𝑛^2 − 3)
𝑔(𝑛) = 1 -> Ω(517)
É bom ressaltar que se 𝑔(𝑛) = 𝑛^2 é Ω(𝑓(𝑛) = 𝑛), logo 𝑓(𝑛) = 𝑛 é O(𝑔(𝑛) = 𝑛^2)
A notação teta limita a função por fatores constantes, ou seja, indica que uma função pode dominar a outra. Porém, em dado momento, ocorrerá uma inversão e ela será dominada.
Sua fórmula de complexidade é: 𝑓(𝑛) = Θ(𝑔(𝑛)), representada como a função F(n) domina G(n) , Porém, G(n) dominará F(n) em algum momento de instante de execução.