算法介绍

●算法概述

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。算法是独立存在的一种解决问题的方法和思想。

​

●算法的特性

1. 有穷性：一个算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成

2. 确定性：算法中每条指令必须有确切的含义，不会产生二义性，对于相同的输入只能得出相同的输出。

3. 输入：一个算法有零个或多个输入。

4. 输出：一个算法具有有一个或多个输出，这些输出是与输入有着某种特定关系的量。

5. 可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

●算法设计目标

• 正确性：算法能够正确的执行预先规定的功能和性能要求。
• 可读性：有助于人对算法的理解。
• 健壮性：有很好的容错性，对不合理的数据进行检查。
• 高效率与低存储量需求：高效率、低存储。算法的效率主要是指算法的执行时间，算法的存储量是指算法执行过程中所需要的最大存储空间。

【算法设计主要考虑可解算法的设计，而算法分析则研究和比较各种算法的性能和优劣，而算法的时间复杂度（算法时间效率）和空间复杂度（算法空间效率）是算法分析的两个主要方面】

●时间复杂度

恶补一下函数渐进的界

函数渐进的界

大O符号

定义：

设f 和g是定义域为自然数集N上的函数. 若存在正数 c 和 n0，使得对一切 n> n0有 0 <= f(n) <= c g(n) 成立, 则称 f(n) 的渐近的上界是 g(n)， 记作 f (n) = O(g(n))

例
设f(n) = n2 + n
f(n)=O(n2)，取 c = 2，n0 =1即可
f(n)=O(n3)，取 c = 1，n0 =2即可

解释

f (n) = O(g(n)) ，f(n)的阶不高于g(n)的阶

时间复杂度

    时间复杂度是指该算法中所有语句（指令）的频度(语句在算法中被重复执行的次数)之和（T(n)），n指的是问题规模，当n趋向于无穷大时，T(n)的数量级就称为算法的时间复杂度，T(n)=O(n)。所以称渐进时间复杂度，简称时间复杂度。说的简单一点就是针对指定基本运算,计数算法所做运算次数。 

常用的时间复杂度所耗费的时间从小到大依次是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

基本运算

   比较, 加法, 乘法,, 交换… 

输入规模：

   输入串编码长度，通常用下述参数度量：数组元素多少，调度问题的任务个数，图的顶点数与边数等. 

针对于相同输入规模的不同实例，算法的基本运算次数也不一样，可定义两种时间复杂度。

最坏情况下的时间复杂度 W(n)

   算法求解输入规模为 n 的实例所需要的最长时间 

平均情况下的时间复杂度 A(n)

   在给定同样规模为 n 的输入实例的概率分布下，算法求解这些实例所需要的平均时间 

设 S 是规模为 n 的实例集实例 I∈S 的概率是 PI算法对实例 I 执行的基本运算次数是 t

注意：
在某些情况下可以假定每个输入实例概率相等

●空间复杂度

   程序运行从开始所需要的存储量。S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。 

一般情况下，一个程序在机器上执行时，除了需要存储程序本身指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。

【空间复杂度先了解即可】

●算法的表示

   算法采用的是伪码表示 

常用伪码描述语句

【注意：伪码不是程序代码，只是算法的主要步骤，伪码通过编程语言去实现】

例

●递推方程

设序列 a0, a1, …, an, …, 简记为 {an}, 一个把an与某些个ai (i<n) 联系起来的等式叫做关于序列 {an} 的递推方程，是设计算法的关键。

迭代法

迭代法是用来求解递推方程的

• 不断用递推方程的右部替换左部
• 每次替换，随着 n 的降低在和式中多出一项
• 直到出现初值停止迭代
• 将初值代入并对和式求和
• 可用数学归纳法验证解的正确性

五大基本算法

• 分治算法
• 动态规划
• 贪心算法
• 回溯算法
• 分支限界法

【想了解这五大基本算法的，WX搜索”Java长征记“，里面有详细介绍。保证你看后有所收获！！！】

干货

想了解更多的算法、数据结构以及关于Java基础知识的关注公众号”Java长征记“