【算法】常见算法分类和思想

我们在实际应用中，对一个问题会有不同的解题思路，比如我们在读书时候，往往对一道数学题目会有多种解题方法，可能有些方法比较简单，有些方法比较复杂，步骤较多。所以找到一个合适的方法可以更快更好的去解决问题。在程序应用中，我们也会有不同的算法去解决问题。

算法分类分为：

1.基础算法：包括字符串，数组，正则表达式，排序，递归等。

2.数据结构：堆，栈，队列，链表，矩阵，二叉树等。

　 3.高级算法：贪心算法，动态规划等。

根据问题的不同，一般可以有以下算法思想去解决问题：

　　递推算法:

　　　　　递推法，就是从已知的结果和条件出发，利用特定关系分解中间步骤得出推论，逐步推导而得到结果。递推算法分为顺推和逆推两种。

　　　　　递推与递归的比较

　　　　　相对于递归算法,递推算法免除了数据进出栈的过程，也就是说不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。

　　分治算法：

　　　　分治，顾名思义，分而治之，分治算法是一种化繁为简的算法思想，往往应用于计算步骤比较复杂的问题，通过将问题简化而逐步得到结果。常用场景就是求出最轻、最重问题（在一堆形状相同的物品中找出最重或最轻的那一个，二分查找，快速排序和归并排序，分治算法也是许多高效算法的基础，比如快速傅立叶变换算法和 Karatsuba 乘法算法。

　　概率算法：

　　　　概率算法是在程序执行过程中利用概率统计的思路随机地选择下一个计算步骤，在很多情况下，算法在执行过程中面临选择时，随机性选择比最优选择省时，因此概率算法可以在很大程度上降低算法的复杂度。

　　　　概率算法大致分类如下：

　　　　　　1.贝叶斯分类算法。

　　　　　　2.蒙特卡罗（Monte Carlo）算法。

　　　　　　3.拉斯维加斯（Las Vegas）算法。　　

　　　　　　4.舍伍德（Sherwood）算法。

　　　　　　5.随机数算法。

　　　　　　6.近似算法。

　　　　　　7.机器学习算法中的的一些概率方法。

递归算法:

　　　　递归算法是指一种通过重复将问题分解为同类的子问题而解决问题的方法。具体来说就是就是一个函数或者类方法直接或间接调用自身的一种方法。

　　　　递归的优点：

　　　　　　1.实现简单，代码可读性好。

　　　　　　2.在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单方便。

　　　　递归的缺点：

　　　　　　1.当需要处理的数据规模比较大的时候，递归算法入栈、出栈较多，每一次函数调用会在内存栈中分配空间，系统效率会很低，递归深度太深的话容易发生栈溢出。

　　　　　 2.容易重复计算。

拆解问题，一个大问题可以被拆分等价于小问题的循环重复
递归返回阶段，上一次自调用的结果是下一次调用的初始值。
边界条件，就是明确递归什么时候结束，终止条件是啥，不能无限制地调用本身，必须有个出口。

　　　递归算法的应用：

　　　　　　1.汉诺塔问题。

　　　　　　2.排列组合。
　　　　　　3.归并排序。

　　　　　　4.斐波那契数列（Fibonacci）数列。

　　　　　　5.二分法递归查找。

　　递归算法的优化：

　　　　　　1.减少重复计算。

　　　　　　2.尾递归。

　　递归与循环：

　　　　递归与循环都是可以处理重复任务的问题，循环没有函数调用开销，但有时使用循环的算法并不会那么清晰地描述解决问题步骤。而递归常常会带来性能问题，特别是在求解规模不确定的情况下。

　　下面看用递归来实现斐波那契数列

$stratTime = microtime(true);
$startMemory = memory_get_usage();

function _fbnq($n){
    if($n <= 0){
        return 0;
    }
    if($n == 1 || $n == 2){
        return 1;
    }
    return _fbnq($n - 1) + _fbnq($n - 2);
}

$arr= [];
for ($i=1;$i<=26;$i++){
    array_push($arr,_fbnq($i));
}
echo implode($arr,',').PHP_EOL;
$endTime = microtime(true);
$runtime = ($endTime - $stratTime) * 1000; //将时间转换为毫秒
$endMemory = memory_get_usage();
$usedMemory = ($endMemory - $startMemory) / 1024;
echo "运行时间: {$runtime} 毫秒".PHP_EOL;
echo "耗费内存: {$usedMemory} K".PHP_EOL;

执行结果

[root@oa-dev bin]# php  index.php
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393
运行时间: 1584.3920707703 毫秒
耗费内存: 1.359375 K

上面函数也可以优化成尾递归，要提供两个累积变量。减少调用栈(call stack)。同时编写递归代码适合要先考虑退出递归的条件。

优化写法：

$stratTime = microtime(true);
$startMemory = memory_get_usage();

function fibonacci($n, $n1, $n2) {
    if($n <= 0) {
        return 0;
    }
    if($n <= 1) {
        return $n2;
    }
    return fibonacci($n - 1, $n2, $n1 + $n2);
}

$arr= [];
for ($i=1;$i<=26;$i++){
    array_push($arr,fibonacci($i,0,1));
}
echo implode($arr,',').PHP_EOL;
$endTime = microtime(true);
$runtime = ($endTime - $stratTime) * 1000; //将时间转换为毫秒
$endMemory = memory_get_usage();
$usedMemory = ($endMemory - $startMemory) / 1024;
echo "运行时间: {$runtime} 毫秒".PHP_EOL;
echo "耗费内存: {$usedMemory} K".PHP_EOL;

　　执行结果

[root@oa-dev bin]# php  index.php
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393
运行时间: 0.53906440734863 毫秒
耗费内存: 1.359375 K

穷举算法:

　　　　穷举也叫暴力破解法，在数学上也把穷举法称为枚举法，就是在一个由有限个元素构成的集合中，把所有元素一一枚举对比研究的方法。比如要找一个集合中最大的数，就把这个集合中的所有数都枚举一遍，通过相互比较找出最大的那个数。

　　使用穷举法解决问题，基本上就是以下两个步骤：

确定问题的解（或状态）的定义、解空间的范围以及正确解的判定条件；
根据解空间的特点来选择搜索策略，逐个检验解空间中的候选解是否正确；