PAA - Análise Assintótica

Na análise de algoritmos para resolver certos problemas, é necessário avaliar não só o tamanho dos dados de entrada, mas os diferentes cenários para esses dados de entrada. Estes cenários são:

• Cenário complexo, cenário de entrada única e cenário constante
• Caso constante, caso polinomial e caso exponencial
• Pior caso, caso médio, melhor caso
• Caso mediano, caso preferencial e caso particular

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, é:

• V, V, V
• F, F, F
• V, F, V
• F, V, F

Qual opção não representa uma notação para classificar assintoticamente um algoritmo?

• Big-O
• Big-Omega
• Big-Beta
• Big-Teta

As figuras a), b) e c) representam quais notações, respectivamente:

• Big-O, Big-Omega, Big-Teta
• Big-Teta, Big-Omega, Big-O
• Big-Omega, Big-O, Big-Teta
• Big-Teta, Big-O, Big-Omega

A respeito de funções e algoritmos, assinale a afirmativa correta.

• O limite inferior de um algoritmo (Ω) é utilizado para a análise do pior caso de sua execução.
• Uma função f(n) domina assintoticamente g(n), se existem duas constantes positivas c e n0, tais que, para n ≥ n0, temos que |g(n)| ≥ c|f(n)|.
• A função f(5.log₂ n) é O(n²)
• A função f(5n³ + 2n²) é O(n).

Se a complexidade de tempo de um algoritmo é da ordem de Θ(n . log n), é correto afirmar que esse algoritmo também é

• Ω(n . log n)
• Ω(n²)
• O(n)
• Θ(n)

Seja n o tamanho da entrada de um algoritmo para um problema P. Cada alternativa, que corresponde a um algoritmo distinto, apresenta o número de operações necessárias para resolver P.  Considerando-se a análise assintótica (Big O notation), qual algoritmo possui menor complexidade?

• 2 + 10 . log n
• 3n² + n
• 1000 + 2n³
• 5n + 128

Considere a função de complexidade f(n) = 3n³ + 4n² +2n. Selecione a opção abaixo contendo o menor valor para a constante c, c > 0, para que g(n) = c.n³ domine assintoticamente f(n), para n >= 1.

• 12
• 3
• 9
• 8

Leia as afirmativas a seguir considerando que f(n) e g(n) são funções positivas.
I) Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo f(n) possui Ordem de complexidade g(n).
II) Se g(n) é O(f(n)), f(n) é um limite superior para g(n).
III) Se a função g(n) = 7.log(n) + 6, então a função g(n) é O(log(n)).
IV) Se g(n) = n² e f(n) = (n+1)² temos que g(n) é O(f(n)) e f(n) é O(g(n)).
V) Se g(n) = 2⁽ⁿ⁺¹⁾ e f(n) = 2ⁿ temos que g(n) = O(f(n)).
Assinale a alternativa que apresenta somente as afirmativas CORRETAS.

• I, II, IV, V
• I, III, IV, V
• II, III, IV
• II, III, IV, V

Considere os seguintes algoritmos e suas complexidades na notação Big O:
- Algoritmo A: O(log n)
- Algoritmo B: O(n²) 
- Algoritmo C: O(n . log n) 
Considerando-se o pior caso de execução destes algoritmos, é correto afirmar que o algoritmo

• A é o menos eficiente
• C é o menos eficiente
• B é o menos eficiente
• C é o mais eficiente