gongshi

标签：gongshi begin end 复杂度 times aligned nmk

证明： \(T(n,m,k) \rightarrow O(nmk)\)

输入过程

\(\qquad\)输入的时间复杂度为:

\[\begin{aligned} T_1(n,m,k)= O(n \times k) \end{aligned} \]

dp过程：

\(\qquad\)状态转移方程的时间复杂度为常数项，即\(O(1)\)
\(\qquad\)该过程发生 \(n\times m \times k\) 次，则状态转移的时间复杂度为:

\[\begin{aligned} T_2(n,m,k) &= O(1) \times n\times m \times k \\ &=O(nmk) \end{aligned} \]

故整体的时间复杂度为：

\[\begin{aligned} T(n,m,k)&=T_1(n,m,k)+T_2(n,m,k)\\ &=O(n k)+O(nmk)\\ &=O(nmk) \end{aligned} \]

标签：gongshi,begin,end,复杂度,times,aligned,nmk
From： https://www.cnblogs.com/CLGYPYJ/p/17808174.html