Questão 2524432

• Banca: FCC
• Órgão: DPE-RS
• Ano: 2017
• Provas: FCC - 2017 - DPE-RS - Analista - Desenvolvimento de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Um Analista, estudando a complexidade de algoritmos de busca linear (ou sequencial), concluiu corretamente que no pior caso, considerando um vetor de n elementos, este tipo de algoritmo tem complexidade

• A. O(n).
• B. O(log₂n-1).
• C. O(√n).
• D. O(log2n).
• E. O(log₂n² ).

Gabarito: A

Comentários

• O gabarito é a letra A. 

   

  A complexidade do algoritmo de busca linear é da ordem de Θ(n), em que n é o tamanho do vetor de busca. 

• A ideia aqui é a busca retornar n comparações sem sucesso para informar que o registro não foi encontrado. Esta é a ideia de pior caso para a complexidade de busca linear.

• Busca sequencial : : definição ==> percorre todos os elementos até encontrar, todos os n elementos, entao ordem Θ(n), letra A

• Complexidade da busca binária: O(log N)

  Complexidade da busca sequencial: O(N)

• Força Guerreiro!!!!!!