您的位置： 文档网所有分类高等教育工学 算法分析笔记

算法分析笔记

第一章

渐进复杂度

函数的渐进性态与渐进表达式：一般来说，当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中的最小值。

算法分析笔记

第1页

你可能喜欢

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

算法分析笔记的相关文档搜索

算法分析笔记相关文档

最新文档

返回顶部