计算复杂性

1066 浅谈计算复杂性理论

任忠

乌鲁木齐石化公司计控中心

摘 要：本文阐述了计算复杂性理论的产生、定义、研究内容和发展。

关键词：算法分析；计算复杂性；起源；发展

1. 计算法复杂性理论的起源

在几千年的数学发展中，人们研究了各式各样的计算，创立了许多算法。但是，以计算或算法本身的性质为研究对象的数学理论，却是在20世纪30年代才发展起来的。

1936年， 为了讨论对于每个问题是否都有求解算法，数理逻辑学家提出了几种不同的计算模型的定义。K.Godel和S.C.Kleene等人创立了递归函数论，将数论函数的算法、可计算性刻画为递归可枚举性。A.M.Turing和E.L.Post提出了理想计算机的概念，将问题算法可解性刻画为在具有严格定义的理想计算机上的可解性。40年代以后，随着计算机科学技术的发展，研究的焦点从理论可计算法转移到现实可计算性上。人们不仅需要研究理论上的、原则上的可计算性， 还要研究现实的可计算性，即研究计算一个问题类需要多少时间，多少存储空间，研究哪些问题是现实可计算的，哪些问题虽然原则上可计算，但由于计算的量太大 而实际上无法计算等。因而一般算法设计方法研究和对一类问题算法解的难度分析便成为计算机科学的热点。此后，计算复杂性的研究等不断有所发展。由此产生了算法学和计算复杂性理论等新兴研究领域。

计算复杂性大的进展始于50年代末、60年代初，当时在美国有两个并行的中心，一个是通用电气公司设立于纽约州Schenectady的研究实验室，核心人物是J.Hartmanis和R.Stearns。1964年11月，他们在普林斯顿举行的第五届开关电路理论和逻辑设计学术年会上发表了论 文"Computational Complexity of recursivese quences"，论文中首次使用了"计算复杂性"这一术语，由此开辟了计算机科学中的一个新领域，并为之奠定了理论基础。他们两人是1993年度 图灵奖获得者。另一个中心是麻省理工学院MIT，在那里，加州大学伯克利分校著名的计算机科学家Manuel Blum与前述两人互相独立地进行着相关问题的研究，并完成了他的博士论文："Amachine independent theory of the complexity of recur-

随机矩阵理论的计算复杂性

随机矩阵理论是研究随机矩阵的性质和行为的数学分支。它在诸多领域中有广泛的应用，包括统计物理、金融数学、通信工程等。本文将重点讨论随机矩阵理论中的计算复杂性问题。

一、简介

随机矩阵是由随机变量构成的矩阵，其元素的取值具有随机性。随机矩阵理论的计算复杂性主要关注以下几个方面：

1. 期望值的计算

对于一个随机矩阵，往往需要计算其期望值，即所有可能取值的加权平均值。而计算期望值通常需要进行大量的矩阵乘法、求逆等运算，导致计算复杂性较高。

2. 特征值的计算

随机矩阵的特征值是其最重要的性质之一。计算随机矩阵的特征值需要使用特征值分解、幂迭代等算法，这些算法的时间复杂性通常与矩阵的维度有关，尤其是在大维度矩阵的情况下，计算特征值需要消耗大量计算资源。

3. 矩阵近似

随机矩阵的计算复杂性还涉及到矩阵的近似问题。由于随机矩阵的维度往往很大，直接计算是不现实的。因此，常常需要寻找适当的矩阵近似方法，以降低计算复杂性。 二、计算复杂性的分析

为了分析随机矩阵理论中的计算复杂性，我们可以从以下几个角度进行讨论：

1. 复杂性的理论界限

根据计算复杂性理论，我们可以对特定问题的计算复杂性进行界定。例如，计算一个n×n矩阵的期望值的计算复杂性被界定为O(n^3)。这样的理论界限可以帮助我们评估计算难度和效率。

2. 算法的设计与改进

