Während des Programmierstudiums stoße ich auf Beispiele für unmögliche Algorithmen. Intuition sagt, dass dies nicht sein kann, aber der Computer widerlegt es, indem er einfach den Code ausführt. Wie kann ein solches Problem, das ein Minimum an kubischen Kosten in der Zeit erfordert, in nur einem Quadrat gelöst werden? Und diesen werde ich definitiv für die Linie entscheiden. Was? Gibt es einen viel effizienteren und eleganteren Logarithmus-Algorithmus? Tolle!

In diesem Artikel werde ich einige dieser "Musterbrechungs" -Algorithmen vorstellen, die zeigen, dass die Intuition die zeitliche Komplexität eines Problems stark überschätzen kann.

Interessant? Willkommen unter dem Schnitt!

Berechnung des n-ten Elements der wiederkehrenden Folge im Logarithmus

Mit "wiederkehrend" meine ich eine Sequenz, die die folgende Gleichung erfüllt:

$$

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

Der Erste $$$k$ Elemente der Sequenz gelten als gegeben. Nummer $$$k$ heißt die Kardinalität der Sequenz, und $$$c_i$ Koeffizienten der Sequenz. Typisches Beispiel: Fibonacci-Zahlen, wobei $$$a_1 = 0$ , $$$a_2 = 1$ , $$$c_1 = 1$ , $$$c_2 = 1$ ... Wir erhalten die bekannten Zahlen: 0, 1, 1, 2, 3, 5, 8, 13, ... Es scheint, dass es keine Schwierigkeit gibt, das n-te Element pro Zeile zu berechnen, aber es stellt sich heraus, dass dies möglich ist für einen Logarithmus!

Idee: Was ist, wenn Sie sich eine Berechnung vorstellen? $$$a_n$ als Erektion in $$$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}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Beweisen wir die letzte Gleichheit. Es ist klar, dass T[i] >= 0



für jeden i



. Lass k = A[i + 1]



. Betrachten Sie drei Fälle:

1. k < 0
   
   
   
   ... Dann wird 0 k
   
   
   
   in der ersten übertreffen max
   
   
   
   .
2. k = 0
   
   
   
   ... Im ersten max
   
   
   
   können Sie einfach das zweite Argument entfernen.
3. k > 0
   
   
   
   ... Dann max{T[i] + k, k, 0} = T[i] + k = max{T[i] + k, 0}
   
   
   
   .

Aufgrund der Linearität und Einfachheit der Gleichung ist der Algorithmus ziemlich kurz:

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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Fazit

Bei beiden Aufgaben hat uns die dynamische Programmiertechnik geholfen, die Leistung qualitativ zu verbessern. Dies ist kein Zufall, Dynamik liefert dank integrierter Wirtschaftlichkeit oft asymptotisch optimale Algorithmen: Wir zählen alles nur einmal.

Welche erstaunlichen Algorithmen kennen Sie?