Análise de Algoritmos | Aulas | Dicionário | Índice

Segmento de soma máxima

Considere o seguinte problema do segmento de soma máxima: dado um vetor de A[1 .. n] de números inteiros encontrar um segmento do vetor que tenha soma máxima.

Embora simples, o problema do segmento de soma máxima é um bom laboratório de algoritmos. Esta página estuda quatro algoritmos para o problema. Cada algoritmo usa uma estratégia diferente; cada algoritmo é mais eficiente que o anterior.

A página contém lições de caráter geral sobre (1) a estimativa do desempenho de algoritmos, (2) o método da divisão e conquista e (3) o método de programação dinâmica.

Esta página foi baseada num capítulo do excelente livro de Bentley.

O problema

Convém introduzir uma terminologia auxiliar para tratar do problema. Diremos que um segmento de um vetor A[1 .. n] é qualquer subvetor da forma A[i .. k], com 1 ≤ i ≤ k ≤ n. A condição i ≤ k garante que segmentos não são vazios. (Teria sido mais natural aceitar segmentos vazios, mas isso poderia tornar a discussão excessivamente sutil em algumas situações.)

A soma de um segmento A[i .. k] é o número A[i] + A[i+1] + ⋅⋅⋅ + A[k]. A altura de um vetor A[1 .. n] é a soma de um segmento de soma máxima. Em outras palavras, a altura de A[1 .. n] é o maior número do tipo A[i] + A[i+1] + ⋅⋅⋅ + A[k] com 1 ≤ i ≤ k ≤ n. (Por exemplo, a altura do vetor no exemplo A é 15 − 10 + 30 = 35.)

Problema do Segmento de Soma Máxima:  Calcular a altura de um vetor A[1 .. n] de números inteiros.

Em virtude da maneira como o conceito de segmento foi definido, a única instância do problema que não tem solução é aquela em que o vetor A[1 .. n] é vazio. Por isso, vamos supor, implicitamente, que n ≥ 1 no enunciado do problema. O problema tem outras sutilezas, que os exercícios abaixo ajudam a entender.

Primeiro algoritmo

O algoritmo óbvio para o problema do segmento de soma máxima examina, sistematicamente, todos os segmentos de A[1 .. n] e escolhe o que tiver maior soma.

O operação max devolve o valor do maior de seus argumentos. Portanto, x := max (x, s) equivale a se s > x então x := s.

O algoritmo está obviamente correto pois implementa literalmente a definição de altura. (A incialização de x na linha 1 está correta pois a altura do vetor é pelo menos A[1].) No início de cada execução da linha 7, s é a soma do segmento A[i .. k]. Como i varia de 1 até n e k varia de i até n, o valor de x na linha 8 é a altura do vetor A[1 .. n].

Desempenho.  Vamos supor que cada execução de qualquer das linhas do pseudocódigo consome uma unidade de tempo. Assim, o número de execuções de cada linha é proporcional ao consumo de tempo da linha. O consumo total de tempo do algoritmo é proporcional à soma dos números de execuções das linhas.

Comecemos a análise pela linha 6, pois ela é a mais executada. Para cada valor fixo de i e de k, a linha 6 é executada k − i + 1 vezes. Para cada i fixo, o número de execuções da linha é

Como i varia de 1 a n, o número total de execuções da linha é a metade de

sendo a, b, c e d constantes e a > 0.  Esse é o número de execuções da linha 6. O número total de execuções de cada uma das demais linhas não passa de n². Por exemplo, o número total de execuções da linha 7 é ∑_{1≤ i ≤ n} (n−i+1) = ½ n(n+1).

Concluímos assim que n³ é o termo dominante no consumo de tempo total do algoritmo. Portanto, para valores grandes de n, o consumo de tempo é praticamente proporcional a n³. Assim, o desempenho do algoritmo está em

Θ(n³)

tanto no pior caso quanto no melhor. O algoritmo é, portanto, cúbico.

Segundo algoritmo

