084-2005

MO640 - Questão para a prova oral
Número: 084
Enunciado:
Qual das afirmações abaixo é INCORRETA com relação ao algoritmo de ordenação por intercâmbio de blocos, proposto por Christie, no artigo Sorting permutations by block-interchanges:

1. O algoritmo possui complexidade O(n²).
2. O algoritmo se basea numa operação chamada de minimal block-interchange que sempre remove 2 pontos de quebra.
3. O número de ciclos do grafo de ciclos (cycle graph) é sempre aumentado de 2 a cada operação de intercâmbio de blocos realizada pelo algoritmo.
4. O algoritmo possui fator de aproximação 2, já que é possível realizar operações de intercâmbio de blocos que removem até 4 pontos de quebra.
5. NDA

Autor(a): Marcelo de Almeida Oliveira