Questões de Concurso

Pedro adotou o algoritmo apresentado a seguir para ordenar um vetor de inteiros V, com índices variando de 1 até n.

Para K de 2 até n faça:
X <- V[K]
W <- (K – 1)
Enquanto W > 0 e V[W] > X faça:
V[W+1] <- V[W]
W <- (W-1)
Fim Enquanto
V[W+1] <- X
Fim Para

O algoritmo utilizado por Pedro foi o:

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 é:

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 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:

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: