第一章 算法概述_算法是指解决问题的一种方法或一个过程

1.1 算法与程序

第1章 算法概述 - 学习笔记

学习要点

1. 理解算法的概念：算法是解决问题的方法或过程，由一系列指令组成的有限序列，旨在完成特定任务。
2. 算法的计算复杂性：
   • 最坏情况：算法在最不利情况下的性能。
   • 最好情况：算法在最理想情况下的性能。
   • 平均情况：考虑所有可能输入的算法性能平均值。
3. 算法复杂性的渐近性态：使用数学符号来描述算法随输入大小增长时的行为趋势。
4. 了解NP类问题：理解非确定性多项式时间(Nondeterministic Polynomial-time, NP)问题的基本概念。

1.1 算法与程序

• 算法的定义：

  • 输入：零个或多个外部提供的量。
  • 输出：至少产生一个量作为结果。
  • 确定性：每条指令清晰、无歧义。
  • 有限性：每条指令执行次数和时间都是有限的。

• 算法与程序的区别：

  • 程序是算法用某种程序设计语言的具体实现。
  • 程序可能不满足算法的有限性，如操作系统的无限循环。
  • 算法通常是解决特定问题的步骤，而程序是这些步骤的具体编码。

• 算法描述方式：

  • 自然语言、表格方式。
  • 采用C++语言描述算法，兼具面向过程和面向对象特点，结构紧凑，可读性强。
  • 有时结合自然语言和C++语言来阐明算法思路。

小结

理解算法的核心概念是计算机科学的基础。掌握算法的计算复杂性和渐近性态对于评估和选择合适的算法至关重要。同时，明确算法与程序的区别，了解如何使用程序设计语言准确描述算法，对于开发有效的软件系统和理解其背后的逻辑非常重要。NP类问题的理解则进一步引导我们探索计算的边界，理解哪些问题是计算机能有效解决的，哪些则需要更多的时间和资源。通过本章的学习，你将打下坚实的基础，为深入研究和实践算法安全和高效地解决问题做好准备。

要掌握的知识点：

• 理解算法的概念

我的理解：

就是要知道算法是什么。

在大脑的记忆空间里先在给定的一号位存放这个概念

• 理解什么是程序，程序与算法的区别和内在联系

我的理解：

同样的先在大脑里模拟两个概念这里用圆来表示

• 掌握算法的计算复杂性概念

我的理解：

嗯第一次听这个东西，我听懵逼的，这是个啥？先暂时存放在第三个空间中，这是第一次出现的新概念

• 掌握算法渐进复杂性的数学表述

我的理解：

渐进复杂性和计算复杂性都有复杂是不是有什么关联呢？这两个概念？同样先把问题放到脑子的第四个房间

• 掌握用C++语言描述算法的方法

卧槽C++那得好好复习一下了

• NP完全问题

听说过，但是不是很懂是什么意思？

一、算法分析概述

(1)问题的引入：

• 什么是算法？

算法 (Algorithm)

算法是指解決问题的一种方法或一个过程。

算法是若干指令的有穷序列，满足性质：

(1)输入：有外部提供的量作为算法的输入。

