A respeito da notação Big O, que designa a complexidade de algoritmos, avalie as afirmativas a seguir.
É correto o que se afirma em:
I – Algoritmos de complexidade O(log n), ou complexidade logarítmica, são aqueles em que o número de instruções executadas cresce muito rapidamente para um pequeno número de dados.
II – Algoritmos de complexidade O(n), ou complexidade linear, são aqueles em que um pequeno trabalho é realizado sobre cada elemento de entrada.
III – Algoritmos de complexidade O(1), ou complexidade constante, são aqueles em que as instruções do algoritmo são executadas um número fixo de vezes.
A) I, apenas.
B) II, apenas.
C) I e III, apenas.
D) II e III, apenas.
E) I, II e III.

Question

A respeito da notação Big O, que designa a complexidade de algoritmos, avalie as afirmativas a seguir.
É correto o que se afirma em:
I – Algoritmos...

Ed · Answer

Vamos analisar cada afirmativa:

I – Algoritmos de complexidade O(log n), ou complexidade logarítmica, são aqueles em que o número de instruções executadas cresce muito rapidamente para um pequeno número de dados. Falso. Na verdade, a complexidade logarítmica significa que o número de instruções executadas cresce lentamente à medida que o tamanho dos dados aumenta. Um exemplo típico é a busca binária.

II – Algoritmos de complexidade O(n), ou complexidade linear, são aqueles em que um pequeno trabalho é realizado sobre cada elemento de entrada. Verdadeiro. Isso está correto, pois em algoritmos de complexidade linear, o tempo de execução cresce proporcionalmente ao número de elementos de entrada.

III – Algoritmos de complexidade O(1), ou complexidade constante, são aqueles em que as instruções do algoritmo são executadas um número fixo de vezes. Verdadeiro. Isso está correto, pois a complexidade constante significa que o tempo de execução não depende do tamanho da entrada.

Agora, considerando as análises:

- O item I é falso.
- O item II é verdadeiro.
- O item III é verdadeiro.

Portanto, a alternativa que contém todos os itens verdadeiros é: D) II e III.

Teoria da Computação

Aspectos Teoricos

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Aspectos Teoricos

Na teoria da computação, a decidibilidade é um conceito fundamental que se refere à capacidade de resolver ou decidir um problema de forma algorítmica.
O que caracteriza um problema decidível na teoria da computação?

O problema da parada desempenha um papel central na teoria da computação, pois aborda a questão de decidir se um programa de computador irá parar ou entrar em um loop infinito.
Qual é a definição do problema da parada?

O próximo problema a ser solucionado é saber se dois AFDs são equivalentes, ou seja, se reconhecem a mesma linguagem.
Qual é a tarefa que deve ser realizada para determinar se dois AFDs são equivalentes?

Perceba que, conhecendo algum algoritmo de ordenação, o k‑ésimo menor elemento vai ocupar exatamente a posição k, resolvendo o problema da seleção.
Qual é o vetor B que deve ser obtido a partir do vetor A = (7,5,9,3,4,1) após a ordenação?

A redução por mapeamento de A para B é uma função computável f que mapeia instâncias de A para instâncias de B de forma que:
Se x é uma instância de A para a qual a resposta é sim, o que podemos afirmar sobre f(x)?

Em problemas decidíveis, existem aqueles que são tratáveis e os que não são tratáveis. Isso quer dizer que qualquer problema decidível exige o gasto de recursos como tempo e memória.
O que é tempo de execução?

Nesse caso, houve 16 movimentos do cabecote de leitura e gravação, portanto esse é o pior dos casos, logo o tempo de execução é 16.
Qual é o tempo de execução para a cadeia ω1 = 0011?

O comportamento assintótico refere-se à tendência de uma função ou processo matemático se aproximar de um limite ou padrão à medida que se estende ao infinito.
O que é notação O-grande (Big O)?

Esse tema certamente é o maior problema em aberto na ciência da computação e um dos maiores da matemática. É conhecido como P versus NP e sua resolução trará impactos profundos para a sociedade.
O que estabelece a questão P versus NP?

O problema de otimização é aquele no qual cada solução possível tem um valor associado e desejamos encontrar a melhor solução em relação a esse valor.
Qual é a diferença entre problemas de otimização e problemas de decisão?

Assim, a grande questão ainda aberta na ciência da computação é: P = NP?
O que significa a questão P = NP?

Mais conteúdos dessa disciplina

Teoria da Computação

Aspectos Teoricos

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Aspectos Teoricos

