Algoritmos e Estrutura de Dados · CESGRANRIO · 2024 | Questão sqc-cg022647

Algoritmos e Estrutura de DadosAlgoritmos

Código: cg022647
Banca: CESGRANRIO
Órgão: IPEA
Ano: 2024
Nível: Superior

Cargo: Técnico de Planejamento e Pesquisa -Ciência de Dados

A biblioteca Scikit-Learn emprega o algoritmo Classification And Regression Tree (CART) para treinar Árvores de Decisão. O algoritmo CART baseia-se na recursividade e na estratégia de divisão binária para construir uma árvore de decisão. Inicialmente, a árvore é representada por um único nó, que contém todos os dados de treinamento. A cada passo, o algoritmo busca a melhor maneira de dividir o conjunto de dados. A recursividade continua até que uma condição de parada seja atendida, como atingir uma profundidade máxima da árvore. Uma vez construída a árvore, a fase de predição ocorre ao percorrer a estrutura da árvore de acordo com as condições estabelecidas nos nós, levando a uma predição (inferência) para uma determinada entrada.Considerando-se que n corresponde ao número de features e m ao número de instâncias, qual é a complexidade computacional assintótica de predição para árvores de decisão treinadas com o algoritmo CART?

AO(m)
BO(m²)
CO(n × m log(m))
DO(n² × m log(m))
EO(log₂ (m))

Revelar gabarito e comentário

GabaritoE — O(log₂ (m))

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Complexidade de predição em árvores de decisão (CART)

Gabarito: letra E. A complexidade assintótica de predição em árvores de decisão treinadas com o algoritmo CART é O(log₂(m)), onde m é o número de instâncias de treinamento. Isso porque, durante a inferência, percorre-se a árvore da raiz até uma folha, e, em árvores balanceadas, a altura é proporcional ao logaritmo do número de elementos. O número de features (n) não afeta o percurso, pois cada nó realiza uma comparação simples (custo O(1)).

A pergunta explora a diferença entre a complexidade de treinamento (que depende de n e m) e a de predição. No CART, o treinamento pode ser O(n × m²) no pior caso, mas a predição é barata. A banca testa se o candidato sabe que, uma vez construída a árvore, a busca é logarítmica em relação ao número de instâncias.

Alternativa A — ❌ Incorreta

Afirma O(m), que seria a complexidade de percorrer todos os elementos (como em uma busca linear). Em árvores degeneradas (não balanceadas) a altura pode ser O(m), mas o CART geralmente produz árvores aproximadamente balanceadas; a complexidade esperada é logarítmica, não linear.

Alternativa B — ❌ Incorreta

O(m²) não corresponde ao custo de predição. Essa complexidade poderia aparecer em algoritmos de treinamento (como o CART original O(n × m²)), mas não na inferência.

Alternativa C — ❌ Incorreta

O(n × m log(m)) mistura n e m; a predição não percorre todas as features nem todos os dados. Cada nó testa uma única feature, independente de n.

Alternativa D — ❌ Incorreta

O(n² × m log(m)) é ainda mais distante; o quadrado de n não se aplica à predição.

Alternativa E — ✅ Correta ⟵ GABARITO

A predição em uma árvore de decisão balanceada consiste em descer da raiz até uma folha. A altura da árvore, em termos assintóticos, é O(log₂(m)), pois cada divisão binária reduz o conjunto de dados aproximadamente pela metade. Assim, o custo é logarítmico no número de instâncias.

PEGA ESSA DICA!

Para provas de algoritmos, lembre-se: treinamento de árvores de decisão pode ser caro (O(n × m²) no pior caso do CART), mas a predição é rápida, O(log₂(m)). Questões como essa testam esse contraste.

Gabarito: letra E.

Link permanente: /questoes/cg022647