Exercício - Complexidade de Algoritmos - Estrutura de Dados 2022 1

Defina qual é a complexidade do algoritmo abaixo e explique o raciocínio: def buscaSequencial(lista, chave): indice = 0 for número in lista: if número == chave: return indice indice = indice + 1 return -1 Diga qual a complexidade do algoritmo abaixo e explique, textualmente, como chegou nessa conclusão: def fat(n): fact = 1 for i in range(1,n+1): fact = fact * i return fact Para o algoritmo abaixo, calcule a complexidade e descreva o cálculo para chegar nessa conclusão: def sort(array): for p in range(0, len(array)): current_element = array[p] while p > 0 and array[p - 1] > current_element: array[p] = array[p - 1] p -= 1 array[p] = current_element Esse algoritmo de ordenação, para cada posição p do array, verifica da posição p até 0 se o elemento da posição p é maior que o atual, fazendo trocas, levando sempre o maior número para a posição p. Deixando de lado os custos constantes, o primeiro laço executa n vezes, sendo n o tamanho do array. Em seguida para cada posição do array, percorremos de p até 0, que no pior caso(quando array[p-1] > current_element e p for a última posição do vetor( vai ser executado n vezes também, pois caminha o array todo, de p até 0). Um detalhe importante é que o laço while só é executado quando (p > 0 e quando array[p-1] > current_element ) então, para as iterações que a condição não é válida, ele não é computado. Mas, como a complexidade é uma representação geral para o código, temos (O(n) (primeiro laço) * (O(n-1) (n-1 pois quando p == 0 ele não é computado). Podemos escrever essa complexidade como (O(n²)), uma vez que n² > n * (n-1).