Questão
ID 3139682Disciplina: Tecnologia da Informação
Assuntos: Complexidade de Algoritmos (Big-O, P x NP)
Ano: 2023 Banca: INEP ENEM - Instituto Nacional de Estudos e Pesquisas Educacionais Anísio Teixeira Órgão: Exame Nacional de Desempenho dos Estudantes
Considere que seja necessário utilizar um algoritmo para resolver um determinado problema. Diante disso, vários profissionais propõem diferentes soluções. Nesse cenário, um possível critério para a escolha do algoritmo é que ele otimize a necessidade de recursos computacionais, como, por exemplo, de tempo de processamento.
Sabe-se que a notação O-grande (big O notation) é usada para classificar a resposta de algoritmos à variação no tamanho dos dados de entrada. Por exemplo, um algoritmo será classificado como O(N) se, ao receber um vetor de tamanho N, tiver tempo de processamento proporcional a N. Outro algoritmo será classificado como O(N2) se o tempo de processamento variar proporcionalmente a N2.
A seguir, são reproduzidos dois algoritmos como funções na linguagem C:
A1: retorna 1 se um dado elemento está presente em um vetor de tamanho N e retorna 0, caso contrário.
A2: soma matriz m1 com matriz m2 e armazena resultado na matriz m3, matrizes com N linhas e N colunas.
Diante dessas informações, é correto afirmar que as classificações O-grande dos algoritmos A1 e A2 são, respectivamente,