《计算机算法设计与分析》第一章：算法概述

第一章 算法概述

        1.1 算法复杂性分析

                公共标准：渐进时间复杂度

                （1）大O表示法：

                        

                        例如：

                                

                        大O表示法和前面的最坏时间复杂度的区别在于：大O表示法表示的更为简洁，

                        而最坏时间复杂度相对就比较繁琐，虽然繁琐但是准确。

                        练习：

                                

                        

                        运算法则：

                                

                                O(f) * O(g) = O(f*g) 适用的情况比如：循环嵌套

                                O(f) + O(g) = O(f + g) 适用的情况是： 一个程序中有多个模块，每个模块

                                算法的实践复杂度的阶都是一样的。

                                

                （2）大 ' 欧米伽 ' 表示法

                        

                        近似法比较原则：

                                

                        习题例子：

                                

                                

                                 

        1.3 NP完全理论

                （1）

                        

                （2）根据时间复杂度解决问题的分类：