算法分析笔记

第一章

渐进复杂度

函数的渐进性态与渐进表达式:一般来说,当N单调增加且趋于∞时,T(N)也将单

调增加趋于∞。

对于T(N),如果存在函数T'(N),使得当N→ ∞使有(T(N)-T'(N))/T(N) →0,那么我

们就说T'(N)是T(N)当N→ ∞时的渐进性态。

在数学上,T'(N)是T(N)当N→ ∞时的渐进表达式。

例如:3N2+4NlogN+7与3N2。

第2章 递归与分治策略

一、什么是分治法?

对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,

如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。

将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原

来问题的解。

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同

问题,以便各个击破,分而治之。

二、分治法使用条件

该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解;

该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

三、排序

1、插入排序

2、归并排序

3、快速排序

分治策略求解问题可以分为三步:分解;递归地解子问题;组合。有的问题分解难而组合容易,如__快速排序____,有的问题分解容易而组合难,如__归并排序___。

四、最近点对问题

S中的点退化为x轴上的n个点x1, x2, …, xn。用x轴上的某个点m将S划分为两个集合S1和S2,并且S1和S2含有点的个数相同。递归地在S1和S2上求出最接近点对 (p1, p2) 和(q1, q2),如果集合S中的最接近点对都在子集S1或S2中,则d=min{(p1, p2), (q1, q2)}即为所求,如果集合S中的最接近点对分别在S1和S2中,则一定是(p3, q3),其中,p3是子集S1中的最大值,q3是子集S2中的最小值。

算法分析笔记

你可能喜欢

  • 算法设计与分析答案
  • ACM算法
  • 数据结构算法面试题
  • 算法分析与设计期末
  • 数据结构高分笔记
  • Linux系统命令使用详解
  • ACM模板

算法分析笔记相关文档

最新文档

返回顶部