(2）输出：至少一个量作为输出。

(3）确定性：组成算法的每条指令是清晰，无歧义的。

(4)有限性：算法中每条指令的执行次数是有限的，执行

每条指令的时间也是有限的

我的理解：

好熟悉的感觉~类比记忆——类比的思想

我认为这个输入就好像三国杀的模式一样，一般情况下每位玩家每回合都可以得到两张牌，即牌的输入，每回合玩家要出牌打击对手保全自己还有保护队友如果牌数多于自己血量就得弃牌即为每回合至少输出一张牌，确定性即为每位角色所拥有的技能是清晰无误的，有限性即每位玩家每回合出牌数是有限的。

总结：

算法四大性质——三国杀

（1）输入——抽牌

（2）输出——出牌

（3）确定性——角色技能

（4）有限性——牌数有限

• 什么是程序？

程序 (Program)

程序是算法用某种程序设计语言的具体实现。

程序可以不满足算法的性质(4)。

•例如操作系统，是一个在无限循环中执行的程序

因而不是一个算法。

•操作系统的各种任务可看成是单独的问题，每-

个问题由操作系统中的一个子程序通过特定的算

法来实现。该子程序得到输出结果后便终止。

---

1.2 算法复杂性分析

第1.2章 算法复杂性分析 - 学习笔记

算法复杂性的重要性

• 定义：算法复杂性是指运行算法所需的计算资源量，主要包括时间和空间资源。时间复杂性和空间复杂性是衡量算法效率的关键指标。
• 目标：设计尽可能低复杂性的算法，并从多个可选算法中选择复杂性最低者。

算法复杂性的数学表述

• 复杂性函数：用C=F(N, I, A)表示复杂性，其中N代表问题规模，I是输入，A是算法本身。
• 时间复杂性：T(N, I)代表算法在抽象计算机上运行所需时间。通常简化为T(N)，忽略输入I的影响。
• 空间复杂性：S(N, I)代表算法需要的存储空间量。

算法的时间复杂性分析

• 元运算：算法中的基本操作，每种操作的执行时间用t₁, t₂, …, tk表示。
• 执行次数：算法中元运算Oi的执行次数为ei(N, I)，其中i=1,2,…,k。
• 时间复杂性函数：T(N, I) ≈ Σ(ti * ei)，即所有元运算的执行时间与执行次数的乘积之和。

复杂性分析的简化

• 特定情况：只考虑算法在最坏情况、最好情况和平均情况下的时间复杂性，分别记为Tmax(N)、Tmin(N)和Tavg(N)。
• 渐近性态分析：当问题规模N趋向无穷大时，复杂性函数的行为。常用记号包括O、Ω、θ和o。

渐近符号的定义和运算规则

• O符号：f(N) = O(g(N))表示f(N)在N趋向无穷大时上有界于g(N)。
• Ω符号：f(N) = Ω(g(N))表示f(N)在N趋向无穷大时下有界于g(N)。
• θ符号：f(N) = θ(g(N))表示f(N)与g(N)同阶。
• o符号：f(N) = o(g(N))表示f(N)的阶比g(N)低。

实际应用和误区

• 选择复杂性最低的算法：在实际应用中，通常关注最坏情况下的时间复杂性Tmax(N)。
• 算法的最优性：使用渐近符号分析算法的最优性。如果一个算法的时间复杂性为问题的下界，则它可能是最优的。
• 易错点：不同的输入和问题规模可能导致算法性能的巨大差异，因此在实际应用中应该结合具体情况分析。

小结

理解算法复杂性对于设计高效算法至关重要。通过分析算法的时间和空间复杂性，我们可以预估算法在不同情况下的表现，并选择或设计出适合特定问题的最优算法。渐近分析提供了一种强大的工具，能够帮助我们从数学上严格地比较不同算法的效率。掌握这些概念和技巧，能够在算法设计和选择中做出明智的决策。

第1.3章 NP完全性理论 - 学习笔记

理解计算复杂性

• 核心问题：确定问题的内在复杂性，区分“易”计算的问题和“难”计算的问题。
• 计算时间下界：了解问题的计算时间下界可以帮助评价算法的效率和改进空间。

易解与难解问题

• 易解问题：可以在多项式时间内解决的问题，通常认为是计算上“易”处理的。
• 难解问题：需要超过多项式时间（如指数时间）才能解决的问题，通常认为是计算上“难”处理的。

P类与NP类问题

• P类问题：可以在多项式时间内解决的判定问题，代表确定性计算模型下的易解问题。
• NP类问题：在非确定性图灵机上可以在多项式时间内验证解的判定问题，代表非确定性计算模型下的易验证问题。

非确定性算法

• 猜测与验证：非确定性算法将问题求解分为猜测和验证两个阶段，其中猜测阶段是非确定性的，验证阶段是确定性的。
• 多项式时间非确定性算法：如果验证阶段可以在多项式时间内完成，则算法被认为是多项式时间非确定性算法。

NP完全问题

• 定义：如果所有NP类问题都可以在多项式时间内归约到该问题，则称该问题为NP完全问题。
• 重要性：NP完全问题是理解计算复杂性的关键，因为它们是NP类中最“难”解的问题。

P=NP问题

• 开放问题：是否所有的NP问题都是P问题，即P=NP，这是计算机科学中最著名的未解决问题之一。
• 影响：如果P=NP被证明为真，那么许多现在认为是难解的问题都将变得易解。

NP完全问题的示例

• SAT问题：布尔表达式的可满足性问题，是第一个被证明为NP完全的问题。
• 其他问题：旅行售货员问题、哈密顿回路问题、子集和问题等，这些问题在计算上的难度类似，都是NP完全问题。

小结

NP完全性理论是理解算法复杂性的核心。它不仅揭示了计算问题的内在难度，还指导我们如何对待那些看似简单却极其复杂的问题。理解这些概念有助于深入探索算法设计和计算理论的边界，同时也提醒我们在面对实际问题时需有合理的预期。虽然NP完全问题可能没有快速的解决方案，但了解它们的本质对于计算机科学的学习和研究至关重要。

• 什么是算法分析？

我的解答：评判一个算法的优劣的系统方法

书本解答：分析算法占用的计算机资源的情况

• 算法分析的两个方面

我的解答：时空复杂度

书本解答：

时间复杂度——算法运行所需要的时间资源的量

空间复杂度——算法运行所需的空间资源的量

• 算法分析的目的

我的解答：对程序的不断优化

书本解答：

设计算法——设计出复杂性尽可能低的算法

选择算法——在多种算法中选择复杂性最低的算法

时间复杂度分析

算法复杂性 二算法所需要的计算机资源

算法的时间复杂性T(n)；

算法的空间复杂性 S(n)。

其中n是问题的规模（输入大小）

图解：

两种方法：

事后实验统计法——编写算法对应程序，统计其执行时间

事前分析估算法——渐进分析法

算法的时间复杂性

（1）最坏情况下的时间复杂性

Tmax(n) = max{ T(I) | size(I)=n}

（2）最好情况下的时间复杂性

Tmin(N)= minf {T(I)|size(I)=n}

（3）平均情况下的时间复杂性

对算法的时间复杂性分析：

（3）平均情况下的时间复杂性

疑问：

1.为什么用期望而不是直接用最大最小值求和除以二？

在计算算法的平均时间复杂度时，使用期望值而不是直接使用最大值和最小值的平均值，是因为期望值能更好地反映算法在不同输入情况下的平均性能。

算法的时间复杂度描述了算法所需执行的操作数或时间与输入规模之间的关系。最好情况时间复杂度表示算法在最理想情况下的性能，而最坏情况时间复杂度表示算法在最不利情况下的性能。然而，最好和最坏情况只能提供一种极端情况下的性能估计，而不能完全描述算法在实际应用中的表现。

使用期望值来计算平均时间复杂度的原因如下：

1. 考虑到实际应用：在实际应用中，输入的数据往往是随机的、多样的，而不是固定的最好或最坏情况。因此，使用期望值能更好地反映算法在不同输入情况下的平均性能，更贴近实际应用的情况。

2. 考虑到输入分布：对于一些问题，输入的分布可能不均匀，最好和最坏情况的出现频率可能不同。使用期望值可以考虑不同情况的发生概率，更准确地评估算法的平均性能。

3. 考虑到算法的设计：算法的设计应该追求在大多数输入情况下表现良好，而不仅仅关注最好或最坏情况。期望值能够综合考虑算法在各种输入情况下的平均性能，为算法设计者提供更全面的评估依据。

需要注意的是，计算算法的期望时间复杂度通常需要对输入的分布和算法的执行过程进行概率分析。这可能需要一定的数学知识和技巧，但它能够提供更准确的算法性能估计，帮助我们选择更适合实际应用的算法。

很显然这就是期望，这给我们一个启发我们学到对于算法时间平均情况的分析可以用概率论中的期望。这就是概率论与算法时间复杂度的联系：（如果想仔细了解一下期望可以看一下我关于期望的文字——概率论上期望的传送门：4.1 随机变量的数学期望）

•其中I是问题的规模为 n的实例，p(I)是实 例1出现的概率

二、渐进复杂度分析

---

2023/5/27 补充

算法渐近复杂性

我的解释：

算法的渐进复杂性（Asymptotic Complexity）是用来描述算法执行时间或空间需求随着输入规模增长而变化的一种分析方法。它关注的是算法在大数据规模情况下的性能表现。

算法的渐进复杂性是用来描述算法在处理输入规模增加时的性能变化情况。通常使用大O符号（O）来表示渐进复杂性。它衡量了算法的时间复杂性和空间复杂性。

时间复杂性是指算法执行所需的时间量，即算法的运行时间。空间复杂性是指算法在执行过程中所需的额外内存空间量，即算法所使用的内存。

渐进复杂性通过观察算法的执行步骤数或占用的内存单元数，随着输入规模的增加，得出一个上限或下限。这个上限或下限不一定是准确的运行时间或内存使用量，但可以用来比较不同算法的相对性能。

以下是一些常见的渐进复杂性表示：

1. O(1)：常数复杂性。算法的执行时间或空间占用是常量，与输入规模无关。例如，访问一个数组中的特定元素。

2. O(log n)：对数复杂性。算法的执行时间或空间占用随着输入规模的增加而增长，但以对数的速度增长。常见的例子是二分查找算法。

3. O(n)：线性复杂性。算法的执行时间或空间占用与输入规模成线性关系。例如，遍历一个数组中的所有元素。

4. O(n log n)：线性对数复杂性。算法的执行时间或空间占用在输入规模增加时略高于线性复杂性。常见的例子是快速排序和归并排序。

5. O(n^2)：平方复杂性。算法的执行时间或空间占用与输入规模的平方成正比。例如，嵌套循环遍历一个二维数组。

6. O(2^n)：指数复杂性。算法的执行时间或空间占用随着输入规模的增加呈指数级增长。这种复杂性通常是非常低效的。例如，求解旅行商问题的暴力穷举算法。

这些只是一些常见的渐进复杂性表示，实际上还有其他更高级的复杂性类别，如多项式复杂性（O(n^k)）和指数对数复杂性（O(2^(n log n))）等。

了解算法的渐进复杂性可以帮助我们估计算法的运行时间和资源需求，从而选择最适合特定问题的算法，并进行性能优化。

渐进复杂性使用大O符号（O）表示，表示算法的上界或上限。它描述了算法的增长率，即算法的执行时间（或空间）与输入规模之间的关系。渐进复杂性不关注具体的常数因子和低阶项，而是更关注随着输入规模增长，算法执行时间的增长趋势。

---

T(n) 100, as n-100;

-(T(n) - t(n) y/ T(n) —>0, as n—>∞;

t切是Tn的渐近性态，为算法的渐近复杂性。

•在数学上，

tn）是丁(n） 的渐近表达式，是Tn略去

低阶项留下的主项。它比丁n）简单。

渐近分析的记号

•在下面的讨论中，对所有n，fn≥0，g(≥0。

（1）渐近上界记号—— O 。

• O(g(n)={f(n1存在正常数C和八。 使得对所有n二n

有：0≤fn≤cg(n}

对渐进上界的解释：

渐进上界（Asymptotic Upper Bound）是一种用于描述算法执行时间或空间需求的上限的分析方法。它使用大O符号（O）表示，并表示算法的增长率或上界。渐进上界描述了算法的执行时间（或空间）与输入规模之间的关系，通常关注算法在最坏情况下的性能表现。

渐进上界主要关注算法的增长趋势，而不关注具体的常数因子和低阶项。因此，它提供了一种简化的方式来比较和分类不同算法的性能。

常见的渐进上界有以下几种：

1. 最坏情况时间复杂度（Worst Case Time Complexity）：表示算法在最不利情况下的时间性能的上界。通常使用O符号表示，例如O(n)表示线性时间复杂度的上界。

2. 最坏情况空间复杂度（Worst Case Space Complexity）：表示算法在最不利情况下的空间需求的上界。通常使用O符号表示，例如O(n)表示线性空间复杂度的上界。

渐进上界的使用有以下优点：

- 简化比较：渐进上界提供了一种简化的方式来比较不同算法的性能。通过忽略常数因子和低阶项，我们可以更专注地分析算法的增长趋势，并比较它们在不同输入规模下的性能。

- 通用性：渐进上界是一种通用的分析方法，适用于各种类型的算法和问题。无论算法的实现细节如何，只要我们能够确定其上界，就可以使用渐进上界进行分析。

- 简洁性：渐进上界提供了一种简洁的方式来表示算法的性能，使得我们能够快速了解算法的增长趋势。它能够帮助我们更好地理解算法的效率，并作出合适的选择。

需要注意的是，渐进上界只提供了一种算法性能的上限估计，并不能准确反映算法在实际应用中的表现。实际执行时间和空间可能会受到具体输入实例、硬件环境、编译器优化等因素的影响。因此，在评估算法性能时，除了渐进上界，还需要考虑实际应用的场景和需求。

（2）渐近下界记号—— Ω

• 8 (g()={t(几)1存在正常数c和八。使得对所有n二八

oF: 0< cg(n) ≤ f(n)}

算法的运行时间是问题规模n的函数，记作T(n)

用基本语句的执行次数表示T(n)

忽略低阶项和常系数，只考虑最高阶

用大O、大Ω和大0表示其渐进意义下的阶

（3）非紧上界记号。o

。(g(n)={f(n)1对于任何正常数c>0，存在正数和八。

二使得对所有几二几。有：0≤f(n<cg(n)}

•等价于 fn/g(n-0, as n-30

•（4）非紧下界记号

•w(g(D)={fn！对于任何正常数C>0，存在正数和八

。＞0使得对所有几二几。有：0≤cg(n<t(n}

•等价于 fn1 g(n-∞,as n-o。

- f(n) E c (g(n)) = g(n) E o (f(n))

（5）紧渐近界记号口

• 0 (g()={fn1存在正常数CrC,和几。使得对所有八

2 no #: Gg(n) < f(n) ≤ c,g(n) }

- I1: 0 (g(n)) = 0 (g(n)) n 2 (g(n))

定理1：（g(n)）=O(g(n))∩Ω（g(n)）

定义1.大O符号——渐进上界记号

若存在两个正的常数C和n0,对于任意n>=n0,都有f(n)<=C*g(n),则称f(n)=O(g(n)),即g(n)为f(n)的上界

例题：

解析：

一个算法的运行时间用大O符号表示时，总是采用最有价值的g(n),称之为“紧凑上界”或紧凑下界

定义2.大Ω符号——渐进下界记号

若存在两个正的常熟C和n0,对于任意n>=n0,都有f(n)>=c×g(n),则称f(n)=Ω(g(n)),g(n)为f(n)的下界。

定义3.大符号——渐进紧界记号

若存在三个正的常数C1，C2和n0，对于任意n>=n0都有C1×g(n)>=f(n)>=C2×g(n),则称f(n)=O(g(n)),即g(n)与f(n)同阶。

渐近分析记号在等式和不等式中的意义

-tn=0(g(n）的确切意义是：fE0(g）。

-般情况下，等式和不等式中的渐近记号口(g(）表示口(g

（几）中的某个函数。

•例如：212+31+1=2n2+0（n）表示

12n2+3n+1=2n2+f（n），其中fn）是口(几中某个际数。

•等式和不等式中渐近记号0,0,9和0的意义是类似的。

渐进式和函数的关系

f(n) = O(g(n)) ~ a ≤ b;

- f(n) = 8 (g(n)) ~ a ≥ b;

- f(n)= (g(n)) ~ a = b:

= f(n)= o(g(n)) ~ a < b;

- f(n) = w(g(n)) ~ a > b.

渐近分析记号的若干性质

•（1）传递性：

= f(n)= (g(n)) ,

g(n)= (h(n)) = f(n) = @(h(n)) :

- f(n) = O(g(n)) ,

g(n)= 0 (h(n)) = f(n) = 0 (h(n)) ;

= f(n)= 2(g(n)) ,

g(n)= 82 (h(n)) = f(n) = s2(h(n)) ;

= f(n)= o(a(n)) , a(n) = o(h(n)) = f(n) = o(h(n)) :

= f(n)= c(a(n)) , a(n) = 0 (h(n)) = f(n) = 0 (h(n)) :

（2）反身性：

f(n)= O(f(n)) ;

- f(n) = O(f(n)) :

- f(n) = 2(f(n)).

•（3）对称性：

- (n)= (g(n)) = g(n) = (f(n)).

•（4）互对称性：

- f(n) = O(g(n)) = g(n)= S2 (f(n))

= f(n)= 0 (g(n)) = g(n) = c (f(n))

（5）算术运算：

O(f(n))+O(g(n)) = O(max{f(n),g(n)]) :

- O(f(n))+O(g(n)) = O(f(n)+g(n))

- O(f(n))*O (g(n)) = O(f(n)*g(n))

O(cf(n)) = O(f(n)) :

- g(n) = O(f(n)) = O(f(n))+O (g(n)) = O(f(n))

•规则O()+0(g(n)=O(maxfn),g(の的证明：

对于任意t(n)EO(n)，存在正常数C，和自然数八，使得对所有

贮几，有t(n≤cto

类似地，对于任意g.(n)EO(g(n)，存在正常数C，和自然数几2，

使得对所有n≥几2，有g.(n)≤cg(n)。

4 G=max{G,, cz}.

ng=max{n, n] , h(n)= maxff(n),g(n)} •

则对所有的n二ng，有

f,(n) +9, (n) ≤ c,f(n) + c,g(n)

≤ Caf(n) + Gag (n) = C (F(n) + g(n))

≤ G-2 max{f(n),.g(n)}

= 20gh (n) = O(max{f(n),g(n)]).

算法渐近复杂性分析中常用函数

（1）单调函数

单调递增：msn=fm)≤fn；

单调递减：msn二fm)≥fn;

严格单调递增：m<n=tm)<fn;

严格单调递减：m<n=fm）>fn.

（2）取整函数

|x1：不大于x的最大整数；

「x：不小于x的最小整数。

取整函数的若干性质

x-1 < x <x< x <xt1 :

In/21 + In/2|= n;

对于n≥0，a,b>0，有：

[Inlallbl=[nlabl:

Il nlal lb| = | nlabl:

- [ alb| < (a+(b-1))/b;

I alb |≥ (a-(b-1))/b;

f×=1×,g(x=「x1为单调递增雨数

（3）多项式函数

p(n)= ata,n+ayn+…..+agnd;

p(n) = O(na):

f(n)=0（m一tn）多项式有界；

f(n) = 0(1) = f(n) ≤ c;

k≥d= p(n) = O(n') ;

• K< d = p(n) = 82(nk);

k>d= p(n) = o(nk) ;

• K<d= D(n) = c(nk).

（4）指数函数

对于正整数m,n和实数a>0:

a0=1:

al=a:

a1=1/a:

(amn= amn:

(amn= (amm;

aman = am+n •

a>1=an为单调递增函数；

a>1 >

16

lim

=0 = n° = 0 (an)

5）对数函数

log n= log,n;

lg n= logion;

In n= log.n;

logkn = (log n)l;

log log n = log(log n);

for a>0,b>0,c>0

a =bloga

log, (ab) =10g, a + log, b

log, a" =nlog, a

log, a

log, a

log,b

logo (1/a) =- log, a

log, a =

log, b

alogc

=cloga

三、渐进时间复杂度分析的一般步骤

1. 明确问题规模的度量

1. 确定基本语句

1. 检查基本语句的执行次数是否依赖于问题的规模

1. 计算基本语句运行的次数，建立求和表达式

1. 用渐进符号大O表示算法增长率的上界，即T(n)=O(f(n))

扩展部分

算法的实验分析

渐进分析是一种数学方法，渐进分析技术能够在数量级上对算法进行精确度量。但是，数学不是万能的，实际上，许多貌似简单的算法很难用数学的精确性和严格性来分析，尤其分析平均情况。算法的实验分析是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。例如，为了测算起冒泡排序算法在实际运行过程中的比较次数和移动次数，可以设置两个计数器count1和count2，在比较语句执行前将count加1，在交换语句执行后将计数器count2加3（因为交换操作需要用三条赋值语句实现）。程序如下：

void BubbleSort(int r[],int n)

{

int count1=0,count2=0;//count1和count2记载比较次数和移动次数

int bound,exchange=n-1;//当上一趟排序

int count1=0. count2=0://countl 和count2 记载比较次数和移动次数

int bound, exchange=n-1://第一趟起泡排序的区间是r0.n11

while (exchange!= 0){/当上一趟排序有记录交换时

hound = exchange;

exchange =0;

for (int j=0: i<bound; i++)411一趟起泡排序区间时「0.bound]

f (++countl &&1j=6+1J1/注意不能写作countl++

int temp =ril;

fil=ri+ll;

rj+1] = temp;

count2=count2 +3:/1 次交换时 了次移动操作

exchange=j：//加载每一次记录交换的位置

count-<"比较的次数是"<<countl<<endl:

count<<'移动的次数是"<<count2<<endl：

}

下面给出算法实验分析的一般步骤：

（1）明确实验目的。在对算法做实验分析时，可能会有不同的目的，实验的

设计依赖于实验者要寻求什么答案。例如，检验算法效率理论分析的正确性，比

较相同问题的不同算法或相同算法的不同实现间的效率，等等

（2）决定度量算法效率的方法。一般来说，有以下两种度量方法。

① 计数法。在算法中的适当位置插入一些计数器，来度量算法中基本语

句（或某些关键语句）的执行次数。

② 计时法。度量某个特定程序段的运行时间，可以在程序段的开始处和

算法资源库2

1 NP 完全问题

1.1 NP 完全问题定义

NP 完全问题产生于各种不同领域：布尔逻辑，图论，算法，网络设计，集

合与划分，存储与检索，排序与调度，数学程序设计，代数与数论，游戏与难

解问题，自动机与语言理论，程序优化，生物学，化学，物理，等等。在本节

中，我们将运用归约方法，对于从图论到集合划分的各种问题进行 NP 完全性

的证明。

令I是-

- 个判定问题，如果问题口属于NP 类问题，并且对 NP 米问题中

的每一个问题口!，都有正'c 口，则称判定问题口是一个 NP完全问题

(NPComplete Problem, ¡¾ NPC).

1.2 NP 完全问题的证明步骤

步骤

证明TENP；

步骤二：选一个己知的 NPC 问题元'∞元

2 COOK 定理及其证明

Cook 定理布尔表达式的可满足性问题 SAT 是NP 完全的。

证明：SAT 的一个实例是k 个布尔变量 x1,x2.….x的m 个布尔表达式

A,Az....Am，若存在各布尔变量 xi(1sisk)的0、1赋值，使每个布尔表达式

A(lsism)都取值 1，则称布尔表达式 A1A..Am是可满足的。

第一步：证明 SAT ENP

SATENP 是显然的。对于任意的布尔量 x1,x2，…,xk 的0、1赋值,容易在多项

式时间内验证相应的 A1Az..Am 的取值是否为 1。因此，SATENP。

第二步：证明Lo,SAT

设M是一合能在多项式时问内识别工的非确定性图灵机，而W是M的-

个输入。由M和w能在名项式时间内构造一个布尔表达式Wo，使得 Wo是可

满足的当且仅当M按受W

不难证明，属于NP 的任何语言能由一台单带的非确定性图灵机在多项式

时问内识别。因此，不妨假定M是一台单带图灵机。设M有s个状态

q0.91,.9s1 和m个带符号X1，X2.…,Xm,P(n)是M 的计算复尜性。设w是M的

• 个长度为n的输入，若M接受W，只需要不多于P(口次移动。也就是说，存

在M的一个瞬象序列00.0.

….0,其中00是初始瞬象，の是接受瞬象，

P（)。由于读写头每次最多移动一个单元，因此，任一接受 W 的瞬象序列不

会使用多手 P(n个单元。不失一般性，假定M到达接受状态后将继续运行下

去，但以后的计算将不移动读写头，也不改变已进入的接受状态，直到pn个

动作为止。也就是说，用一些空动作填补计算路径，使它的长为P(D)，即恒有

r=P(n).

判断Q0,01,…,0p为一条接受 W的计算路径等价于判断下述7条事实

(在每一瞬象中，读写头只扫描一个单元：

(2)在每一瞬象中，每个单元中的带符号是唯一确定的：

(3)在每一瞬象中只有一个状态：

(④)在该计算路径中，从一个瞬象到下一个瞬象每次最多有一个单元(被读写

头扫描着的那个单元）的符号被修改；

(5)相继的瞬象之间是根据移动函数8来改变状态、读写头位置和单元中符

（600是M 在输入 W时的初始瞬象：

⑦最后一个瞬象 QprD中的状态是可接受状态

为了确切地表达上述了条事实，需要引进和使用以下几种命题变量。

(Dc<ijt>=1，当且仅当在时刻t，M的工作带的第i个单元中的带符号

是X，其中 1si<P(n), 1sism, 0≤t<P(n).

（2)S<k，t>=1，当且仅当在时刻t，M 的状态为qk，其中 1sk<s,

O<t<P(n).

（3)H<i, t=1，当日仅当在时刻t，读写头扫描第i个单元，其中

1<<P(n), 0<<P(n).

这里总共最多有O(P0))个变量，它们可以由长不超过clog2n 的二进制数

表示，其中c是一个常数。为了叙述方便，假定每个变量仍表示为单个符号而

不是clogsn 个符号。这样做减少了一个因子clogzn，但不影响对问题的讨论

现在可以用上面定义的这些变量，通过模拟瞬象序列Q0.01，

疑问：

（1）告诉我算法渐进复杂性分析中常用函数有什么用？

总结：算法概述、算法复杂性分析、NP完全性理论

重点：

1. 算法概述（第1章）:

   • 算法定义：解决问题的有序步骤和方法。
   • 算法性质：输入、输出、确定性和有限性。
   • 算法与程序：区分算法（抽象步骤集）和程序（具体实现）。

2. 算法复杂性分析（第1.2章）:

   • 时间和空间复杂性：度量算法效率和资源消耗的两个主要方面。
   • 复杂性函数：使用T(N, I)和S(N, I)来表示算法的时间和空间复杂性。
   • 渐近符号：如O、Ω、θ和o，用于描述算法性能随输入规模增长的趋势。

3. NP完全性理论（第1.3章）:

   • P vs NP问题：探讨多项式时间内可解决问题(P)与可验证问题(NP)的关系。
   • NP完全问题：一类特别“难”的问题，如果有一个NP完全问题可以在多项式时间内解决，则P=NP。
   • 典型NP完全问题：如SAT问题、旅行售货员问题等。

难点：

1. 算法复杂性分析:

   • 理解和正确应用渐近符号，特别是区分O、Ω、θ和o的具体含义和用法。
   • 分析算法时考虑最坏、最好和平均情况的复杂性，特别是如何确定和计算平均情况复杂性。

2. NP完全性理论:

   • 理解非确定性图灵机和非确定性算法的概念。
   • 掌握如何证明一个问题是NP完全的，特别是理解归约的概念和方法。

易错点：

1. 算法概述:

   • 将程序和算法混为一谈。应记住算法是独立于具体实现的问题解决方案。
   • 忽视算法的确定性和有限性，特别是在算法设计和分析中。

2. 算法复杂性分析:

   • 错误地将渐近符号应用于具体复杂性计算，例如混淆O和Ω或忽视低阶项的影响。
   • 在分析算法时，过于依赖或忽视某一特定情况下的复杂性（如仅考虑最坏情况）。

3. NP完全性理论:

   • 错误地认为所有NP类问题都是难解的，忽视P类是NP类的子集这一事实。
   • 在证明问题是NP完全时，忽视或错误地应用多项式时间归约。

理解这些重点、难点和易错点是掌握算法基础的关键。通过克服这些难点和避免这些易错点，可以更深入地理解算法的本质、性能评估方法和计算复杂性的理论。