MozhuCY's blog.

算法设计

字数统计: 451阅读时长: 1 min
1970/01/01 Share

算法的概念

算法是求解一类问题的任意一种特殊方法.较严格的说法是对特定问题的求解步骤的一种描述.他是指令的有限序列,此外算法还有以下5个特征

  • 输入:算法有0>=个输入量
  • 输出:算法有1>=个输出量
  • 确定性:算法的每一条指令都有确切的定义,无二义性
  • 能行性:算法的每一条指令都可以通过已经实现了的基本运算执行有限次来进行实现
  • 有穷性:算法必须总能在有限的步骤以后停止

而描述算法的几种方法包括了自然语言,流程图,伪代码,程序设计语言

算法分析基础

算法的复杂度就是运行一个算法所需要的时间于空间,一般比较好的算法都具有以下几个特征,正确性,简明,效率,优解.
大O符号,设非负函数f(n)和g(n),如存在c>0和n0,使得当n0<=n时,有f(n) <= cg(n),则记为f(n) = O(g(n))
Omega符号,设非负函数f(n)和g(n),如存在c>0和n0,使得当n0<=n时,有f(n) >= cg(n),则记为f(n) = Omega(g(n))

时间复杂度分为O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)
指数时间算法O(2^n) < O(n!) < O(n^n)

分治法

将一个大问题分解为若干个小问题,然后求解子问题,若子问题规模还是很大无法求解,还可细分,直到问题足够小,能够求解,最后将子问题组合成原始问题的解.一般通过递归实现,

CATALOG
  1. 1. 算法的概念
  2. 2. 算法分析基础
  3. 3. 分治法