Complexidade de Tempo de Algoritmos: Teoria da Computação 20221

Complexidade de Tempo de Algoritmos Parte 2 Teoria da Computação 20221 Para fazer nalisar o tempo gasto na execução da função somatória chegamos à seguinte tabela Note que para determinar a quantidade de execuções da linhas 3 tivemos um pouco de dificuldade para chegar aos valores exatos No entanto com o uso da notação assintótica essa dificuldade desaparece Refinando um pouco mais os valores da tabela Calculando a complexidade de tempo Tn T n O1O1OnOnOnO1 On O algoritmo somatória gasta tempo linear tanto no pior quanto no melhor caso No pior caso o tempo é Tn On No melhor caso o tempo é Tn n Como tanto no pior caso como no melhor obtivemos On dizemos que Tn n Ou seja Notação O descreve o pior caso Notação descreve o melhor caso Notação usada quando o pior caso é igual ao melhor caso Assim a notação O define um limite superior fn On 3 indica que para valores grandes de n uma função cúbica limita superiormente fn Exercício Verdadeiro ou falso x 2 7 Ox x 2 7 O1 x 2 7 Ox 2 x 2 7 Ox 3 A notação define um limite inferior Exercício Verdadeiro ou falso x 2 7 x x 2 7 1 x 2 7 x 2 x 2 7 x 3 Qual é a complexidade de tempo dos seguintes algoritmos melhor pior caso caso Busca sequencial Busca binária bubblesort selectionsort insertionsort mergesort quicksort Perguntas Qualis desses algoritmos é On 4 Qualis desses algoritmos é On Qualis desses algoritmos é n Teoria da Computação 20221