1) theory of complexity of computations
计算的复杂性理论
2) computational complexity theory
计算复杂性理论
3) complication of calculus
计算的复杂性
4) complexity
[英][kəm'pleksəti] [美][kəm'plɛksətɪ]
计算复杂性
1.
This paper investigates the complexity of decision problem: for propositional CNF formulas H and F, does there exist a variable (or literal) renaming such that (H)=F? Both MAX(1) and MARG(1) are .
考虑判定问题“对于给定的CNF公式H和F是否存在一个变元(或文字)改名,使得(H)=F?”的计算复杂性。
2.
its complexity is O(nlog2n),Fanally, numerical examples show the effectiveness of this algorithm.
借助快速付立叶变换(FFT),本文给出一种求n阶鳞状因子循环矩阵的逆阵、自反g-逆、群逆、Moore-Penrose逆的快速算法,该算法的计算复杂性为O(nlog2n),最后给出的两个数值算例表明了该算法的有效性。
3.
its complexity is O(nlog_2n),Fanally,numerical examples show the effectiveness of this algorithm.
借助快速傅立叶变换(FFT),给出一种求n阶置换因子循环矩阵的逆阵、自反g-逆、群逆、Moore-Penrose逆的快速算法,该算法的计算复杂性为O(nlog2n),最后给出的两个数值算例表明了该算法的有效性。
5) computational complexity
计算复杂性
1.
An infeasible-interior-point algorithm for a class of complementary problems and its computational complexity;
求解一类互补问题的不可行内点法及其计算复杂性
2.
The computational complexity for F′2|m 1=1, m 2=2|C max of this model is studied.
研究了装配式流水作业排序问题的一个新模型 ,并对该模型相应的排序问题的计算复杂性进行了探讨 ,且证明了其在优化指标为作业排序长度的条件下该问题是NP 完全问题 ,没有多项式时间算法。
3.
This paper explores into the computational complexity of scheduling problem in assembly flow shop.
探讨装配式作业排序问题的计算复杂性，证明了在优化指标为作业排序长度的条件下该问题是ＮＰ－完全问题。
6) computation time complexity
计算复杂性
1.
The algorithm needn t calculate the eigenvalues of the r-circulant matrices, and the computation time complexity of the algorithm is O(nlog_2n) by using FFT.
若用FFT计算,其计算复杂性为O(nlog2n)。
2.
Their computation time complexity are O(mn log 2 mn ).
利用快速傅里叶变换 (FFT)技术 ,给出了计算 (m ,n)型二重 (R ,r) 循环矩阵的全部特征值和两个(m ,n)型二重 (R ,r) 循环矩阵相乘的快速算法 ,证明了它们的计算复杂性均为O(mnlog2 mn
3.
New concepts of elementary r-circulant matrices and their some propertiesare given, It is also proved that the computation time complexity of some related algorithnisis O(log_2n)by using FFT, where n is order number of a matrix.
给出了初等Υ－循环矩阵的新概念，并研究了它们的性质，还利用ＦＦＴ（快速富里叶变换）证明了有并算法的计算复杂性为Ｏ（ｎｌｏｇ＿２ｎ）这里ｎ为矩阵的阶数。
补充资料：计算复杂性理论
| 计算复杂性理论 computational complexity theory 计算机科学中研究数学问题的内在难度的理论。一个问题的难度反映在求解该问题所花费的计算资源的多少之上 ，常用的计算资源有：计算所需的时间，计算所需的存储空间等。对计算复杂性的研究能够使人们弄清被求解问题的固有难度，评价某个算法的优劣，或者获取更高效的算法。 为了研究计算复杂性，首先需要一个计算模型，用以说明哪种操作或步骤是许可的，以及它们的费用是多少。常用的计算模型有图灵机、随机存取机、组合线路等。通过这些计算模型可以研究问题复杂性的上界和下界，或寻求最佳算法。 问题的计算复杂性是问题规模的函数，故对一个问题需要首先定义规模。例如对于矩阵运算，矩阵的阶数可被定义为问题的规模。如果求解一个问题需要的运算次数或步骤数是问题规模N的指数函数，则称该问题有指数时间复杂性 ；如果所需的运算次数是N的多项式函数，则称它有多项式时间复杂性。 一般认为，具有多项式时间算法的问题是易解的问题 ；具有多项式时间复杂性的算法是好的算法。在计算复杂性理论中，把具有多项式时间复杂性的问题类记为P。有许多问题，对它们已知的最好的算法也具有指数时间复杂性。在组合学、图论、运筹学等领域存在大量这样的问题，我们并不知道对这些问题是否存在多项式时间算法。特别需要指出的是，在现实中有一大类这样的问题，它们的计算复杂性具有等效性，如果能用多项式时间解决它们当中的一个问题，则它们全部都能用多项式时间求解。这样的问题类称为NP-完全问题类。关于NP-完全问题类的研究是计算复杂性理论中的一个难点。 对于某个具体问题，其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立 。证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多。 算法设计与分析是计算机科学的重要组成部分，从计算复杂性的角度看，算法设计与分析的主要任务就是建立问题复杂性的上界。设n表示问题的规模，以下是几个常见的问题及其复杂性上界：①n维快速傅里叶变换需要O（nlogn）次算术运算 。② n位数的乘法在多带图灵机上需时 O （nlognloglogn）。③n阶方阵乘法需要O（n2.496）次算术运算。④n位数是否为素数的判别需时O（nclogloglogn）。 寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，这是不可能的，因此，确定计算复杂性下界只能靠理论证明。常用的确定下界的方法是对角线论证，使用这种方法可证明某些问题是不能用算法求解的。 |
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条