Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 可计算性简明纲要(7)
发信站: 哈工大紫丁香 (2001年06月14日15:42:42 星期四), 站内信件

第三节 多项式时间的算法
记号 如果算法的时间代价为多项式函数,则称算法是多项式
时间的,记作PTIME.如果算法的空间代价是多项式函数,则称
算法是多项式空间的,记作PSPACE.
注解 这里的写法不严格.实际上,多项式时间(空间)内可以
判定的问题的集合为PTIME(PSPACE).为了方便,在这里混合
使用.
定理 求解最大公约数的Euclidean算法,以及扩展Euclidean
算法属于PTIME.
定理 快速乘方算法属于PTIME.
定理 求解线性方程组的Gauss消去法属于PTIME.
定理 求解图的最小生成树的Kruskal算法属于PTIME.
定理 求解图的最小生成树的Prim算法属于PTIME.
定理 求解图中两顶点之间最短路的Dijistra算法属于PTIME.
定理 求解最大匹配的Hungarian算法属于PTIME.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]