Saat belajar pemrograman, saya menemukan contoh algoritma yang tidak mungkin. Intuisi mengatakan bahwa ini tidak mungkin, tetapi komputer membantahnya hanya dengan menjalankan kode. Bagaimana masalah seperti itu, yang membutuhkan biaya kubik minimum pada waktunya, diselesaikan hanya dalam persegi? Dan yang itu saya pasti akan memutuskan untuk baris itu. Apa? Apakah ada algoritma logaritma yang jauh lebih efisien dan elegan? Luar biasa!

Dalam artikel ini saya akan menyajikan beberapa dari algoritma "pemecah pola" ini, yang menunjukkan bahwa intuisi dapat sangat melebih-lebihkan kompleksitas waktu suatu masalah.

Menarik? Selamat datang di bawah potongan!

Perhitungan elemen ke-n dari urutan berulang dalam logaritma

Yang saya maksud dengan "berulang" adalah urutan yang memenuhi persamaan berikut:

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

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

Pertama $k$ elemen urutan dianggap sudah diberikan. Jumlah $k$ disebut kardinalitas urutan, dan $c_i$ koefisien urutan. Contoh umum: angka Fibonacci, di mana $a_1 = 0$ , $a_2 = 1$ , $c_1 = 1$ , $c_2 = 1$ ... Kita mendapatkan angka-angka terkenal: 0, 1, 1, 2, 3, 5, 8, 13, ... Sepertinya tidak ada kesulitan dalam menghitung elemen ke-n per baris, tetapi ternyata bisa dilakukan untuk logaritma!

Ide: bagaimana jika Anda membayangkan sebuah komputasi $a_n$ saat ereksi $n$ - - ? , ? , $a_{n+2}$ ? $a_n$ $a_{n+1}$ . , , . - "" . ? : ! , , ?

, ! :

A = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})

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

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

, ? ? , :

(\begin{matrix} f_{n + 1} & f_{n} \\ f_{n} & f_{n - 1} \end{matrix}) \times (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) = (\begin{matrix} f_{n + 2} & f_{n + 1} \\ f_{n + 1} & f_{n} \end{matrix})

$\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}

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

$A$ :

(\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix})

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

? , . , . :

(\begin{matrix} 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{matrix}) \times (\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) = (\begin{matrix} 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{matrix})

$\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{matrix} t_{5} & t_{4} & t_{3} \\ t_{4} & t_{3} & t_{2} \\ t_{3} & t_{2} & t_{1} \end{matrix}) = (\begin{matrix} 3 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \end{matrix})

$\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{matrix} c_{1} & 1 & 0 & 0 & \dots & 0 \\ c_{2} & 0 & 1 & 0 & \dots & 0 \\ c_{3} & 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ c_{k} & 0 & 0 & 0 & \dots & 1 \end{matrix})

$\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)$ .

. , . . , .
. , .
$O(n \log n)$ . , : , , .
$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}

Mari kita buktikan persamaan terakhir. Jelas T[i] >= 0

bagi siapa pun i

. Biarkan k = A[i + 1]

. Pertimbangkan tiga kasus:

k < 0

... Maka 0 akan mengungguli k

yang pertama max

.
k = 0

... Pada max

argumen pertama , Anda cukup menghapus argumen kedua.
k > 0

... Lalu max{T[i] + k, k, 0} = T[i] + k = max{T[i] + k, 0}

.

Karena linearitas dan kesederhanaan persamaan, algoritme ini cukup singkat:

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

Kesimpulan

Dalam kedua tugas tersebut, teknik pemrograman dinamis membantu kami meningkatkan kinerja secara kualitatif. Ini bukan kebetulan, dinamika sering kali memberikan algoritme yang optimal secara asimtotik berkat ekonomi bawaan: kami hanya menghitung semuanya sekali.

Algoritme menakjubkan apa yang Anda ketahui?

Algoritma yang luar biasa cepat

Perhitungan elemen ke-n dari urutan berulang dalam logaritma

Kesimpulan

More articles: