Questão 33 — Análise de Complexidade — Notação O (Algoritmos e Estruturas de Dados) — Serviço de Seleção do Pessoal da Marinha (SSPM) · Marinha do Brasil 2023

Algoritmos e Estruturas de Dados Análise de Complexidade — Notação O

Serviço de Seleção do Pessoal da Marinha (SSPM) 2023

Marinha do Brasil · Quadro Técnico do Corpo Auxiliar da Marinha (CP-T) — Informática · Caderno Amarela

Gabarito disponível

Referente à notação O, considere as funções apresentadas abaixo e assinale a opção que apresenta, respectivamente, as funções na referida notação.

I- 6 x 2ⁿ + 5 x n¹⁰
II- log n + 3 x log n² + 4 x log² n
III- 404
IV- n² + 2n + 1

Selecione uma alternativa A) O(2ⁿ); O(log² n); O(1); O(n²) B) O(n¹⁰); O(log n²); O(404); O([n+1]²) C) O(2ⁿ); O(log n²); O(1); O(n²) D) O(n¹⁰); O(log² n); O(404); 2O(n+1) E) O(2ⁿ); O(log² n); O(c); O(n²+ 2n)

Resolução comentada

Dominam os termos 2ⁿ, log² n, constante e n².

I) 2ⁿ cresce mais que n¹⁰, logo O(2ⁿ). II) log n² = 2 log n, e o termo dominante é log² n, logo O(log² n). III) Uma constante é O(1). IV) O termo dominante é n², logo O(n²).

Análise das alternativas

B e D) Consideram n¹⁰ dominante em I, e D ainda usa '2O(n+1)' em IV. C) Mantém log n² em II, sem apontar o termo dominante log² n. E) Usa O(c) e O(n²+2n), que não são formas simplificadas.

Referência: SZWARCFITER, J. L.; MARKENZON, L. Estruturas de Dados e seus Algoritmos; análise de algoritmos.

Resolução comentada do VaiConcursos.