O algoritmo Altura-Zero é muito ineficiente pois a soma de cada segmento é recalculada muitas vezes. Por exemplo, a soma de A[100 .. 200] é refeita durante o cálculo da soma de todos os segmentos A[i .. k] que têm i ≤ 100 e k ≥ 200. Nosso segundo algoritmo procura não recalcular a soma de alguns dos segmentos:

O algoritmo está correto.  A cada passagem pela linha 2, imediatamente antes da comparação de q com n, vale temos a seguinte propriedade invariante:

x é a altura do vetor A[1 .. q−1].

Essa propriedade vale quando q = 2 pois, por definição, segmentos não são vazios. Suponha agora que a propriedade vale no início de uma iteração qualquer. Observe que o bloco de linhas 3-6 examina todos os segmentos que terminam no índice q e atualiza o valor de x de acordo. Portanto, a propriedade continua valendo no início da iteração seguinte.

A propriedade invariante mostra que o algoritmo está correto, pois na última passagem pela linha 2 teremos q = n + 1 e portanto x é a altura do A[1 .. n].

Desempenho.  Suponhamos que cada execução de qualquer das linhas do pseudocódigo consome uma unidade de tempo. Então o consumo total de tempo é proporcional à soma dos números de execuções de todas as linhas.

Para cada valor fixo de q, o bloco de linhas 5-6 é executado q vezes. Como q cresce de 2 até n, o número total de execuções do bloco de linhas 5-6 é

O número total de execuções de cada uma das demais linhas é essencialmente igual a n. (Por exemplo, o número total de execuções da linha 3 é n − 1 e o número total de execuções da linha 2 é n.) Portanto, o termo dominante no consumo total de tempo do algoritmo é n² (tanto no pior quanto no melhor caso). Logo, o consumo de tempo está em

Θ(n²)

e portanto o algoritmo é quadrático.

Terceiro algoritmo: divisão e conquista

O algoritmo Altura-Um é ineficiente porque a soma de alguns segmentos é calculada mais de uma vez. Por exemplo, a soma de A[1 .. 100] é refeita durante o cálculo das somas de A[1 .. 101], A[1 .. 102], etc. Nosso terceiro algoritmo procura remediar essa ineficiência.

O algoritmo usa o método da divisão e conquista: divide a instância dada ao meio, resolve cada uma das metades e finalmente combina as duas soluções.

Para descrever o algoritmo, é preciso que o índice do primeiro elemento do vetor A seja variável. Portanto, o enunciado do problema precisa ser generalizado como segue: calcular a altura de um vetor A[p .. r] de números inteiros. (Assim, o problema original é uma coleção de instâncias do problema generalizado.) Como já fizemos acima, vamos supor que o vetor não é vazio, ou seja, que p ≤ r.

O algoritmo está correto.  Se p = r, é claro que o algoritmo dá a resposta correta. Suponha agora que p < r. Depois da linha 4, por hipótese de indução, x′ é a altura de A[p .. q]. Depois da linha 5, x″ é a altura de A[q+1 .. r]. Depois do bloco de linhas 6-13, y′ + y″ é a maior soma da forma A[i] + ⋅⋅⋅ + A[ j] com i ≤ q < j6. (Veja exercício abaixo.)

Resumindo, y′ + y″ cuida dos segmentos que contêm A[q] e A[q + 1], enquanto x′ e x″ cuidam de todos os demais segmentos. Concluímos assim que o número x calculado na linha 14 é a altura correta de A[p .. r].

Desempenho.  Seja T(n) o consumo de tempo do algoritmo quando aplicado a um vetor de tamanho n = r−p+1. O bloco de linhas 6-13 examina cada elemento de A[p .. r] uma só vez e portanto consome tempo proporcional a n. Temos então

A parcela T(⌈n/2⌉) descreve o consumo da linha 4, a parcela T(⌊n/2⌋) descreve o consumo da linha 5, e a parcela n resume o consumo das demais linhas. (Veja um dos exercícios abaixo.) Se adotarmos o valor inicial T(1) = 1, como é razoável, teremos a seguinte tabela para valores pequenos de n:

