n x n
ラプラス展開に基づいて、行列式を計算するアルゴリズムを作成しました。
以下の繰り返し関係を取得しました。
T(n) = n(n² + T(n-1))
ウィキペディアで、これにより結果が得られるはずだと読みましたT(n) = O(n!)
が、それを証明する方法がわかりません(直感的ですが)。
n x n
ラプラス展開に基づいて、行列式を計算するアルゴリズムを作成しました。
以下の繰り返し関係を取得しました。
T(n) = n(n² + T(n-1))
ウィキペディアで、これにより結果が得られるはずだと読みましたT(n) = O(n!)
が、それを証明する方法がわかりません(直感的ですが)。
式は正しいですが、再帰関係は正しくありません。n²
サブマトリックスを保存または生成する必要がないため、 は必要ありません。
Mij
(n-1) x (n-1)
サブ行列の行列式です。n
したがって、さまざまな行列の行列式を計算する必要がありますn
。したがって、正しい再帰関係はT(n) = n⋅T(n-1) + 2n-1
です。これは次のように単純化されます
T(n) = n ⋅ T(n-1) + 2n-1
= n ⋅ (n-1) ⋅ T(n-2) + n ⋅ (n-1)
= n ⋅ ( (n-1) ⋅ ( (n-2) ⋅ (...) + n-3 ) + n-2 ) + n-1
= 2n-1 + n ⋅ (2(n-1)-1) + n ⋅ (n-1) ⋅ (2(n-2)-1) + ... + n!
< 2 ⋅ n + 2 ⋅ n ⋅ (n-1) + 2 ⋅ n ⋅ (n-1) ⋅ (n-2) + ... + 2 ⋅ n! + n!
= 2 ⋅ (n + n ⋅ (n-1) + ... + n!/2) + 3 ⋅ n!
< 2 ⋅ (n!/(n-1)! + n!/(n-2)! + ... + n!/2!) + 3 ⋅ n!
2⋅n!/k! ≤ n!/(k-1)!
for allによりk ≥ 2
、
n!/(n-1)! + n!/(n-2)! + n!/(n-3)! + ... + n!/2!
≤ n!/(n-2)! + n!/(n-2)! + n!/(n-3)! + ... + n!/2!
≤ n!/(n-3)! + n!/(n-3)! + ... + n!/2!
≤ n!/(n-4)! + ... + n!/2!
≤ ...
≤ n!/2! + n!/2!
≤ n!
など
T(n) = n ⋅ T(n-1) + 2n-1
< 2 ⋅ (n!/(n-1)! + n!/(n-2)! + ... + n!/2!) + 3 ⋅ n!
≤ 2 ⋅ n! + 3 ⋅ n!
= 5 ⋅ n!
= O(n!)
だからあなたのアルゴリズムはO(n!)