A Complexidade Computacional é a área da Ciência da Computa...

A alternativa correta é: D - F, V, F

Vamos analisar cada uma das afirmações dadas na questão para entender melhor o tema da complexidade computacional e justificar as alternativas.

( ) 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.

Essa afirmação é falsa. A função de complexidade de tempo de um algoritmo na verdade descreve a ordem de crescimento do tempo de execução em função do tamanho da entrada, não o tempo exato de execução do programa.

( ) 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).

Essa afirmação é verdadeira. A análise de pior caso nos dá uma garantia de que o tempo de execução do algoritmo não excederá f(n), independentemente da entrada específica.

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

Essa afirmação é falsa. A análise de caso médio considera a média dos tempos de execução para todas as entradas possíveis, ponderada pela probabilidade de cada entrada, e não simplesmente a média aritmética do pior e do melhor caso.

Agora vamos revisar as alternativas incorretas:

• A - V, V, V: Errou ao considerar a primeira e a terceira afirmação como verdadeiras.
• B - F, F, F: Errou ao considerar a segunda afirmação como falsa.
• C - V, F, F: Errou ao considerar a primeira afirmação como verdadeira.
• E - F, F, V: Errou ao considerar a terceira afirmação como verdadeira.

Como você pode ver, entender a definição correta dos conceitos de complexidade de tempo e suas análises (pior caso, melhor caso, e caso médio) é essencial para responder corretamente questões desse tipo em concursos públicos.

Se precisar de mais alguma explicação ou tiver dúvidas adicionais, estou à disposição!

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³).