渐近符号、递归及解法
渐近符号、递归及解法
这节课，大概讲了一些符号的用法，毕竟偏数学化，没有涉及算法的知识。我也参考了下别人的笔记，本节课内容不是太多，主要是符号表示和递归的复杂度求解方式，下面分2个部分讲解。
一， 渐进符号
（1） O符号 ， f(n) = O(g(n)) ，表示 f(n)的复杂度最多与g(n)一个 数量级 ，即小于等于。
（2） Ω符号，f(n) = Ω(g(n))，f(n)的复杂度最少与g(n)一个 数量级 ，即大于等于。
（3） o符号，f(n) = o(g(n))，表示f(n)的复杂度要比g(n)的 数量级 小，即小于。
（4）ω符号，f(n) = ω(g(n))，表示f(n)的复杂度要比g(n)的 数量级 大，即大于。
（5） Θ符号， (n) = Θ(g(n))，表示f(n)的复杂度既大于等于g(n)的复杂度，又小于等于g(n)的复杂度，即于g(n)的复杂度相当。
二，三种方式来解递归式
算法设计中经常会用到递归，利用递归式的方法可以清晰地显示算法的整个过程，而对于分析算法的复杂度，解递归式就有了用处。
（1）代换法。
分为三个步骤：a）凭感觉猜，不用关系系数和常数，猜测可能的形式。b） 通过数学归纳法验证第一步才出来的form是否满足条件。c）确定系数和常数。 缺点是并不严格。
（2）递归树。
上一节归并排序的时候有用到过这个方法。
（3）主定理。（ 只对特等的递归式有效，包含三种情况 ）
主定理通常 解决 如下的递归表达式： 递归式描述的是将规模为n的问题划分为a个子问题，并且每个子问题的规模是n/b，这里a和b是正常数。划分原问题和合并 结果的 代价有函数f(n)描述。
现在是不是很累了？休息一下，清凉一夏。
分类: 算法研究
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息