Precisamos de uma fórmula fechada para T. Poderíamos recorrer ao Teorema Mestre para mostrar que T(n) = Θ(n lg n), mas é mais instrutivo verificar isso diretamente. Começamos por mostrar que, para todo número natural n maior que 1,

T(n)  ≤  2 n lg n .

Eis a prova:  Quando n = 2, a desigualdade vale porque T(n) = T(2) = 4 ≤ 2⋅2⋅lg 2 = 2 n lg n. Quando n = 3, a desigualdade vale pois T(n) = T(3) = 8 < 9.5 < 2⋅3 < 2⋅3⋅lg 3 = 2 n lg n. Suponha agora que n ≥ 4 e que a desigualdade vale para argumentos de T menores que n. Então

Um cálculo semelhante prova que T(n) ≥ ½ n lg n  para todo n natural positivo. Portanto,

T(n) = Θ(n lg n) .

Concluímos assim que o algoritmo Altura-DC é linearítmico.

Quarto algoritmo: programação dinâmica

Embora mais eficiente que Altura-Um, o algoritmo Altura-DC tem suas próprias ineficiências, pois refaz alguns cálculos várias vezes (por exemplo, a soma de A[i .. q] nas linhas 6-9 já foi calculada durante a execução da linha 4). O próximo algoritmo procura eliminar essa ineficiência.

Nosso quarto algoritmo usa o método de programação dinâmica, que consiste em armazenar os resultados de cálculos intermediários numa tabela e assim evitar que eles sejam refeitos.

Para aplicar o método, será preciso introduzir o seguinte problema auxiliar, que restringe a atenção aos segmentos finais do vetor: dado um vetor A[1 .. q] com q ≥ 1, encontrar a maior soma da forma

A[i] + ⋅⋅⋅ + A[q] ,

com 1 ≤ i ≤ q. Para facilitar a discussão, diremos que a maior soma dessa forma é a semialtura do vetor A[1 .. q]. A altura do vetor A[1 .. n] é o máximo das semialturas de A[1 .. n], A[1 .. n−1], A[1 .. n−2], etc.

A semialtura de um vetor tem uma propriedade recursiva que a altura não tem: se A[i .. q] corresponde à semialtura de A[1 .. q] e i < q então A[i .. q−1] corresponde à semialtura de A[1 .. q−1]. (De fato, se assim não fosse, teríamos A[h] + ⋅⋅⋅ + A[q − 1] > A[i] + ⋅⋅⋅ + A[q − 1] para algum h ≤ q − 1 e portanto teríamos A[h] + ⋅⋅⋅ + A[q−1] + A[q] > A[i] + ⋅⋅⋅ + A[q−1] + A[q], o que é impossível.)

Se denotarmos a semialtura de A[1 .. q] por S[q], podemos resumir a propriedade recursiva por meio de uma recorrência: para qualquer vetor A[1 .. q],

S[q] = max (S[q−1] + A[q] , A[q]) .

Em outras palavras, S[q] = S[q−1] + A[q] a menos que S[q − 1] seja negativo, caso em que S[q] = A[q]. Essa recorrência serve de base para o seguinte algoritmo, que calcula a altura de A[1 .. n]:

(Compare esse código com o do algoritmo Altura-Um.)

O algoritmo está correto.  A cada passagem pela linha 2, imediatamente antes que q seja comparado com n, S[q−1] é a semialtura de A[1 .. q−1]. Mais que isso: para todo j de 1 a q − 1 ,

S[ j] é a semialtura de A[1 .. j] .

Em particular, no início da linha 6, esse fato vale para todo j de 1 a n. O bloco de linhas 6-8 escolhe a maior das semialturas e portanto, no fim do algoritmo, x é a altura correta de A[1 .. n].

Desempenho.  A estimativa do consumo de tempo do algoritmo é muito fácil. As linhas 1, 6 e 9 do algoritmo são executadas 1 vez cada. As linhas 2, 3, 4, 7 e 8 são executadas cerca de n vezes cada, e portanto o algoritmo consome tempo proporcional a n. Em outras palavras, o desempenho do algoritmo no pior caso está em

Θ(n)

e portanto o algoritmo é linear.