算法概述-Java常用算法

---

1、算法概念

广泛算法定义：算法是模型分析的一组可行性的、确定的和有穷的规则。

经典算法特征：有穷性、确切性、输入、输出和可行性。

常用的算法包括递推、递归、穷举、贪婪、分治、动态规划和迭代等。

2、算法相关概念

算法与公式：
公式是一种高精度的计算方法，可以认为就是一种算法；而算法并不一定是公式。

算法与程序：
算法和程序是不同的。程序设计语言是算法实现的一种形式，也就是一种工具。比较流行的程序设计语言C、C++、Java、Python 等。

算法与数据结构：
数据结构是数据的组织形式，可以用来表示特定的对象数据。数据结构是算法实现的基础。

数据结构 + 算法 + 程序设计语言 = 程序
注意：算法是解决问题的一个抽象方法和步骤，同一算法在不同的语言中具有不同的实现形式，这依赖数据结构和程序设计语言的语法结构。

3、算法的性能评价

• **时间复杂度：**通常所说的算法执行所需要耗费的时间，时间越短，算法越好。

• **空间复杂度：**算法程序在计算机中执行所需要消耗的存储空间。

4、算法应用归纳

1、并行算法
并行算法就是用多台处理机 联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题，然后使用多台计算机同时求解它，从而最终求得原问题的解。
划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法、破对称法等都是常用的设计并行算法的方法

2、遗传与进化算法
遗传算法（Genetic Algorithm，GA）和进化算法（Evolutionary Algorithms，EA）是科学交叉的结果。遗传与进化算法根据生物的遗传、进化和变异的特性，通过模拟自然演化的方法来得到最优解。

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

进化算法，或称“演化算法”（evolutionary algorithms）是一个“算法簇”，尽管它有很多的变化，有不同的遗传基因表达方式，不同的交叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，但它们产生的灵感都来自于大自然的生物进化。与传统的基于微积分的方法和穷举法等优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性，能够不受问题性质的限制，有效地处理传统优化算法难以解决的复杂问题。

3、量子算法
量子物理学的发展是近代物理学领域的最大突破，其提出了一系列颠覆性的概念和方法。量子物理学发展，使其迅速与信息论和计算相结合，产生了量子信息技术和量子计算。量子计算是一种依照量子力学理论进行的新型计算，量子计算的基础和原理使其能够大大超越传统的图灵机模型的计算机。
已经发展的量子算法包括量子Shor算法、Grover搜索算法、Hogg搜索算法等