Ciência de Dados - Complexidade de Algoritmos

Qual é a complexidade de tempo consumida para a geração de uma solução no algoritmo descrito?

• O(n^2)

• O(n)

• O(n^3)

• O(n^4)

Quantas soluções únicas existem para tabuleiros de tamanho 8x8?

• 6

• 12

• 92

• 46

Qual é a estratégia utilizada pelo algoritmo randomizado de Monte Carlo para alocar damas em cada linha?

• Alocação sequencial da primeira posição livre encontrada

• Alocação baseada na ordem lexicográfica crescente

• Escolha aleatória entre todas as posições livres

• Escolha baseada na posição das damas alocadas anteriormente

Qual é a complexidade de espaço do algoritmo randomizado de Monte Carlo descrito?

• O(n)

• O(n^2)

• O(n^3)

• O(n^4)

O que acontece se não houver posição livre na linha i durante a execução do algoritmo de Monte Carlo?

• O algoritmo reporta insucesso e encerra sem retrocesso

• O algoritmo retrocede para a última posição livre encontrada

• O algoritmo reinicia a execução desde o início

• O algoritmo tenta alocar a dama em outra linha

Qual é a principal diferença entre o algoritmo randomizado de Monte Carlo e o determinístico de retrocesso?

• O algoritmo randomizado não permite retrocessos

• O algoritmo determinístico não utiliza sorteio

• O algoritmo randomizado não gera soluções únicas

• O algoritmo determinístico não reporta insucesso

Como o algoritmo randomizado de Monte Carlo determina as posições livres de uma certa linha i?

• Pela alocação sequencial das damas

• Através da função LIVRE.i; j /

• Por sorteio entre todas as posições possíveis

• Com base na ordem lexicográfica crescente

Qual é a complexidade de tempo para a geração de uma solução no algoritmo randomizado de Monte Carlo?

• O(n^4)

• O(n^3)

• O(n^2)

• O(n)

O que o algoritmo randomizado de Monte Carlo faz em caso de insucesso na alocação de damas?

• Encerra a execução sem retrocesso

• Reporta insucesso e tenta novamente

• Reinicia a execução desde o início

• Retrocede para a última alocação bem sucedida

Qual é a complexidade de espaço do algoritmo descrito no texto?

• O(n^2)

• O(n^4)

• O(n)

• O(n^3)