计算科学 - 如何计算给定算法的复杂度 - 吾爱随笔录

如何计算给定算法的复杂度

计算科学算法复杂

2021-12-24 06:34:29

我给出了以下算法：

输入：正则矩阵 $A \in \mathbb R^{n,n}$ 输出：A = LU 的 LU 分解

对于k = 1，. . . , n做

对于j = k，. . . , n做 $r_{kj} = a_{kj} − \sum_{i=1}^{k-1} l_{ki}r_{ij}$

结束

对于i = k + 1，. . . , n做

$l_{ik} = (a_{ik} − \sum_{j=1}^{k-1} l_{ij}r_{jk})/r_{kk}$

结束

给定每个基本操作 (+,-,*,/) 的成本为 1，如何得出该算法的复杂度为2/3n^3 - 1/2n^2 - 1/6n？我真的很想了解这种复杂性的封闭公式是如何得出的。

1个回答

为了计算 $r_{kj}$ ，你需要做 $k-1$ 乘法和 $k$ 加法，总共 $2k-1$ 操作。你需要这样做 $j=k...n$ ， IE $n-k$ 次共 $(n-k)(2k-1)$ 计算所有的操作 $r_{kj}$ 对于给定的 $k$ . 然后你需要为所有人这样做 $k$ 从 1 到 $n$ ，所以第一个循环的成本是

\sum_{k = 1}^{n} (n - k) (2 k - 1) = n \sum_{k = 1}^{n} (2 k - 1) - \sum_{k = 1}^{n} k (2 k - 1) = 2 n \sum_{k = 1}^{n} k - \sum_{k = 1}^{n} 1 - 2 \sum_{k = 1}^{n} k^{2} + \sum_{k = 1}^{n} k = 2 n \frac{1}{2} n (n + 1) - n - something + \frac{1}{2} n (n + 1) .

$\sum_{k=1}^n (n-k)(2k-1) = n\sum_{k=1}^n (2k-1) - \sum_{k=1}^n k(2k-1) \\ = 2n\sum_{k=1}^n k - \sum_{k=1}^n 1 - 2 \sum_{k=1}^n k^2 + \sum_{k=1}^n k \\ = 2n\frac 12 n(n+1) - n - \text{something} + \frac 12 n(n+1).$ 您需要查找第三个总和的公式：我忘记了它的确切值，但它与

n^{3}

$n^3$ .

您可以对算法的第二个内部循环进行相同的计算。

其它你可能感兴趣的问题

上一篇与 svm 优化相关的困惑下一篇确定计算要求