Please enable JavaScript.
Coggle requires JavaScript to display documents.
Análise de algoritmos, Vinícius Lima Sá de Melo - vlsm - Coggle Diagram
Análise de algoritmos
Avalia dois aspectos, tempo de execução e memória ocupada
-
-
Tamanho da entrada depende da magnitude do problema, ex: um problema de ver a quantidade de caracteres a entrada se baseia nas letras
Notações
O (big oh)
Representa funções da mesma ordem de grandeza ou menor, ex: n² e n + 1
If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}).
Ω(big omega)
Ordem de grandeza maior ou igual, Ex: n³ e n²
θ(big theta)
Ordem de grandeza igual, Ex: n² e n² + 2
-
-
-
Para analisar algoritmos não recursivos, primeiro definimos o parâmetro para tamanho da entrada, depois a operação principal do algoritmo, analisar o número de repetições, baseado nos casos e depois manipular algebricamente para obter a menor fórmula
-