本博文简单介绍了算法的相关概念(包括：算法设计模式、算法性质、描述方式、评价方法等)以及时间复杂度分析。

1 导学

1.1 算法的基本概念

算法设计模式：

  • 暴力求解(Brute force)
  • 分治法(Divide and conquer)
  • 贪婪算法(Greedy approach)
  • 动态规划(Backtracking)
  • 回溯法(Branch and bound)
  • 分支界限法(Randomized algorithm)等

算法：算法是借助计算机解决问题的方法，是有限条确定性指令的序列

算法的性质：输入、输出、确定性、有限性

算法的描述方式：自然语言、数学公式、流程图、伪代码、程序设计语言

算法的评价方法：正确性、有效性、易理解、易实现、通用性

例子：最大公约数
暴力解法：取min(a,b)，从大到小尝试，直到两个数均可被整除。
欧几里得：max%min==0？result=min : result=(max%min和min的最大公约数）

1.2 算法复杂度

算法复杂度分析的三种情形：

  • 最好情形(Best case)
  • 最差情形(Worst case)
  • 平均情形(Average case)

例如：二分查找(Binary search)的时间复杂度，在三种情况依次为Θ(1)、Θ(log2n)、Θ(log2n)

1.2.1 时间复杂度

评价标准：

  • 运行时间
    • 优点：最直接反映
    • 缺点：机器依赖、缺乏解释
  • 运算次数
    • 优点：机器无关、具有解释力
    • 缺点：统计繁琐、规模较大时关键在于增长量级
  • 增长量级

近似表示
@图 1.1 上界|center|500x0
@图 1.2 下界|center|500x0
@图 1.3 同阶|center|500x0

例子：Fibonacci
递归算法：O(2n)

1
2
3
4
public static long GetByRecursion(long n){
	if(n==1||n==2)return 1;
	else return GetByRecursion(n-1)+GetByRecursion(n-2); //递归调用
}

迭代算法：O(n)

1
2
3
4
5
6
7
8
9
public static long GetByIteration(long n){
	long a=1,b=1;
	for(long i=3;i<n;i++){
		long temp=a+b;
		a=b;
		b=temp;
	}
	return b;
}

1.3 算法思维

算法思维：现实问题——>形式化描述——>设计算法——>方案实施——>现实问题

1.1.4 例：交通信号灯