Exercícios de analise de algoritmos

1) Sim, o algoritmo cumpre o que promete, somando todos os elementos do vetor. Ele faz isso dividindo o vetor sempre ao meio, calculando a soma de cada metade recursivamente, e depois somando os resultados.

Por exemplo, suponha o vetor A = [2, 4, 6, 1, 3, 5], sendo este 1-indexado (a primeira posição possui índice 1)

• SOMA(A, 1, 6) = 21
  
  • x = SOMA(A, 1, 3)
    
    • x = SOMA(A, 1, 2)
      • x = SOMA(A, 1, 1) = A[1] = 2
      • y = SOMA(A, 2, 2) = A[2] = 4
      • x + y = 6
    • y = SOMA(A, 3, 3) = A[3] = 6
    • x + y = 12
  • y = SOMA(A, 4, 6)
    
    • x = SOMA(A, 4, 5)
      • x = SOMA(A, 4, 4) = A[4] = 1
      • y = SOMA(A, 5, 5) = A[5] = 3
      • x + y = 4
    • y = SOMA(A, 6, 6) = A[6] = 5
    • x + y = 9
  • x + y = 21

Para calcular a complexidade deste algoritmo, poderíamos utilziar o teorema mestre. Porém, isso não será necessário, pois a complexidade deste algoritmo é bastante intuitiva. Apesar de somar os elementos do vetor de uma forma mais "complicada" que o habitual, na prática o algoritmo sempre acessará todas as N posições do vetor, e cada uma delas apenas uma única vez. Sendo assim, a complexidade é O(N)

2) Como o vetor é dado na forma decrescente, pode-se encontrar a maior diferença A[j] - A[i] de forma gulosa. Para que essa diferença seja a maior possível, queremos que A[j] seja o maior possível e que A[i] seja o menor possível, e como o vetor está ordenado de forma decrescente, sabemos que o maior elemento está na primeira posição (A[1]) e o menor elemento está na última posição (A[n]). Ou seja, a maior diferença é A[1] - A[n]. Todas as operações envolvidas possuem custo constante (acesso a 2 posições do vetor e cálculo da diferença), por isso este algoritmo tem complexidade constante: O(1).

3)

(a) O algoritmo de “quicksort” pode ser implementado para tentar na prática evitar o pior caso.

Verdadeiro, mas cuidado! Existem formas de otimizar o algoritmo "quicksort" para evitar cair no pior caso (acredito que a técnica "mediana de três" seja a mais conhecida), porém isso não garante que o algoritmo nunca cairá no pior caso, ainda existem casos no qual a complexidade será O(n²).

(b) O merge sort sempre consome tempo ?(nlgn)

Verdadeiro. Essa é uma das grandes vantagens do merge sort. Na maioria dos casos ele é mais lento que o quicksort, mas diferente deste último, sua complexidade no pior caso ainda é O(nlgn).

(c) A busca binária não precisa de um vetor ordenado para funcionar.

Falso. O vetor estar ordenado é o que nos garante "eliminar" metade do intervalo de busca de uma vez. Dado um vetor A[1..n] em que estamos buscando o valor x e possui a posição central q = (n + 1)/2. Com o vetor ordenado, se A[q] = x, então já encontramos o valor desejado; se A[q] < x, estão x só pode estar entre as posições q+1 e n, pois todas as posições de 1 à q-1 possuem valores menores que A[q], e assim sendo, menores que x; de forma análoga, se A[q] > x, o valor x só pode estar entre as posições 1 e q-1. Agora, se o vetor não estivesse ordenado, não teriamos como garantir nada disso, e todas as posições precisariam ser varridas.

(d) O filho esquerdo de um nó k em um heap é dado por ?k/2?.

Falso. Pela definição de heap, com raiz iniciada em 0, um nó k possui o filho esquerdo 2*k + 1 e o filho direito 2*k + 2.