En étudiant la programmation, je rencontre des exemples d'algorithmes impossibles. L'intuition dit que cela ne peut pas être, mais l'ordinateur le réfute en exécutant simplement le code. Comment un tel problème, qui nécessite un minimum de coûts cubiques dans le temps, peut-il être résolu en un carré? Et celui-là, je déciderai définitivement de la ligne. Quoi? Existe-t-il un algorithme de logarithme beaucoup plus efficace et élégant? Incroyable!

Dans cet article, je présenterai plusieurs de ces algorithmes «révolutionnaires», montrant que l'intuition peut largement surestimer la complexité temporelle d'un problème.

Intéressant? Bienvenue sous la coupe!

Calcul du nième élément de la séquence récurrente dans le logarithme

Par «récurrent», j'entends une séquence qui satisfait l'équation suivante:

$$

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

La première $$$k$ les éléments de la séquence sont considérés comme donnés. Nombre $$$k$ s'appelle la cardinalité de la séquence, et $$$c_i$ coefficients de la séquence. Exemple typique: nombres de Fibonacci, où $$$a_1 = 0$ , $$$a_2 = 1$ , $$$c_1 = 1$ , $$$c_2 = 1$ ... Nous obtenons les nombres bien connus: 0, 1, 1, 2, 3, 5, 8, 13, ... Il semble qu'il n'y ait aucune difficulté à calculer le nième élément par ligne, mais il s'avère que cela peut être fait pour un logarithme!

Idée: et si vous imaginez un calcul $$$a_n$ comme érection dans $$$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}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Prouvons la dernière égalité. Il est clair que T[i] >= 0



pour n'importe qui i



. Laissez k = A[i + 1]



. Considérez trois cas:

1. k < 0
   
   
   
   ... Ensuite, 0 surperformera k
   
   
   
   dans le premier max
   
   
   
   .
2. k = 0
   
   
   
   ... Dans le premier max
   
   
   
   , vous pouvez simplement supprimer le deuxième argument.
3. k > 0
   
   
   
   ... Alors max{T[i] + k, k, 0} = T[i] + k = max{T[i] + k, 0}
   
   
   
   .

En raison de la linéarité et de la simplicité de l'équation, l'algorithme est assez court:

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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Conclusion

Dans les deux tâches, la technique de programmation dynamique nous a aidés à améliorer qualitativement les performances. Ce n'est pas un hasard, la dynamique donne souvent des algorithmes asymptotiquement optimaux grâce à l'économie intégrée: nous ne comptons tout qu'une seule fois.

Quels algorithmes étonnants connaissez-vous?