算法的定义：

算法与程序的区别：

算法描述方式：

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

理解算法的概念

我的理解：

就是要知道算法是什么。

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

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

我的理解：

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

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

我的理解：

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

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

我的理解：

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

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

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

NP完全问题

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

什么是算法？

算法 (Algorithm)

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

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

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

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

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

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

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

我的理解：

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

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

算法四大性质——三国杀

（1）输入——抽牌

（2）输出——出牌

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

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

什么是程序？

程序 (Program)

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

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

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

因而不是一个算法。

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

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

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

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

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）平均情况下的时间复杂性

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

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

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

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。

• 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)表示线性空间复杂度的上界。

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

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

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

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

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

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

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

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

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

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

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

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

二使得对所有几二几。有：0≤f(n0，存在正数和八

。＞0使得对所有几二几。有：0≤cg(n=n0,都有f(n)=n0,都有f(n)>=c×g(n),则称f(n)=Ω(g(n)),g(n)为f(n)的下界。

若存在三个正的常数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))

对于任意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