1、算法是什么:通常来说,算法指的是解决问题的一种方法或过程,一个给定的算法可以用来描述解决问题的一个求解方案。
2、算法设计方法:
(1)分治法:将问题实例划分为许多小的实例,对小的实例进行递归求解,再合并这些解。
(2)减治法:通过建立问题给定实例的解和同样问题比较小实例的解的关系,再采用递归或非递归求解 。
(3)变治法:三个方法将问题变化成更易求解的形式,把问题转变成另一个可用已知算法求解的问题;把问题的实例变化成相同问题的另一个实例;将一个问题的实例表现变为同样实例的另一种表现。
(4)蛮力法:通过一般方法直接解决问题。
还有贪婪技术、动态规划等算法设计方法。
3、算法的描述方法:
流程图表示、自然语言表示、伪代码表示、程序设计语言表示
4、算法分析:
算法分析指的是估量算法或程序的效率,即估算算法消耗的资源。
(1)算法好坏衡量的标准:正确性(无语法错误、能得到正确结果)、可读性(易于阅读、理解、修改)、健壮性、时间效率和存储需求。
(2)分析的方法:实测法(使用不同算法分析同一个问题,测量算法代码的消耗)、事后估计法
(3)分析的内容:
时间复杂度:算法的时间效率可以表示为T(n)=O(f(n)),表示消耗多少时间
空间复杂度:表示S(n)=O(f(n)),表示占用多少内存空间