Complexidade de Tempo de Algoritmos - Teoria da Computacao 2021

Complexidade de Tempo de Algoritmos Teoria da Computação 2021 Uma forma comum de se analisar o desempenho de tempo de execução de um algoritmo é fazendo uma contagem do número de operações básicas necessárias para resolver um determinado problema Considerando que a execução de cada operação básica gasta tempo constante contando o total de operações básicas executadas dará uma estimativa do tempo de execução do algoritmo 1 Exemplo função somatoria Considere a seguinte função para somar os números de 1 até n considerando n 1 int somatoriaint n int result 0 int i 1 while i n result i i returnresult Para estimar o tempo gasto pela função somatoria devemos avaliar o tempo gasto em cada linha do seu código calcular quantas vezes cada linha é executada contabilizar o tempo total gasto na execução de cada linha e finalmente se o elemento buscado estiver na 1a posição do vetor pesquisada pelo algoritmo o tempo total de execução será constante pois serão executas uma quantidade fixa de operações básicas se o elemento buscado não ocorrer no vetor o desempenho do algoritmo dependerá do tamanho d o vetor pois quanto maior for o vetor maior será o tempo total gasto Normalmente enfatizamos duas situações usadas na análise do desempenho de algoritmos análise de melhor caso situação em que um algoritmo gasta o menor tempo possível em uma execução qualquer e análise de pior caso situação em que um algoritmo gasta o maior tempo possível em uma execução qualquer se o elemento buscado estiver na 1a posição do vetor pesquisada pelo algoritmo o tempo total de execução será constante pois serão executas uma quantidade fixa de operações básicas se o elemento buscado não ocorrer no vetor o desempenho do algoritmo dependerá do tamanho d o vetor pois quanto maior for o vetor maior será o tempo total gasto Normalmente enfatizamos duas situações usadas na análise do desempenho de algoritmos análise de melhor caso situação em que um algoritmo gasta o menor tempo possível em uma execução qualquer e análise de pior caso situação em que um algoritmo gasta o maior tempo possível em uma execução qualquer calcular o tempo total gasto com a função Para fazer tudo isto elaboramos a seguinte tabela com os detalhes anotados para cada linha de código Note que cada linha do código consiste de poucas operações básicas de um computador O tempo gasto em cada uma delas depende do computador onde é executada Para contornar esta dependência de máquina dizemos simplesmente que cada linha gasta tempo constante anotados com c 1 c 2 etc Para calcular o tempo total de execução da função basta somar os tempos totais de execução das linhas Tn 1 c 1 1 c 2 n1 c 3 n c 4 n c 5 1 c 6 Ou seja Tn n c 3 c 4 c 5 c 1 c 2 c 3 c 6 Como c 3 c 4 c 5 é uma constante que podemos chamar de a e c 1 c 2 c 3 c 6 também é uma constante que chamaremos de b o tempo total pode ser escrito como Tn a n b Assim descobrimos que o tempo gasto pela função somatoria depende do valor de n e que o total de tempo gasto varia como uma função linear de n 2 Análises de melhor e de pior caso Considerando por exemplo um algoritmo de busca sequencial de um elemento em um vetor é fácil perceber que Teoria da Computação 2021 3 Notação O O Grande Para tratar da análise de pior caso de um algoritmo usamos a notação O grande Dados um algoritmo e uma instância de tamanho n dizemos que um algoritmo é O 1 se gasta tempo constante para qualquer entrada de tamanho n O log 2 n se gasta tempo limitado por uma função logaritmica do tamanho da entrada O n se gasta tempo limitado por uma função linar do tamanho da entrada O nlog 2 n se gasta tempo limitado por uma função nlog 2 n do tamanho da entrada O n 2 se gasta tempo limitado por uma função quadrática do tamanho da entrada etc Ao fazer esta análise consideramos sempre que o tamanho da entrada é um valor n arbitrariamente grando ou como os teóricos de análise de algoritmos normalmente dizem assintoticamente tendendo ao infinito Por exemplo a soma de dois números do tipo int é O1 a busca binária é Olog 2 n a busca sequencial é O n a ordenação por seleção é On 2 o merge sort é Onlog 2 n Fazemos a comparação de algoritmos diferentes através da comparação das funções usadas para descrever o desempenho deles e usando a seguinte relação de comparação de desempenho O1 Olog 2 n On Onlog 2 n On 2 A notação O pode parecer estranha para muitos mas ela é bastante útil Por exemplo muitos erram na quantidade de vezes que a linha 3 do código de somatoria é executado Será que é n1 Ou será n1 Ou será n A resposta correta é n1 pois devemos contabilizar na execução do algoritmo o teste realizado quando i vale n1 o que faz com que o comando repetitivo seja encerrado No entanto para efeito do cálculo de complexidade assintótica este detalhe é irrelevante O que interessa é que esta linha é executada uma quantidade linear de vezes Assim podemos refazer a tabela da forma Ao refazer os cálculos de complexidade os resultados obtidos serão os mesmos Calculeos Teoria da Computação 2021