计算机二级公基知识1-算法概论

其实很早就想去考计算机二级证了,也是怕开学之后没时间准备(我特么要转专业,大学不能摸鱼啊),所以想趁着暑假多准备一些。(图文无关)


写在前面

对于OIer来说考二级还是相对比较简单的吧(flag),公基知识中有一部分就是数据结构与算法,NOIP普及组难度,后面那些应该也不是很难理解。

很遗憾的是错过了9月份的考试,只能等到12月再参加考试了= =

对,二级确实没啥用,但我就是想把它拿到手。

ps:前面的几部分对刚入坑的OIer同样适用。

算法

算法是指解题方案的准确而完整的描述。程序可以作为算法的一种描述。作为一个算法,它应该具有可行性,确定性,有穷性,同时应该拥有有用的情报。

可行性主要包括两个方面。第一,算法中的每一个步骤必须都是可实现的。比如不可除以0,实数集范围内不可求负数的平方根等。第二,算法执行后的结果要能够达到预期的目的。算法在执行过程中往往受到计算工具的能力限制,有可能会使结果产生一定的偏差(主要是指有效数字等)。同时需要注意,算法≠计算公式,它们之间是有区别的。

算法的确定性是指算法中的每一个步骤都应该有明确的定义,严禁模棱两可,也不能出现歧义。它也反映了算法与数学公式的差别。比如说,在解决某个现实中的问题时,数学公式是正确的,但按照这个数学公式设计的算法可能不会让计算机接受,这是因为数学公式没有考虑异常情况,当出现异常情况时,计算机就不知道该怎么办了。

算法的有穷性是指的是算法必须能够在有限的时间内完成,也就是它的步骤一定是有限的。同时算法的有穷性还意味着必须要在合理的时间内完成。比如未加任何优化的八皇后问题,它一共要执行648次运算,如果一台计算机每秒钟能执行循环100万次,那这个程序执行完毕也要9年时间。这显然没有实用价值。

一个算法是否有效,还取决于为算法提供的情报是否足够。一个算法的执行结果总是与其输入的数据有关,不同的输入可能会带来不同的输出。当输入不够或者格式错误时,算法将无法执行。一般来说,当算法拥有足够的情报时才是有效的,否则就是无效的。

·算法设计的基本方法

计算机的解题过程通常是在实行某种算法。这种算法我们称之为计算机算法。计算机算法不同于人工处理的方法。

1.列举法(穷举法)

它的基本思想很简单,根据提出的问题,找出所有可能出现的情况,并用问题所给出的条件去检索哪些是需要的,哪些是不需要的。因此,列举法常用来解决存在性或方案数问题。

列举法的实现通常都比较简单,暴力枚举,暴力搜索都算是列举法。但是它有一个致命的缺点,当列举的情况比较多时,该算法的执行速度会令人非常不满意。因此,在使用列举法时,可以稍加优化(剪枝)。在设计列举算法时,只要对实际问题做出详细的分析,将与问题有关的知识条理化,是可以大大减少枚举量的。有许多实际问题的规模很大,如果采用人工操作的话工作量通常难以想象,但借助计算机强大的计算能力,这会变得很简单。

2.归纳法

通过列举少量的特殊情况,经过(冷静)分析,找出一般的关系。它是一个由特殊到一般,由现象到本质的过程。它可以解决列举量为无限的问题。但是,从一个实际问题中归纳总结出一个一般的关系,通常来说并不是一件容易的事情。尤其是归纳为一个数学模型时更为困难。归纳是一种抽象,从特殊现象中找出一般关系。但由于在归纳过程中不可能对所有的情况进行列举,因此,由归纳法得到的结论本质上还是一种猜测,我们还需要对这种猜测加以论证才可以证明归纳正确。

3.递推法

所谓递推是指,从已知的初始条件出发,逐次推出所要求的各个中间结果和最后结果。其中初始条件一般是所给问题中指定,或是从初始条件经过推导得来。递推的本质也是归纳法,它是归纳法的一种。因此,递推的关系式通常是归纳的结果。递推法在数值计算中极为常见,但是,对于数值型的递推算法必须要注意数值计算的稳定性问题。

4.递归法

人们在解决一些特殊的复杂问题时,为了降低问题的复杂程度,一般会将问题逐层分解,最后归结为一些简单的问题。这种将问题逐层分解的过程,其实并没有降低问题的复杂程度,只是将原来规模大的问题划分成若干个规模小的问题,逐个解决后合并为整个大问题的答案。换句话说,是沿着原来分解的逆过程进行综合。这就是递归法的基本思想。其实不难看出,递归的本质也是归纳。在工程中,有很多问题是递归定义的,数学上的许多函数也是递归定义的。

其实就是

我 调 用 我 自 己

实际上,有一些问题既可以归纳为递推算法,也可以归纳为递归算法。但是递推和递归的实现方法是大不一样的。递推是从初始条件出发,逐次推出所需的结果,一环扣一环。但是递归是从算法本身直接到达递归边界,然后逐个处理子问题。通常的,递推算法要比递归算法清晰易读,递推算法的结构也相对于递归算法要简练一些。

5.分治法

在一些资料上也叫做减半递推技术。所谓减半,是指的将问题的规模减半,但是问题的性质不变,所谓递推,是指的重复减半的过程。

如果您听过一个术语叫“二分答案”,说的是一回事其实

6.回溯法

实际上,有些实际问题很难归纳出一组简单的递推公式或者是直观的求解步骤,并且也很难做到无限列举。对于这类问题,“试”是一种很好的方法。通过对问题的分析,找出一个解决问题的线索,然后沿着这个线索逐步试探,对于每一步试探,如果成功,就得到问题的一个“可行解”,如果试探失败,就返回上一步,再寻找下一个方案。这种方法称作回溯法。

算法的复杂度

算法的复杂度主要包括时间复杂度和空间复杂度。

算法的时间复杂度是指执行算法所需要的计算量。

为了能够比较客观的反映出一个算法的效率,在度量一个算法的计算量时,应该要与计算机本身,编写算法的人员本身,编写算法的语言无关,而且还要与实现过程中的各种细节无关。唯一有关的是算法在执行过程中的计算量,即基本运算的执行次数。同时,算法所执行的次数还与问题的规模有关,在OI上,问题的规模通常用n来表示。

综上所述,算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的一个函数。即

算法的工作量 = f(n)

比如有一个二重循环,每一层都是从1到n,这个算法总共要执行n2次,也就是说时间复杂度是O(n2)

ps:刚才牵扯到一个记号,叫大O记号,有兴趣的读者可以自行查阅相关资料。

通常的,我们在分析算法的时间复杂度时,要以最坏情况为基础进行分析,它更具有说服力和实用价值。还有一种方法是用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量,但是不常用。

一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。一般包括三部分,一是算法本身所占的空间,二是输入数据所占的空间,三是算法执行过程需要的额外空间。如果额外空间量相对于问题规模来说是一个常数,则我们说这个算法是在原地工作的。在许多实际问题中,为了减少算法所占用的存储空间,我们通常会采用一些压缩存储技术,以便尽量减少不必要的额外空间。


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:计算机二级公基知识1-算法概论

文章作者:Shawn Zhou

发布时间:2018年08月08日 - 17:08

最后更新:2018年12月09日 - 18:12

原始链接:http://yoursite.com/2018/08/08/国考计算机二级公共基础知识-Part-1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。