关于计算概论A期中考试之后的算法学习

0 引言

期中考试之前的计算概论课程,所讲的内容大概是C语言的基础语法,目的在于写出语法上正确的代码,熟练地进行各类型数据的读入输出,并且做一些简单的处理。期中考试的重难点,也在于对数据进行正确的读入与储存,而对于后续的计算,则基本上是处于“暴力即可”的一个标准。而期中考试之后,计算概论的学习上会进行从语法学习到简单算法学习的一个转变,表现在编写程序上,就是从“写一个正确的做法”到“写出一个优秀的算法”的转变。这就需要先去了解什么样的程序可以算得上是一个优秀的程序。

1 关于时空复杂度

1.1 时间复杂度

任何一个程序在运行的过程中,都需要消耗一定的时间,用来执行被一个步骤,也需要一定的空间,来进行数据的存储。对于程序运行的时间,是可以比较轻易地感受到的,就比如说在不同的搜索引擎中进行同一个问题的搜索,那么在不考虑搜索结果的情况下,给出结果更快的搜索引擎会更多地受到青睐;在一些前沿领域中,例如无人驾驶技术,一个更快的程序可以更快地完成对外界情况的判断,从而尽早作出反应,规避潜在的风险。我们以后的编写的程序,需要时刻考虑它运行时间的长短,也即程序的时间复杂度:

一般来说,复杂度是一个关于数据规模的函数。对于某些算法来说,相同数据规模的不同数据依然会造成算法的运行时间/空间的不同,因此我们通常使用算法的最坏时间复杂度,记为T(n)。 (OI-Wiki)

前面提到的时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数,记作T(n)=O(f(n)),它称为算法的渐进时间复杂度,简称时间复杂度。

1.2 时间复杂度举例

图片来自 sigongzi
O(n^2)
O(n^2)
O(n)
O(n^2)
O(nlogn)
O(sqrt(n))
图片来自 sigongzi

1.3 空间复杂度

空间复杂度就是程序运行所占用的内存。

我们不妨以 int 类型为例,在计算机中,一个 bit 是 8 个二进制位,而 int 类型数据是 32 个二进制位,所以一个 int 占 4 个 bit 。所以对于一个内存限制为 256M 的题,最多可以开 1024*1024*256/4 ≈ 64000000 个 int 。

大家做的题目中很难遇到卡内存的题,所以只需要计算好内存,正常开数组就不会爆,不太需要寻找内存更优的算法。

2 优化时空复杂度的算法

2.0 复杂问题中的暴力枚举方法

2.1 暴力枚举的局限性以及可能的改进方法

通过暴力穷举每一种可能状态得到答案是一种通用的解题方法,但是正如我们在解数学题过程中尽可能避免暴算一样,即便计算机拥有远超出人类的强大计算能力,在应付一个复杂度很高的做法的时候,也无法实现很大规模的问题的处理。因此我们可以通过去除掉一些不必要的枚举/对一些状态进行合并来简化,甚至可以通过将问题转化为更简单的问题的方法来提高运行的效率。

2.2 贪心算法

“关于计算概论A期中考试之后的算法学习”的5个回复

发表评论

邮箱地址不会被公开。 必填项已用*标注