Ed
há 3 semanas
Vamos analisar cada afirmativa: I. A função T(n) é igual a Θ(1) para o caso base da recorrência do tempo de execução que equivale a pesquisar em um vetor com um elemento. Verdadeiro, pois quando o vetor tem apenas um elemento, a pesquisa é feita em tempo constante. II. A função T(n) para o caso recorrente é igual a T(n/2) + Θ(1), que envolve a divisão do vetor em duas partes e depois o processamento das partes. Falso, a pesquisa binária não divide o vetor em duas partes, mas sim descarta uma metade a cada chamada recursiva. A relação correta seria T(n) = T(n/2) + Θ(1). III. Ao realizar a soma de todos os tempos de execução em um nível da árvore de execução, tem-se uma expressão no formato Θ(n). Verdadeiro, pois em cada nível da árvore de recursão, a soma dos tempos de execução é proporcional ao número de elementos que estão sendo processados. IV. A soma na vertical leva em consideração a altura da árvore de recursão e esta altura da árvore é log(n). Verdadeiro, a altura da árvore de recursão da pesquisa binária é logarítmica em relação ao número de elementos. Com base nas análises: - I é verdadeiro. - II é falso. - III é verdadeiro. - IV é verdadeiro. Portanto, a alternativa que contém todos os itens verdadeiros é: e) I, II e III, apenas.