Enquanto estudo programação, encontro exemplos de algoritmos impossíveis. A intuição diz que não pode ser, mas o computador refuta simplesmente executando o código. Como esse problema, que requer um mínimo de custos cúbicos no tempo, pode ser resolvido em apenas um quadrado? E esse eu definitivamente decidirei para a linha. O que? Existe um algoritmo de logaritmo muito mais eficiente e elegante? Surpreendente!

Neste artigo, apresentarei vários desses algoritmos de "quebra de padrões", mostrando que a intuição pode superestimar muito a complexidade de tempo de um problema.

Interessante? Bem-vindo ao corte!

Cálculo do enésimo elemento da sequência recorrente no logaritmo

Por "recorrente", quero dizer uma sequência que satisfaça a seguinte equação:

$$

$$a_{n+k+1} = \sum_{i = 1}^{k} c_{i} a_{n + i}$$

O primeiro $$$k$ elementos da sequência são considerados dados. Número $$$k$ é chamado decardinalidade dasequência, e $$$c_i$ coeficientes i da sequência. Exemplo típico: números de Fibonacci, onde $$$a_1 = 0$ , $$$a_2 = 1$ , $$$c_1 = 1$ , $$$c_2 = 1$ . Obtemos os números conhecidos: 0, 1, 1, 2, 3, 5, 8, 13, ... Parece que não há dificuldade em calcular o enésimo elemento por linha, mas acontece que pode ser feito para um logaritmo!

Idéia: e se você imaginar um cálculo $$$a_n$ como ereção em $$$n$ enésima potência de algum objeto? Você pode elevar a uma potência para o logaritmo, mas que tipo de objeto será? Em geral, o que você precisa saber para calcular $$$a_{n+2}$ ? Somente $$$a_n$ $$$a_{n+1}$ . , , . - "" . ? : ! , , ?

, ! :

$$

$$\begin{equation*} A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \end{equation*}$$

, $$$a_{n+1} = A^n_{1,1}$ . , !

, ? ? , :

$$

$$\begin{equation*} \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix} \times \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} f_{n+2} & f_{n+1} \\ f_{n+1} & f_n \end{pmatrix} \end{equation*}$$

, " " . . $$$A$ . "":

$$

$$t_1 = 1 \\ t_2 = 1 \\ t_3 = 1 \\ ... \\ t_{n+3} = t_{n+2} + t_{n+1} + t_n$$

$$$A$ :

$$

$$\begin{equation*} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \end{equation*}$$

? , . , . :

$$

$$\begin{equation*} \begin{pmatrix} t_{n+2} & t_{n+1} & t_n \\ t_{n+1} & t_n & t_{n-1} \\ t_n & t_{n-1} & t_{n-2} \end{pmatrix} \times \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} t_{n+3} & t_{n+2} & t_{n+1} \\ t_{n+2} & t_{n+1} & t_n \\ t_{n+1} & t_n & t_{n-1} \end{pmatrix} \end{equation*}$$

, $$$T$ :

$$

$$\begin{equation*} \begin{pmatrix} t_5 & t_4 & t_3 \\ t_4 & t_3 & t_2 \\ t_3 & t_2 & t_1 \end{pmatrix} = \begin{pmatrix} 3 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \end{pmatrix} \end{equation*}$$

$$$t_{n+2} = (T \times A^{n - 1})_{1, 1}$ . , $$$A$ $$$n - 1$ , $$$T$ $$$A$ . $$$T$ $$$A$ .

, $$$k$ :

$$

$$\begin{equation*} \begin{pmatrix} c_1 & 1 & 0 & 0 & \cdots & 0 \\ c_2 & 0 & 1 & 0 & \cdots & 0 \\ c_3 & 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ c_k & 0 & 0 & 0 & \cdots & 1 \end{pmatrix} \end{equation*}$$

, , $$$2k - 1$ , "" .

, $$$O(k^3 \log n)$ : $$$O(k^3)$ , $$$O(\log n)$ . . , , $$$n \ge 44$ , $$$n \ge 208$ . \ , . , $$$n \ge 118$ .

Matrix :

class Matrix:
    def __init__(self, n):
        self.n = n
        self.rows = [[0 for col in range(n)] for row in range(n)]

    def set(self, row, col, value):
        self.rows[row][col] = value

    def get(self, row, col):
        return self.rows[row][col]

    def __str__(self):
        result = ''
        for row in self.rows:
            result += ' '.join([str(col) for col in row])
            result += '\n'
        return result

    def __mul__(self, other):
        result = Matrix(self.n)
        for row in range(self.n):
            for col in range(self.n):
                s = sum([self.get(row, k) * other.get(k, col) for k in range(self.n)])
                result.set(row, col, s)
        return result

    def __len__(self):
        return self.n

    def __pow__(self, k):
        if k == 0:
            result = Matrix(len(self))
            for i in range(len(self)):
                result.set(i, i, 1)
        elif k == 1:
            result = self
        elif k == 2:
            result = self * self
        else:
            rem = k % 3
            prev = self.__pow__((k - rem) // 3)
            result = prev * prev * prev
            if rem:
                result *= self.__pow__(rem)
        return result
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

__pow__



: M ** k



, M



Matrix



. , 3. .

$$$T$ $$$A$ , Matrix



:

A = Matrix(3)
A.set(0, 0, 1)
A.set(0, 1, 1)
A.set(1, 0, 1)
A.set(1, 2, 1)
A.set(2, 0, 1)
T = Matrix(3)
T.set(0, 0, 3)
T.set(0, 1, 1)
T.set(0, 2, 1)
T.set(1, 0, 1)
T.set(1, 1, 1)
T.set(1, 2, 1)
T.set(2, 0, 1)
T.set(2, 1, 1)
T.set(2, 2, 0)
n = int(sys.argv[1])
if n:
    print(T * A ** (n - 1))
else:
    print(T ** 0)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

$$$n$ — , . , , , - . , , .

: A[1..n]



( ). A[i..j]



. i



j



. , $$$O(n^3)$ , $$$O(n^2)$ , $$$O(n \log n)$ $$$O(n)$ .

:

1. . , . . , .
2. . , .
3. $$$O(n \log n)$ . , : , , .
4. $$$O(n)$ . T[1..n]
   
   
   
   , i
   
   
   
   - , i
   
   
   
   . , $$$T$ , $$$T$ .

. , T[i + 1]



, T[i]



? , i



, , . , T[i + 1]



T[i] + A[i + 1]



, A[i + 1]



, 0, A[i + 1] < 0



. :

T[0] = 0,
T[i + 1] = max{T[i] + A[i + 1], A[i + 1], 0} = max{T[i] + A[i + 1], 0}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

. , T[i] >= 0



i



. k = A[i + 1]



. :

1. k < 0
   
   
   
   . 0 k



max
   
   
   
   .
2. k = 0
   
   
   
   . max
   
   
   
   .
3. k > 0
   
   
   
   . max{T[i] + k, k, 0} = T[i] + k = max{T[i] + k, 0}
   
   
   
   .

, :

def kadane(ints):
    prev_sum = 0
    answer = -1
    for n in ints:
        prev_sum = max(prev_sum + n, 0)
        if prev_sum >= answer:
            answer = prev_sum
    return answer
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Em ambas as tarefas, a técnica de programação dinâmica nos ajudou a melhorar qualitativamente o desempenho. Isso não é coincidência, a dinâmica geralmente fornece algoritmos assintoticamente ideais graças à economia embutida: contamos tudo apenas uma vez.

Que algoritmos incríveis você conhece?