算法导论学习总结

    这个学期学习了《算法设计与实践》这门课，主讲老师是王斌老师，这门是以算法导论（CLRS）这本书为教材，对计算机中经常使用到的算法做一个细致的讲解，在学完这门课之后感觉对算法的掌握程度也更上了一个台阶，趁着刚学完知识还没完全忘记，对这门课的知识做一个系统的总结。

算法导论知识梳理

一、函数的增长

    这一章的内容主要是从理论方面来分析算法的时间复杂度，通过算法的时间工作效率对算法的性能进行一种有效的度量。
给出四个渐进符号 $\theta,O,\Omega,o,\omega$,这四种符号的具体定义如下：

$$\Theta(g(n))=\left\{f(n):\exists c_1,c_2,n_0,\forall n\geq n_0,0 \leq c_1g(n) \leq f(n) \leq c_2g(n)\right\}$$ $$O(g(n))=\left\{f(n):\exists c, n_0,\forall n \geq n_0 ,0 \leq f(n) \leq cg(n)\right\}$$ $$\Omega(g(n))=\left\{f(n):\exists c ,n_0,\forall n \geq n_0, 0 \leq cg(n) \leq f(n))\right\}$$ $$o(g(n))=\left\{f(n):\forall c >0 ,\exists n_0>0,\forall n \geq n_0, 0 \leq f(n)<cg(n))\right\}$$ $$\omega(g(n))=\left\{f(n):\forall c>0 ,\exists n_0>0,\forall n \geq n_0, 0 \leq cg(n) < f(n))\right\}$$

通常我们使用这四个符号来刻画算法的运行时间。但是也可以用于刻画算法的其他方面。

未完待续。。。。