Mientras estudiaba programación, me encontré con ejemplos de algoritmos imposibles. La intuición dice que esto no puede ser, pero la computadora lo refuta simplemente ejecutando el código. ¿Cómo se puede resolver un problema así, que requiere un mínimo de costos cúbicos en el tiempo, en solo un cuadrado? Y ese definitivamente lo decidiré por la línea. ¿Qué? ¿Existe un algoritmo de logaritmo mucho más eficiente y elegante? ¡Asombroso!

En este artículo presentaré varios de estos algoritmos de "ruptura de patrones", mostrando que la intuición puede sobrestimar en gran medida la complejidad temporal de un problema.

¿Interesante? ¡Bienvenido bajo el corte!

Cálculo del enésimo elemento de la secuencia recurrente en el logaritmo

Por "recurrente" me refiero a una secuencia que satisface la siguiente ecuación:

$$

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

El primero $$$k$ los elementos de la secuencia se consideran dados. Número $$$k$ se llama cardinalidad de la secuencia, y $$$c_i$ coeficientes de la secuencia. Ejemplo típico: números de Fibonacci, donde $$$a_1 = 0$ , $$$a_2 = 1$ , $$$c_1 = 1$ , $$$c_2 = 1$ ... Obtenemos los números conocidos: 0, 1, 1, 2, 3, 5, 8, 13, ... Parece que no hay dificultad para calcular el enésimo elemento por línea, pero resulta que se puede hacer para un logaritmo!

Idea: ¿y si imaginas un cálculo? $$$a_n$ como erección en $$$n$ - - ? , ? , $$$a_{n+2}$ ? $$$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}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Demostremos la última igualdad. Eso está claro T[i] >= 0



para cualquiera i



. Deja k = A[i + 1]



. Considere tres casos:

1. k < 0
   
   
   
   ... Entonces 0 superará k
   
   
   
   en el primero max
   
   
   
   .
2. k = 0
   
   
   
   ... En el primero max
   
   
   
   , simplemente puede eliminar el segundo argumento.
3. k > 0
   
   
   
   ... Entonces max{T[i] + k, k, 0} = T[i] + k = max{T[i] + k, 0}
   
   
   
   .

Debido a la linealidad y simplicidad de la ecuación, el algoritmo es bastante corto:

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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Conclusión

En ambas tareas, la técnica de programación dinámica nos ayudó a mejorar cualitativamente el rendimiento. Esto no es una coincidencia, la dinámica a menudo proporciona algoritmos óptimos asintóticamente gracias a la economía incorporada: solo contamos todo una vez.

¿Qué algoritmos asombrosos conoces?