Questões de Concurso Público CVM 2024 para Analista CVM - Perfil 8 - TI / Sistemas e Desenvolvimento - Tarde

O analista Joaquim precisou ordenar um array com N elementos. Para economizar tempo, Joaquim optou por usar um algoritmo já disponível na biblioteca de ordenação. A biblioteca contém as implementações originais dos algoritmos Quicksort, Selection Sort, Insertion Sort, Merge Sort e Heap Sort. O analista escolheu o algoritmo que, no pior caso, apresenta uma relação quadrática entre a quantidade de operações necessárias para a ordenação e o número de elementos do array. No caso médio, a quantidade de operações necessárias se aproxima de N multiplicado por um logaritmo de N.

Joaquim escolheu o algoritmo de ordenação:

O analista José precisa escolher entre dois algoritmos, Abusca e Cbusca. José sabe que, sendo N o tamanho da entrada do algoritmo, Abusca requer 2^N + log₂(N) operações para ser executado. Já o Cbusca requer N⁴ + N operações para ser executado. José determinou, na notação O-grande, a complexidade de tempo no pior caso para cada algoritmo e, por fim, deve escolher o algoritmo que apresenta a menor ordem de complexidade no pior caso.

José deve escolher o algoritmo:

A analista Ana precisou implementar rapidamente uma função hash denominada AHash. A AHash deve determinar um valor numérico entre 0 e 5 para uma chave de entrada. Ana optou por implementar em AHash o método de hashing denominado Método da Divisão. Para compatibilizar possíveis chaves alfanuméricas com o Método da Divisão, Ana implementou um dicionário que atribui a cada caracter um valor numérico. Internamente, a AHash utiliza como chave o produto dos números correspondentes aos caracteres da chave original.
Sabendo que os caracteres C, V e M correspondem, respectivamente, aos números 67, 86 e 77, a AHash retornará para a chave “CVM”:

Diversas operações matemáticas podem ser implementadas de forma recursiva, como no algoritmo seguinte.

Função X (J: inteiro, K: inteiro)
Início
Se J < K Então
Retorne J
Senão
Retorne X (J-K, K)
Fim


Considerando o domínio dos inteiros positivos, a função terá como resultado o(a):

O cálculo da complexidade computacional é essencial para verificar a viabilidade do algoritmo. Observe o código a seguir, em Python, para o problema da torre de Hanoi.

def hanoi(n, o, d, a):
if n==1:
print("D1 de "+o+" p/ "+d)
else:
hanoi(n-1, o, a, d)
print("D"+str(n)+" de "+o+" p/ "+d)
hanoi(n-1, a, d, o)

A complexidade desse algoritmo no pior caso é: