プログラミングを勉強していると、不可能なアルゴリズムの例に出くわします。直感ではこれは不可能だと言われていますが、コンピューターはコードを実行するだけで反論します。時間内に最小の立方体コストを必要とするこのような問題を、どのようにして1つの正方形で解決できるでしょうか。そして、それは私が間違いなくラインのために決めるでしょう。何？はるかに効率的でエレガントな対数アルゴリズムはありますか？すごい！

この記事では、これらの「パターンを壊す」アルゴリズムのいくつかを紹介し、直感が問題の時間計算量を大幅に過大評価する可能性があることを示します。

面白い？カットの下でようこそ！

対数での反復シーケンスのn番目の要素の計算

「再発」とは、次の式を満たすシーケンスを意味します。

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

最初 $k$ シーケンスの要素は指定されていると見なされます。数 $k$ シーケンスのカーディナリティと呼ばれ、 $c_i$ シーケンスの係数。典型的な例：フィボナッチ数、ここで $a_1 = 0$ 、 $a_2 = 1$ 、 $c_1 = 1$ 、 $c_2 = 1$ ..。よく知られている数値を取得します：0、1、1、2、3、5、8、13、...行ごとにn番目の要素を計算するのは難しいことではないようですが、それは可能であることがわかります対数のために！

アイデア：計算を想像するとどうなるか $a_n$ 勃起として $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}

最後の平等を証明しましょう。T[i] >= 0

誰にとっても明らかですi

。しましょうk = A[i + 1]

。3つのケースを考えてみましょう。

k < 0

..。その場合k

、最初ので0がパフォーマンスを上回りmax

ます。
k = 0

..。最初のmax

引数では、2番目の引数を削除するだけです。
k > 0

..。次にmax{T[i] + k, k, 0} = T[i] + k = max{T[i] + k, 0}

。

方程式の線形性と単純さのために、アルゴリズムは非常に短いです。

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

結論

どちらのタスクでも、動的計画法はパフォーマンスを質的に向上させるのに役立ちました。これは偶然ではありません。組み込みの経済性のおかげで、ダイナミクスは漸近的に最適なアルゴリズムを提供することがよくあります。すべてを1回だけカウントします。

あなたはどんな素晴らしいアルゴリズムを知っていますか？

驚くほど高速なアルゴリズム

対数での反復シーケンスのn番目の要素の計算

結論

More articles: