能达丰富性计算的计算复杂性

    $$ $N$ 步能达丰富性计算,即 $N$ 步能达域 $R_{r,N}$ 的体积计算，可以采用博文“The volume computing of a special polyhedron in n-dimensions space”(http://blog.sciencenet.cn/blog-3343777-1062307.html)的直接计算，或者采用博文“线性离散系统的能控丰富性的一个简化计算式”(http://blog.sciencenet.cn/blog-3343777-1066509.html)的递推计算。对线性系统 $\varSigma(A,B)$ ,两种计算方法的计算复杂性为（以计算一次 $n\times n$ 的矩阵行列式值为单位）：

   1. 直接计算的行列式的计算次数为：

$=\frac{\left(N\times r\right)!}{\left(N\times r-n\right)!n!}$

   2.递推计算的行列式的计算次数小于或等于

$\leq\frac{r\times\left(N\times r-r\right)!}{\left(N\times r-r-n+1\right)!(n-1)!}+1$

其中 $n$ $$ 和 $r$ 分别为系统的状态向量和输入向量的维数。即两种计算方法的计算复杂性分别为关于 $N$ 的多项式时间 $\mathcal{O}(N^{n}r^{n})$ 和 $$ $\mathcal{O}(\left(N-1\right)^{n-1}r^{n})$ ,博文“线性离散系统的能控丰富性的一个简化计算式”(http://blog.sciencenet.cn/blog-3343777-1066509.html)的递推计算方法至少降低了1阶的多项式时间复杂性。

     对单输入系统（即 $r=1$ )，两种算法的计算时间为

$\frac{N!}{\left(N-n\right)!n!}$ 和 $\frac{(N-1)!}{\left(N-n\right)!(n-1)!}+1$

可简记为 $\mathcal{O}(N^{n})$ 和 $\mathcal{O}(\left(N-1\right)^{n-1})$ .