7月 21

汉诺塔问题时间复杂度推导

汉诺塔问题 汉诺塔(台港:河内塔)(Tower of Hanoi)是根据一个传说形成的数学问题[1]https://zh.wikipedia.org/wiki/汉诺塔: 有三根杆子A,B,C。A杆上有 N 个 (N>1) 穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆: 每次只能移动一个圆盘; 大盘不能叠在 … Continue reading

7月 09

用主定理解阶乘递归算法的复杂度

上一篇提到,并非所有递推关系式都可应用支配理论。那么,递归求阶乘的算法可以用吗? 递归求阶乘算法 算法如下 计算过程是 $1 \times 2 \times 3 ... \times n$,基本能直接看出来时间复杂度是 $\ O(n)$。 用主定理求解 在 CSDN 上有一篇文章[1]https://blog.csdn.net/weixi … Continue reading

7月 09

二分查找的时间复杂度为什么是O(logn)

直接推导 设问题规模为 $n$,需要 $t$ 次查找,由二分查找的过程可知,每一次查找问题规模减半,最差情况下,直到问题规模为 1 时才找到或者仍未找到,因此可知: $$n \times \left(\frac{1}{2}\right) ^t = 1$$ 则: $$2^t = n$$ 两边取 $\log$,得 $$t = \log_{2} … Continue reading

7月 06

IT服务领域术语总结

概念 ITSM IT服务管理(ITSM)是一套帮助企业对IT系统的规划、研发、实施和运营进行有效管理的方法,是一套方法论。ITSM起源于ITIL(IT Infrastructure Library,IT基础架构标准库)[1]百度百科 IT服务管理。 ITIL ITIL是CCTA(英国国家电脑局)于1980年开发的一套IT服务管理标准库。它 … Continue reading

12月 29

计算理论实验--CFG是P成员

计算理论第二个实验,比第一个复杂,本机测试通过,可是ACM上总是说我的结果是错误的。郁闷中..   算法是动态规划,按照书上的伪码描述写出代码,不过还不理解为什么算法可行。关于伪码描述,可以在这里查看:CFG是P成员。 Problem description 上下文无关文法CFG G是否派生某个串W。采用动态规划(Dynamic … Continue reading

12月 29

计算理论实验—ADFA的可判定性

计算理论实验要求在ACM系统提交,头一次用ACM做实验,本机测试对的提交之后却得到错误的结果,相当的郁闷,不过还好,后来在同学的帮助下解决了,顺利AC。   实验题目: ADFA={<B,w>|B是DFA,w是串,B接收w},证明:ADFA是可判定的。 编写一个算法/程序,对于给定的输入<B,w>,可以判 … Continue reading