Questão 705184

• Banca: UPENET/IAUPE
• Órgão: JUCEPE
• Ano: 2012
• Provas: UPENET - 2012 - JUCEPE - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

 Sabe-se que o valor de um dado armazenado com um tipo inteiro é o próprio número inteiro na base binária que forma uma cadeia de bits. A largura (ou precisão) de um tipo inteiro é a quantidade de bits disponíveis para a sua representação. O algoritmo abaixo avalia a quantidade de bits necessária para armazenar um inteiro. Determine sua complexidade. 

int numero_bits (int x) {
               int bits = 0;
               while (x != 0) { bits++; x=x/2; }
               return bits;
} 

• A. O(log₂x)
• B. O(log₁₀x)
• C. O(x)
• D. O(x/2)
• E. O(x² )

Gabarito: A

Comentários

• x=x/2 --> Logaritmico

•  
  Logaritmo - O(log n) : Ocorre tipicamente em algoritmos que dividem problemas em problemas menores. Ex: Algoritmo de busca binária, buscar um elemento em um vetor ordenado;