||
能达丰富性计算的计算复杂性
$$ $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})$ .
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-2 03:25
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社