While studying programming, I come across examples of impossible algorithms. Intuition says that this cannot be, but the computer refutes it by simply running the code. How can such a problem, which requires a minimum of cubic costs in time, be solved in just a square? And that one I will definitely decide for the line. What? Is there a much more efficient and elegant logarithm algorithm? Amazing!

In this article I will present several of these "pattern-breaking" algorithms, showing that intuition can greatly overestimate the time complexity of a problem.

Interesting? Welcome under the cut!

Calculation of the nth element of the recurrent sequence in the logarithm

By "recurrent" I mean a sequence that satisfies the following equation:

$$

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

The first $$$k$ elements of the sequence are considered given. Number $$$k$ is called the cardinality of the sequence, and $$$c_i$ coefficients of the sequence. Typical example: Fibonacci numbers, where $$$a_1 = 0$ , $$$a_2 = 1$ , $$$c_1 = 1$ , $$$c_2 = 1$ ... We get the well-known numbers: 0, 1, 1, 2, 3, 5, 8, 13, ... It seems that there is no difficulty in calculating the n-th element per line, but it turns out it can be done for a logarithm!

Idea: what if you imagine a computation $$$a_n$ as erection in $$$n$ degree of any object? You can raise to a power for the logarithm, just what kind of object will it be? In general, what you need to know to calculate $$$a_{n+2}$ ? Only $$$a_n$ and $$$a_{n+1}$ ... So this object, whatever it is, must contain these two numbers. There must also be some "natural" way to multiply these objects. Doesn't it look like anything? Much like matrices: they are made up of numbers and can be multiplied! But is there such a matrix, multiplying which with itself, will we consistently get the Fibonacci numbers?

It turns out there is! There she is:

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

You can check for yourself and make sure that $$$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}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Let us prove the last equality. It is clear that T[i] >= 0



for anyone i



. Let k = A[i + 1]



. Consider three cases:

1. k < 0
   
   
   
   ... Then 0 will outperform k
   
   
   
   in the first max
   
   
   
   .
2. k = 0
   
   
   
   ... In the first max
   
   
   
   one, you can simply remove the second argument.
3. k > 0
   
   
   
   ... Then max{T[i] + k, k, 0} = T[i] + k = max{T[i] + k, 0}
   
   
   
   .

Due to the linearity and simplicity of the equation, the algorithm is quite short:

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

In both tasks, the dynamic programming technique helped us to qualitatively improve performance. This is no coincidence, dynamics often gives asymptotically optimal algorithms thanks to built-in economy: we only count everything once.

What amazing algorithms do you know?