随机矩阵理论的计算复杂性问题也可以通过设计和改进算法来解决。例如，在计算期望值时，可以利用分块矩阵的性质来加速计算。在求解特征值时，可以采用迭代方法来减小计算量。这些方法可以提高计算的效率，降低计算复杂性。

3. 数值方法与计算机实现

为了应对计算复杂性的挑战，我们可以利用数值方法和计算机实现来加速计算过程。例如，使用数值逼近的方法求解特征值和期望值，采用并行计算的技术提高计算速度。这些方法可以在实践中降低计算复杂性。

三、应用与展望

随机矩阵理论的计算复杂性问题对于各个领域的研究和应用都具有重要意义。在统计物理中，它可以用于描述复杂系统的行为；在金融数学中，它可以用于风险管理和投资决策；在通信工程中，它可以用于信道容量的分析等。

第三章计算复杂性理论

主要内容

3.1 Turing机

3.2 计算复杂性理论

3.3 NP完全性理论的基本概念

3.4 NP完全性证明

3.5 用NP完全性理论分析问题

3.6 NP难度

3.1 Turing机

一、Turing机的定义

1. 基本模型

2. 基本Turing机的变种

单向带的Turing机

k条带的Turing机

非确定型的Turing机

二、Turing机模型的等价性

1. 单向带Turing机与基本Turing机等价

2. k条带的Turing机与基本Turing机等价

3. 非确定型Turing机与基本Turing机等价一、Turing机的定义

1. 基本模型双向无限带的Turing机M = , 其中Q 有穷状态集有穷带字符集输入字符集B 空白字符, B－q0初始状态, q0QF 终结状态集, FQ,qY,qNF: (Q－F)×Q××{L,R} 状态转移函数

(ID)

1q2表示此刻Turing机的FSC处于状态q,读写头

指在串2的第一个字符.

例如Turing机M的某时刻的状态转移函数是

(q,xi) = (p,Y,L)

带上的字符串为x1x2...xi...xn, 读写头指向字符xi, 则

它的瞬间描述是:

x1x2...xi-1qxi...xn┣x1x2...xi-2pxi-1Yxi+1...xn┣表示由左边的ID一步达到右边的ID

┣*表示由左边的ID经有限步达到右边的ID

被M接受的语言记作L(M)，是*上的字的集合.

当这些字左端对齐方格1放在带上,M处于状态q0,M的

带头指向方格1时, 经过有限步M将停机在接受状态qY,

即

L(M)={|*,1,2*(q0⊢*1qY2)}

如果字不是L(M)中的字, M可以不停机或停机在拒斥状

态qN.

例1 L={0n1n|n1}, 设计接受L的Turing机如下:

M =

Q = {q0,q1,q2,q3,qY},

如果一个算法在平均情况下的计算时间复杂性

算法的时间复杂度也就是算法的时间度量，记作：t(n) = o(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。t(n)表示一个算法中的语句执行次数称为语句频度或时间频度。

时间频度t(n)中，n称为问题的规模，当n不断变化时，时间频度t(n)也会不断变化。

资料开拓：

常见的时间复杂度量级有：

常数阶$o(1)$；

线性阶$o(n)$；

平方阶$o(n^2)$；

立方阶$o(n^3)$；

对数阶$o(logn)$；

线性对数阶$o(nlogn)$；

指数阶$o(2^n)$。

1、常数阶$o(1)$，表示该算法的执行时间（或执行时占用空间）总是为一个常量，不论输入的数据集是大是小，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是o(1)。

2、线性阶$o(n)$，则表示一个算法的性能可以随着输出数据的大小变化而线性变化。

3、平方阶$o(n^2)$，表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话，算法的性能将会变为立方阶$o(n3)$。

4、指数阶$o(2^n)$，则表示一个算法的性能可以随着输出数据的每次减少而减小两倍，典型的方法就是裴波那契数列的递归计算同时实现。