
什么是算法?
算法是在有限的输入条件下,用有限的步骤来解决特定问题的一种过程。
这些算法可以用不同的方式进行分类。它们是:
1)实现方法
2)设计方法
3)其他分类
本文讨论了每种分类方法的不同算法。
按实现方法分类:在这种分类中,可以将算法命名为三个主要类别。他们是:
1)递归或迭代:递归算法是一次又一次地调用自身直到达到基本条件的算法,而迭代算法则使用循环和/或数据结构(如堆栈,队列)来解决任何问题。每个递归解决方案都可以实现为迭代解决方案,反之亦然。
2)精确或近似:能够为任何问题找到最佳解决方案的算法称为精确算法。对于所有这些问题,无法找到最优化的解决方案,则使用一种近似算法。近似算法是将结果作为一个问题的子结果的平均结果的算法类型。
3)串行算法,并行算法或分布式算法:在串行算法中,一次执行一条指令,而并行算法是将问题分为子问题并在不同处理器上执行的算法。如果并行算法分布在不同的计算机上,则它们称为分布式算法。
按设计方法分类:在这种分类中,可以将算法命名为三个主要类别。他们是:
1)贪婪法:在贪婪法中,每一步都决定选择局部最优,而不考虑未来的后果。
2)分而治之:分而治之策略包括将问题划分为子问题,递归解决它们,然后将它们重新组合以得到最终答案。
3)动态编程:动态编程的方法类似于分而治之。区别在于,只要我们具有相同结果的递归函数调用,便不再尝试再次调用它们,而是尝试将结果存储在表形式的数据结构中并从表中检索结果。因此,降低了总体时间复杂度。“动态”是指我们动态决定是调用函数还是从表中检索值。
其他分类:除将算法划分为上述大类外,还可以将算法划分为其他大类,如:
1)随机算法:为更快的解决方案做出随机选择的算法称为随机算法。
2)按复杂度分类:根据获得输入大小的任何问题的解决方案所花费的时间进行分类的算法。此分析称为时间复杂度分析。