Na teoria da computação, a decidibilidade é um conceito fundamental que se refere à capacidade de resolver ou decidir um problema de forma algorítmica.O que caracteriza um problema decidível na teoria da computação?

O problema da parada desempenha um papel central na teoria da computação, pois aborda a questão de decidir se um programa de computador irá parar ou entrar em um loop infinito.Qual é a definição do problema da parada?

O próximo problema a ser solucionado é saber se dois AFDs são equivalentes, ou seja, se reconhecem a mesma linguagem.Qual é a tarefa que deve ser realizada para determinar se dois AFDs são equivalentes?

Perceba que, conhecendo algum algoritmo de ordenação, o k‑ésimo menor elemento vai ocupar exatamente a posição k, resolvendo o problema da seleção.Qual é o vetor B que deve ser obtido a partir do vetor A = (7,5,9,3,4,1) após a ordenação?

A redução por mapeamento de A para B é uma função computável f que mapeia instâncias de A para instâncias de B de forma que:Se x é uma instância de A para a qual a resposta é sim, o que podemos afirmar sobre f(x)?

Em problemas decidíveis, existem aqueles que são tratáveis e os que não são tratáveis. Isso quer dizer que qualquer problema decidível exige o gasto de recursos como tempo e memória.O que é tempo de execução?

Nesse caso, houve 16 movimentos do cabecote de leitura e gravação, portanto esse é o pior dos casos, logo o tempo de execução é 16.Qual é o tempo de execução para a cadeia ω1 = 0011?

O comportamento assintótico refere-se à tendência de uma função ou processo matemático se aproximar de um limite ou padrão à medida que se estende ao infinito.O que é notação O-grande (Big O)?

Esse tema certamente é o maior problema em aberto na ciência da computação e um dos maiores da matemática. É conhecido como P versus NP e sua resolução trará impactos profundos para a sociedade.O que estabelece a questão P versus NP?

O problema de otimização é aquele no qual cada solução possível tem um valor associado e desejamos encontrar a melhor solução em relação a esse valor.Qual é a diferença entre problemas de otimização e problemas de decisão?

Assim, a grande questão ainda aberta na ciência da computação é: P = NP?O que significa a questão P = NP?

Mais conteúdos dessa disciplina

Na teoria da computação, a decidibilidade é um conceito fundamental que se refere à capacidade de resolver ou decidir um problema de forma algorítmica.
O que caracteriza um problema decidível na teoria da computação?

O problema da parada desempenha um papel central na teoria da computação, pois aborda a questão de decidir se um programa de computador irá parar ou entrar em um loop infinito.
Qual é a definição do problema da parada?

O próximo problema a ser solucionado é saber se dois AFDs são equivalentes, ou seja, se reconhecem a mesma linguagem.
Qual é a tarefa que deve ser realizada para determinar se dois AFDs são equivalentes?

Perceba que, conhecendo algum algoritmo de ordenação, o k‑ésimo menor elemento vai ocupar exatamente a posição k, resolvendo o problema da seleção.
Qual é o vetor B que deve ser obtido a partir do vetor A = (7,5,9,3,4,1) após a ordenação?

A redução por mapeamento de A para B é uma função computável f que mapeia instâncias de A para instâncias de B de forma que:
Se x é uma instância de A para a qual a resposta é sim, o que podemos afirmar sobre f(x)?

Em problemas decidíveis, existem aqueles que são tratáveis e os que não são tratáveis. Isso quer dizer que qualquer problema decidível exige o gasto de recursos como tempo e memória.
O que é tempo de execução?

Nesse caso, houve 16 movimentos do cabecote de leitura e gravação, portanto esse é o pior dos casos, logo o tempo de execução é 16.
Qual é o tempo de execução para a cadeia ω1 = 0011?

O comportamento assintótico refere-se à tendência de uma função ou processo matemático se aproximar de um limite ou padrão à medida que se estende ao infinito.
O que é notação O-grande (Big O)?

Esse tema certamente é o maior problema em aberto na ciência da computação e um dos maiores da matemática. É conhecido como P versus NP e sua resolução trará impactos profundos para a sociedade.
O que estabelece a questão P versus NP?

O problema de otimização é aquele no qual cada solução possível tem um valor associado e desejamos encontrar a melhor solução em relação a esse valor.
Qual é a diferença entre problemas de otimização e problemas de decisão?

Assim, a grande questão ainda aberta na ciência da computação é: P = NP?
O que significa a questão P = NP?