第1章 算法概述-wyg.pptx

第1章算法概述;1.1算法与程序----算法(Algorithm);1.1算法与程序----程序(Program);问题求解(ProblemSolving);1.2算法复杂性分析;算法的时间复杂性;算法渐近复杂性;PracticalComplexity;PracticalComplexity;PracticalComplexity;PracticalComplexity;PracticalComplexity;渐近分析的记号;（3）非紧上界记号o

o(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有n?n0有：0?f(n)cg(n)}

等价于f(n)/g(n)?0，asn??。

教材：如果对于任意给定ε0，都存在正整数n0，使得当n=n0时f(n)/g(n)ε,则称f(n)当n充分大时的阶比g(n)低

（4）非紧下界记号?

?(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有n?n0有：0?cg(n)f(n)}

等价于f(n)/g(n)??，asn??。

f(n)??(g(n))?g(n)?o(f(n));（5）紧渐近界(同阶)记号θ或

θ(g(n))={f(n)|存在正常数c1,c2和n0使得对所有n?n0有：c1g(n)?f(n)?c2g(n)}

教材：同阶记号θ

f(n)=θ(g(n)),f(n)=O(g(n))且f(n)=?(g(n))

;渐近分析记号在等式和不等式中的意义;最优算法;1.3NP完全性理论;1.3NP完全性理论

NP类问题;1.3NP完全性理论

NPC类问题;NP完全问题的近似算法;补充：

递归和非递归算法的数学分析;补充：蛮力法

选择排序和冒泡排序;补充：减治法;补充：排序算法及时间复杂度