算法导论知识点总结

算法的知识点总结

算法的知识点非常广泛，涉及到数学、计算机科学、逻辑学等多个领域。本文将从算法的基本概念、常用算法思想、数据结构和算法的关系以及一些常用的算法进行总结介绍。

一、算法的基本概念

1. 算法的定义

算法是一种解决问题的方法或技巧，它是一个有序的、确定性的操作序列，用来解决特定的问题或完成特定的任务。算法可以描述为一系列的步骤，每个步骤都能够被清晰地描述，并且能够按照一定的顺序执行。

2. 算法的特性

（1）输入：算法需要接受一些输入数据来解决问题。

（2）输出：算法需要产生一个输出来解决问题。

（3）确定性：算法的每一步骤都必须是明确的，没有二义性。

（4）有限性：算法必须在有限步骤内结束。

3. 算法的评价标准

（1）时间复杂度：衡量算法执行所需的时间的指标，通常使用大O表示法来描述。

（2）空间复杂度：衡量算法所需的空间资源的指标，通常使用占用空间的增长率来描述。

二、常用算法思想

1. 贪心算法

贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望通过局部最优解最终达到全局最优解。贪心算法通常适用于解决最优化问题，但不能保证一定能得到全局最优解。例如，找零钱时，可以采用贪心算法，选择面值最大的硬币，直到找零完成。

2. 动态规划

动态规划是一种具有重叠子问题和最优子结构性质的解决问题的方法。动态规划通常适用于不同阶段的决策问题，它将问题分解为若干个相互重叠的子问题，然后按照一定的顺序求解子问题从而得到原问题的最优解。例如，最长递增子序列、背包问题等都可以使用动态规划来解决。

3. 分治算法 分治算法是一种将问题分解成一些小的子问题，然后递归地解决这些子问题，最后将这些子问题的解合并起来得到原问题的解。分治算法通常包括三个步骤：分解，解决子问题，合并子问题的解。例如，归并排序、快速排序等都是基于分治思想的算法。

4. 回溯算法

回溯算法是一种在解决约束满足问题时的穷举搜索技术，它通过递归地搜索所有可能的解来找到满足约束的解。回溯算法通常适用于求解一个问题的所有解或者最优解。例如，八皇后问题、0-1背包问题等都可以使用回溯算法来解决。

算法导论小笔记

算法导论（CLRS）笔记

Note on CLRS

(Outline & Draft, 2011)

Jian Xiao1

第2章Getting started

1. Merge sort相关的扩展问题

1）链表实现V.S.数组实现。Divide阶段，如何快速找到链表的中点？另外，如何减少Divide/Combine的时间（相比数组实现）？

2）In-place merge的方法。

3）归并树：把Merge sort的中间过程都记录下来，所形成的树。（其实就是一棵线段树,每个节点存放该节点的区间内有序化后的数）

4）逆序数的计算。

2. 两数和问题。数的集合S，一个数x，判断S中是否存在两个数，二者的和为x。

这个问题扩展以后是一个subset problem，为NPC问题。

第3章Growth of Functions

1. 全部5个渐进符号的确切含义

第4章Recurrences

1. Substitution方法，Recursion tree方法计算复杂度

2. Master Theorem及其不能被三种case覆盖的其他情况

Master Theorem的证明

3. Chip testing problem

4. Monge arrays，凸四边形不等式，最优二叉查找树DP算法的优化

第5章Probabilistic Analysis and Randomized Algorithms

1. 用Biased-Random产生Uniform-Random分布。

2. In-place、O(n)的uniform random permutation

In-place、O(n)的各个position等概的排列 1iamxiaojian@/doc/d19529538.html,

3. Coupon collector’s problem

4. On-line hiring problem

《算法设计与分析》复习提纲 2014.7.5

1 引言(ch1)

1. 什么是算法及其特征

算法（Algorithm）是通过一个有限的指令序列集合对特定问题进行求解的一种计算执行描述。

算法特征：

（1）输入：一个算法具有零个或多个取自指定集合的输入值；

（2）输出：对每一次输入，算法具有一个或多个与输入值相联系的输出值；

（3）确定性：算法的每一个指令步骤都是明确的；

（4）有限性：对每一次输入，算法都必须在有限步骤（即有限时间）内结束；

（5）正确性：对每一次输入，算法应产生出正确的输出值；

（6）通用性：算法的执行过程可用于所有同类求解问题，而不仅适用于特殊输入。

2.问题实例和问题规模

问题实例是指需要计算同一个结果的问题的所有输入。

问题规模是指输入实例的大小,而输入实例是指问题的具体计算例子

2 算法初步(ch2)

1. 插入排序算法

1）算法步骤：

从左到右扫描数据A，扫描到一个元素，将A[j]与其左边的元素从右到左依次比较，若比之小，则将其之前元素后移，插入A【j】,直至A【j】比他前面的元素大，扫描A中的下一个元素

2）伪代码：

InsertSort(A)

{

for j=2 to A.length //第一层循环

｛

Key=A[j]

i=j-1

While i>0 and a[i]>key //第二层循环

｛

A[i+1]=A[i]

｝

i=i-1

A[i+1]=key

｝

}

2.算法复杂性及其度量 (1)时间复杂性和空间复杂性；

(2)最坏、最好和平均情形复杂性；

顺序情况下B（n）=O（n）、倒序情况下W（n）=O（n2）、A（n）=O(n2)

空间复杂性：需要常数个额外的临时空间存储临时数据

2. 插入排序的最坏、最好和平均时间

最坏O(n2)、最好O(n)和平均时间O(n2),空间复杂度是O(1)，稳定排序

3. 归并排序算法及其时间复杂性－时间Θ（n log n））

算法概述知识点总结

一、算法的概念

1. 算法是什么

算法（Algorithm）是指用于解决特定问题的一系列具体操作步骤。它是一种解决问题的方法论，能够将问题的输入转化为输出。

2. 算法的特点

（1） 确定性：算法在相同的输入条件下，能够得到相同的输出结果。

（2） 可行性：算法的每一步操作可以实际执行，不会陷入无穷循环。

（3） 有穷性：算法必须在有限的步骤内结束。

（4） 输入输出：算法必须具有输入和输出。

3. 算法的重要性

算法在计算机科学领域有着重要的地位，它是计算机程序的核心。一个好的算法能够提高程序的执行效率和准确性，从而提高计算机系统的整体性能。

二、算法的设计方法

1. 分治法

分治法（Divide and Conquer）是一种算法设计方法，它将问题分解为更小的子问题，通过递归地解决子问题，最终得到原问题的解。分治法常用于解决大规模问题，例如快速排序、归并排序、最近点对等。

2. 贪心法

贪心法（Greedy Algorithm）是一种构造性的算法设计方法，它每次以最优的策略选择当前的最佳解，从而得到问题的整体最优解。贪心法常用于最优化问题，例如最小生成树、哈夫曼编码等。

3. 动态规划

动态规划（Dynamic Programming）是一种通过将问题分解为更小的子问题来解决复杂问题的算法设计方法。动态规划通过存储子问题的解以减少重复计算，能够有效解决一些复杂的优化问题，例如背包问题、最长公共子序列等。

4. 回溯法 回溯法（Backtracking）是一种通过不断试探和放弃来寻找问题解空间的算法设计方法。回溯法常用于解决一些搜索和排列组合问题，例如全排列、N皇后问题等。

5. 分析设计

算法的分析设计是指分析问题的特性和要求，设计出合适的算法来解决问题。它是算法设计的关键环节，需要充分考虑问题的复杂度、特性和约束条件，从而选择合适的算法设计方法。

三、算法的复杂度分析