Questão 2286736

• Banca: SUGEP - UFRPE
• Órgão: UFRPE
• Ano: 2016
• Provas: SUGEP - UFRPE - 2016 - UFRPE - Técnico em Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

A Complexidade Computacional é a área da Ciência da Computação que se ocupa, entre outros, do estudo e análise do custo de tempo de execução e espaço ocupado pelos algoritmos. Sobre Complexidade Computacional, marque V para as afirmações Verdadeiras, ou F para as Falsas.

( ) A função de complexidade de tempo de algoritmo indica o tempo necessário para executar o programa que implementa o algoritmo em função do tamanho da entrada.

( ) Se f é uma função de complexidade baseada na análise de pior caso, o custo de aplicar o algoritmo nunca é maior do que f(n).

( ) Na análise do caso médio toma-se a média aritmética do pior caso com o melhor caso.

A sequência correta, de cima para baixo, é:

• A. V, V, V
• B. F, F, F.
• C. V, F, F
• D. F, V, F.
• E. F, F, V.

Gabarito: D

Comentários

• Questão estranha.. não consegui encontrar resposta para as alternativas I e II.

  I - A função de complexidade de tempo de algoritmo indica o tempo necessário para executar o programa que implementa o algoritmo em função do tamanho da entrada.

  Definição do Wikipedia: "Em ciência da computação, a complexidade de tempo de um algoritmo quantifica a porção de tempo tomada por um algoritmo para rodar em função do tamanho da entrada do problema". Não encontrei diferença que justifique a alternativa ser Falsa.

   

  II Se f é uma função de complexidade baseada na análise de pior caso, o custo de aplicar o algoritmo nunca é maior do que f(n).

  Para este exemplo, o Quicksort em seu pior caso é de complexidade O(n²), portanto maior que O(n).

   

  Se alguém puder explicá-la, agradeceria.

• Oi Leonardo, o caso II creio que ele esteja falando que a função f(n) é o pior caso. Por ser o pior caso, nada virá acima dela com relação à complexidade do algoritmo. Foi assim que entendi pelo menos! A meu ver ele não está dizendo que f(n) é O(n).

   

   

• Verdade Yane Wanderley, consegui compreender!

  Obrigado pela explicação!

• Leonardo, com relação à II, quando ele diz f(n) ele não está se referindo à complexidade linear O(n). f(n) é a função de complexidade de tempo do algoritmo. De fato ela nunca será maior que o pior caso do algoritmo. Portanto, II está correta.

• Creio que o erro da I está em afirmar que a função de complexidade indica o tempo necessário para executar o programa, o que não é necessariamente verdade. Por exemplo, podemos ter uma função de tempo em que o programa é executado em 5n³ + 2n² + 500n unidades de tempo, porém sua função de complexidade será apenas O(n³).

• Força Guerreiro!!!!!!