大一新生以此篇开启你的算法之路

各位大一计算机萌新们，你们好，本篇博客会带领大家进行算法入门，给各位大一萌新答疑解惑。博客文章略长，可根据自己的需要观看，在博客中会有给大一萌新问题的解答，请不要错过。

入门简介：

算法，从字面意思来说就是计算方法，它是解决的问题的方法。一个问题有很多种方法解决问题，那么这很多种方法就是算法。官方给出的解释是：算法（Algorithm）是计算机科学中一个非常重要的概念，指的是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，算法是对特定问题求解步骤的一种描述，它是一组定义良好的计算过程，用于将输入数据（或称为问题的初始状态）转换成所需的输出形式（或称为问题的解）。

不懂没关系，我们继续往下看。

我们来举个简单的例子，热爱学习的你到图书馆借了10本书，由于自动借书机器的故障，你的一本算法书籍没有扫描登记混在了10本书当中，当你通过图书馆门禁时，警报突然响了，惊慌失措的你立马查看是哪一本书没有登记，你把借阅的10本书一本一本的通过门禁，看看哪一本没有登记。坐在旁边的门卫大爷看不下去了，立马抢夺过来，门卫大爷首先把10本书分成两组，每5本一组，首先把任意一组通过门禁，如果警报响起未登记的书就在这一组里面，否则在另外一组里面。然后把警报响起的那组再分成两组，一组3本，一组2本，任意一组通过门禁，如果是2本的那一组警报响起的话，把这2本再分成2组，分别是每组1本，再分别通过门禁就会知道是哪一本没有登记了，如果是3本的那组警报响起的话，再把3本分成两组，分别是2本、1本，若是2本的警报响起，再分成两组，那么就可以找到了。

看完上面的例子，你是不是对算法有了稍微的了解了，由上面的例子我们来看，如果是一本一本的通过门禁，如果运气真的很差，就是在第10次才能检测出没有登记的书籍。如果是按照门卫大爷的方法，最坏的情况下，第4次就可以检测出没有登记的书籍，最坏的情况如下：第一次5本书一组，警报响了，把5本分成3本、2本两组，3本的那组响了，3本分成2本、1本两组，2本的那组响了，把2本分成每本一组，再通过一次就可以检测出来。此时你不禁感叹道算法这么厉害吗？

算法有哪些

算法在中国古代文献中称为“术”，最早出现在《周髀算经》、《九章算术》。距今不知道有多少种算法，但是ACM竞赛里常考的就一张图片搞定。下面放一张ACM队里培训常用得一张图片。里面涉及到了很多常用的算法，这些算法根据难度分为初级、中级、高级。

上面算法有非常多，如果你立志于拿acm金牌，参加World Final，那么这些都要熟练掌握，如果是大一小白，先从简单的学起来，像基本算法、搜索、动态规划、数据结构，再慢慢的去学习中级的算法，这些是一名acmer必须要掌握的基础。像非常难的算法，而且你只要能拿一个铜牌就比较满意。例如网络流、A*算法、欧拉函数等高级算法不需要学，下面放一本书中的算法难度分类。

如果上面看起来比较费劲可以看一下下面这张，一位资深acmer的经验总结。

快问快答

博主以自己大学算法经历给各位大一新生总结出了几个比较常见的问题，以及对不正经问题的回答，可以让大一计算机新生少踩很多坑。希望对大家有所帮助。

Q:什么专业才能搞算法?

A:什么专业都可以搞算法，前提是计算机类的专业，其他专业的课程可能对算法没有帮助，人工智能专业毕业大部分是搞算法的，但是计算机科学与技术、软件工程、网络工程、人工智能、大数据等都可以学习算法。

Q:学习算法可以干什么?对学习有帮助吗？

A:学习算法的最终目的就是打比赛拿奖，拿到奖相当于给自己镀上了一层金，不管是考研还是找工作都是加分项，毕竟获奖的人都非常厉害，企业一般都会抢人。学习算法对学习有所帮助博主还是持中立态度，算法是计算机里面属于最难的了。学习了算法拿到奖说明你的能力很强，自然其他的课程也可以应对自如，但是一些acmer由于兴趣抛弃了课程，导致了挂科，这是得不偿失的，希望大家能够平衡学习时间。另外，大部分学校都会开设算法设计与分析这门课程，如果比赛中得到了比较好的奖项，这门课程有的学校可以申请免修，最终成绩直接90+。

Q:学习算法可以参加哪些竞赛？难度如何？

A:ACM国际大学生程序设计竞赛（ACM-ICPC）这是全球最知名的计算机程序设计竞赛，由美国计算机协会主办，参赛形式为团队参赛（3人），大赛分为区域赛、全球总决赛，只有经过层层选拔才能参加全球总决赛。区域赛一般在上一年的9-12月份举行，决赛安排在每年的3-4月份。

中国大学生程序设计竞赛（CCPC）这是中国自己的程序设计竞赛，地位仅次于ACM-ICPC，由教育部高等学校计算机类专业教学指导委员会主办的。参赛形式为团队参赛（3人），大赛每年春夏季组织若干场省赛和地区赛、一场女生专场赛，秋季组织一场网络选拔赛、三场全国分站赛和一场总决赛在中国这个比赛还是非常具有含金量的，办赛规模、规则、组织模式都是对标ACM-ICPC，国内认可度也是非常高的。

团队程序设计天梯赛（GPLT）是属于中国高校计算机大赛的竞赛版块之一，由教育部高等学校计算机类专业教学指导委员会等四个委员会联合主办。每届大赛分为模拟赛、初赛、决赛，初赛一般定于5月中旬至6月上旬，采用线上竞技方式进行。决赛一般定于7月举行，比赛为现场赛。采用PTA判题。难度分为3个梯级：基础级、进阶级、登顶级。以个人独立竞技、团队计分方式排名。

蓝桥杯全国软件和信息技术专业人才大赛，是由中华人民共和国工业和信息化部人才交流中心主办，国信蓝桥教育科技（北京）股份有限公司承办的计算机类学科竞赛，大赛分很多赛道C/C++、python、java、嵌入式、单片机、web等等，打算法的话就是软件赛。大赛分为省赛、国赛，只有省赛一等奖才能进入国赛。省赛一般在每年的4月份举办、国赛一般在每年的6月份举办。大赛为个人赛，以个人进行参赛。这几年蓝桥杯在计算机竞赛中比较火热，参赛的学生越来越多，大一新生比较适合参赛，也比较水，会暴力求解保底就是省赛三等奖，是加综测的不二之选。有的学校也把它当做ACM集训队的考核，大赛在国内的认可度也还算可以。

另外还有很多很多计算机的竞赛由于文章长度限制，不再一一列举，比如百度之星、传智杯、码蹄杯、大学生科技节中的算法竞赛、全国高校计算机能力挑战赛等等。

Q：怎样才能参加算法竞赛，如何报名？

A:像ACM-ICPC这样团队型比赛，需要你赛前组队，一般参赛名额都是ACM队员分配，每一个学校都有一个类似社团的组织，它的名称因学校不同名称也不同，例如：ACM集训队、ACM训练队、ACM实验室、算法协会等等。他们专门负责这样的竞赛报名、组织、训练。这样的组织一般都会有一名教练，负责对外申请参赛、带队参赛，还有一名队长，n名副队长，负责管理整个ACM队员，以及队员的培训、训练。如果想参加ACM-ICPC建议大一加入这个组织，经过他们的考核留在队里，后面就有机会打比赛了，报名费一般800RMB一队，这种比赛学校肯定都会报销，可以说是公费旅游。

蓝桥杯这种属于个人参赛，在官网上报名即可，任何人都可以报名，不需要ACM队员身份限制。报名费300RMB，进入国赛报名费也是300RMB，一般到了国赛学校就会给报销，有的学校省赛获奖也会给报销或者补贴。

蓝桥杯报名网站：蓝桥杯大赛 — 全国大学生TMT行业赛事

Q:学习算法用什么语言比较好?

A：一般来说使用C/C++语言的选手比较多，C++选手是最多的，因为大一入学都会学习C语言，其次有的专业会学习C++。按照博主感觉来说，C++真的比C语言好用，有一句话是这样流传的，当你学会了C++就感觉C语言好垃圾。因为C++有很多库函数可以随时调用，也有vector数组等等，比C语言简便多了。其次oi✌绝大多数都是C++选手，他们是靠信息学竞赛保送到大学或者有加分政策。这也体现了C++的简单性。其次Python的选手也是比较多的，Java的话，很少了，Java一般都是在开发上使用。另外博主提一嘴，oi✌他们从初中甚至小学就开始接触编程，实力非常强大，被暴打也算是正常，不要有心理压力。

Q:学习算法有什么网络资源可以利用？有没有推荐的？需不需要报课？

A:现在网络上有关算法的资源非常非常多，也包括有许多买课的。那么我们该如何选择呢，博主建议能不报课的尽量不报，毕竟算法课也是非常贵的。如果你加入了ACM队并且跟随他们的训练进度。那么就以ACM队的资源为主，他们会定时展开培训，组织训练，一般来说不需要报课，如果报课的话时间是非常紧的。如果你是单打独斗且自制力比较强，有每天都有刷题的意识，那么博主觉得也不需要报课，可以在B站寻找免费的资源学习。反而你自制力不强，一直想摆烂，需要有人约束你才能学习，那么博主就觉得报课比较好了。上面是博主个人观点，还请各位以自身情况为主。下面博主推荐几位比较好的B站UP主，博主一直看他们的视频学习：

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频

大雪菜的个人空间-大雪菜个人主页-哔哩哔哩视频

算法训练营的个人空间-算法训练营个人主页-哔哩哔哩视频

幻想家协会会长的个人空间-幻想家协会会长个人主页-哔哩哔哩视频

信奥编程罗老师的个人空间-信奥编程罗老师个人主页-哔哩哔哩视频

AcKing_专业的IT教育品牌的个人空间-AcKing_专业的IT教育品牌个人主页-哔哩哔哩视频

Turing_Sheep的个人空间-Turing_Sheep个人主页-哔哩哔哩视频

简单介绍一下这几位UP主，董晓老师是讲算法的，讲的非常非常详细，很像高中老师负责的那种感觉。大雪菜是AcWing算法刷题网站的创办者，主要讲AcWing中的算法题，2011年获得NOI金牌报送北京大学，是所有acmer的‘y总’。算法训练营是陈小玉老师，著作《算法训练营》(入门篇、进阶篇)《趣学算法》《趣学数据结构》，主要讲解算法。幻想家协会会长是前杭二教育集团信息学竞赛教练，研究算法竞赛十年，主要讲解codeforces中的题目。信奥编程罗老师是主要讲算法题的，讲的洛谷上的题非常不错。AcKing是一个IT教育网站，可以看一看他讲的免费的视频，还是非常不错的。Turing_Sheep博主视频主要是专攻蓝桥杯的，讲解蓝桥杯历年的真题，非常适合新手。

Q:算法刷题网站有哪些？主要以什么为主?

A:现在的刷题网站可所谓数不胜数，博主给大家推荐几个所有acmer都在用的刷题网站，排名不分先后，点击蓝字可以直接跳转。

一、AcWing

AcWing是B站UP主大雪菜2018年创建的，评测系统几乎0延迟，题目种类非常多，并且基本每一个题都有yxc的视频讲解，每周都有周赛，也会有讲解，深受广大acmer的喜爱。唯一地缺点就是有的题目需要购课才可以做，有需要的根据自己情况有优惠时购买，也是比较值的，毕竟属于个人网站，也是需要盈利的，知识付费嘛。

二、Codeforces

codeforcse网站是俄罗斯的，在访问加载时可能比较慢，但是说起codeforces，每一个acmer都会夸赞，每一次比赛出的题目非常非常质量，非常值得推荐。与ACM-ICPC题目风格非常类似，只要打ACM-ICPC的必然打codeforces比赛，打这个比赛的话可能需要你熬夜，毕竟与俄罗斯有时差，一般在22：35开始，比赛时长2小时左右。比赛一周至少一次，难度分为Div1、Div2、Div3、Div4，难度为递减，Div1难度是最高的，Div1与Div2不建议新手比赛，Div4是入门难度，里面的等级分rating是每一位acmer实力的象征。

三、首页 - 洛谷 | 计算机科学教育新生态

洛谷也是国内非常好的刷题网站，关键是它的题目全部免费，实时评测，开放测试数据下载，用户可以上传自己的解答，能够给别人提供解题思路，每一周也会有比赛，也有rating评定。

四、力扣 (LeetCode) 全球极客挚爱的技术成长平台

力扣中的题目也很不错，题目有很多大厂的面试题，许多求职者也在里面刷题。力扣的亮点为在写代码时，不用写主函数，只需要写函数即可，实际上力扣内部封装好了一个主函数，不需要格外实现主函数，非常方便。

五、牛客竞赛OJ_ACM/NOI/CSP/CCPC/ICPC_信息学编程算法训练平台

牛客是一个求职网站，它结合了面试的题目，后面慢慢也有了算法题——牛客竞赛，也是求职进大厂的非常好的网站。它的题库非常多，也很适合小白练习，面向各种竞赛，它的亮点在于牛客暑假多校训练营，里面集结了很多大佬参加暑假的集训，暑假多校的题目非常质量，它主要面向准备参加ICPC/CCPC等算法竞赛选手的暑假训练营。

六、“蓝桥杯”练习系统

蓝桥杯练习系统是面向参加蓝桥杯选手的练习平台，使用的人数虽然不及前面的网站，但是对于练习蓝桥杯来说也是非常好用的，“蓝桥杯”练习系统是蓝桥杯官网的练习题库，题面风格与蓝桥杯真题很类似，非常适合参加蓝桥杯的新手。

其次还有一些其他的刷题网站，博主不再一一列举，欢迎各位acmer在评论区补充，对于哪个刷题网站好用，我的回答是都非常不错，如果能坚持刷题就可以。还要看个人需求，觉得哪个好用就用哪个，上述属于博主观点，还请以自身情况为准。

Q:学习了算法以后可以干什么工作？会从事与算法相关的岗位吗？

A:学习算法可以从事很多岗位，基本可以从事所有的计算机行业，算法是计算机领域最难的一块，毕竟最难的都会了，什么开发岗对你来说学习起来不就简简单单了。其实学习算法的目的就是为了找一份好工作，一份好工作的敲门砖是acm奖牌。现在很多大厂都限制acm奖牌，算法工程师的面试条件也得要一块奖牌，所以学习了算法不一定从事有关算法的职位，最终目的是要拿到一块奖牌。算法工程师现在最低限度也要985/211的本科生了，双非的本科生成为算法工程师的概率很小，大多数去了开发岗，有了奖牌的双非本科生可以去一些中大厂的开发等岗位，也是很不错的。

（PS：图片来自老韩校长）

Q:大几搞算法比较好？如果没有成果还需要继续吗？

A:不存在大几搞算法比较好这个说法，可以说在大几学习算法的比重比较大，一年的学习算法可能达不到acm铜牌的水平，学习算法是一个日积月累的过程。一般学生的学习过程是大一沉淀学习算法，大二发力在算法竞赛上花费时间比较多，大三由自身情况而定，如果感觉还有很大的提升空间并且能够拿到奖且时间比较充裕的话，就可以再打一年比赛，如果大三需要考研、实习、科研等，训练的时间不充裕的话，建议就不要打比赛了。如果是学校acm队主力的话可能还要再打一年。大四基本都不会打比赛了，都要准备毕业设计或者考公考研了。如果是大一没有成果的话，是很正常的，大一一般首发的机会比较少，一个学校的名额是有限的，大部分名额分给了大二的队伍，还需要继续学习算法，为下一年做准备。大二没有成果的话，要看自身情况了，如果一心热爱且时间充沛，那就继续加油，再打一年。反之，没有信心下一年拿奖或者再拿也是一样的奖项，尽量放弃acm了，转去其他方向发展，acm竞赛对此时的你来说提升的程度不是很大了。大三没有成果的话就不建议再继续打了，除非是学校的主力，考个研它不香吗。

上面介绍完有关算法的问题，下面带领大家入一下门，算法评价标准最重要的就是时空复杂度，分别是时间复杂度、空间复杂度，在做题的是必须要考虑的问题，是评价一个算法好坏的标准，下面将会带大家认识一下它们。

时空复杂度

根据上面图书馆借书的例子，我们知道用了两种方法来查找没有登记的书，这两种方法的好坏评价标准为时间复杂度和空间复杂度。那么我们抛砖引玉，评价算法好坏的标准就是时间复杂度和空间复杂度。一般在题目开始上方会有此类限制例如：1s,128MB、2s,256MB，这是在告知你的算法设计的时空复杂度。如果超出了时间限制会Time Limit Exceeded（TLE）超出内存限制会Memory Limit Exceeding（MLE）。

时间复杂度：

时间复杂度是衡量算法执行效率的一个重要指标，它描述了算法执行时间随输入数据规模增长的变化趋势。时间复杂度通常用大O表示法来描述，它反映了算法在最坏情况下的性能。

大O表示法：用来描述算法的时间复杂度，表示为O(f(n))，其中 f(n) 是输入规模 n 的函数。
常数时间：表示算法的执行时间不随输入规模的变化而变化，记为O(1)。
线性时间：表示算法的执行时间与输入规模成正比，记为O(n)。
对数时间：表示算法的执行时间与输入规模的对数成正比，记为 O(logn)。
多项式时间：包括线性、二次、三次等，表示算法的执行时间是输入规模的多项式函数，记为 O(n^k)，其中 k 是常数。

时间复杂度的计算：

加法法则：如果算法由多个部分组成，总的时间复杂度是各个部分时间复杂度的最大值，即O(f(n))+O(g(n))=O(max(f(n),g(n)))。
乘法法则：如果算法中的两个部分是顺序执行的，总的时间复杂度是两部分时间复杂度的乘积，即O(f(n))×O(g(n))=O(f(n)⋅g(n))。
忽略常数因子：在大O表示法中，常数因子、低阶项和系数通常被忽略，因为它们对算法的增长趋势影响较小。

上面例子第一种方法一本一本的去检测最坏的情况下是10次，在程序中我们只需要一个for循环遍历一遍即可所以时间复杂度为O(n)，n=10。第二种方法叫二分，每一次对半查找，所以时间复杂度为O(logn)，n=10。

一般来说一个循环（for、while）循环就是一个O(n)，嵌套的话就是连乘。

for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		for(int k=0;k<n;k++){
			//操作
		}
	}
}
//上述时间复杂度为O(n^3)

如果不是嵌套，因为时间复杂度求的是最坏的情况，所以在整个程序里面抓大头，寻找最大的即可。如果是时间复杂度有一个系数例如O(2*n)，我们一般忽略前面的系数，记为O(n)。

for(int i=0;i<n;i++){
	//操作
}
for(int j=0;j<m;j++){
	//操作
}
for(int k=0;k<p;k++){
	//操作
}
//上述时间复杂度为O(max(n,m,p))

常见的时间复杂度

O(1)：常数时间复杂度，如直接访问数组的某个元素。
O(n)：线性时间复杂度，如遍历一个包含 �n 个元素的数组。
O(logn)：对数时间复杂度，如二分查找。
O(n^2)：如冒泡排序和插入排序。
O(2^n)：指数时间复杂度，如解决某些组合问题。

现在博主教一下大家如何判断是否超出时间复杂度，我们以1s限制为例，例如时间复杂度为O(n^2)，当n=1000时，带入大约是10^6，当得到的数值<=10^7，一定是可以解决此题的，1s在C++代码操作次数大约在10^7~10^8之间。当在这一个范围之内看你运气了，当大于等于10^8，这个算法就是不好的算法，完全解决不了此题。

空间复杂度：

空间复杂度是衡量算法在执行过程中所需的存储空间大小的指标。它与时间复杂度一样，是算法分析中的一个重要概念。空间复杂度通常用大O表示法来描述，它反映了算法在执行过程中所需的存储空间随输入数据规模增长的变化趋势。

大O表示法：用来描述算法的空间复杂度，表示为O(f(n))，其中f(n) 是输入规模 n 的函数。
常数空间：表示算法的存储空间需求不随输入规模的变化而变化，记为 O(1)。
线性空间：表示算法的存储空间需求与输入规模成正比，记为O(n)。
多项式空间：表示算法的存储空间需求是输入规模的多项式函数，记为O(n^k)，其中 k 是常数。
指数空间：表示算法的存储空间需求是输入规模的指数函数，记为O(2^n)。

空间复杂度的计算

总空间：包括算法执行过程中所有变量和数据结构占用的空间总和。
辅助空间：除了输入数据本身占用的空间之外，算法在执行过程中额外使用的存储空间。
递归栈空间：对于递归算法，每次递归调用都会占用一定的栈空间，其空间复杂度与递归的深度有关。

常见的空间复杂度

O(1)：常数空间复杂度，如简单的变量赋值操作。
O(n)：线性空间复杂度，如存储 n 个元素的数组。
O(logn)：对数空间复杂度，如二叉树的深度遍历。
O(n^2)：如动态规划算法中可能使用的二维数组。
O(n^k)：多项式空间复杂度，如 k 维数组。
O(2^n)：指数空间复杂度，如某些图算法或组合算法。

一般来说在题目中空间复杂度不需要考虑，除非开了很多似用非用的空间。只要不超时解决了题目，那么你就是一名优秀的acmer。

由时间复杂度推算法

下面推荐一个非常好用的方法，根据题目给的数据范围推出应该用什么算法，总结由AcWing算法刷题平台yxc总结，原文链接：由数据范围反推算法复杂度以及算法内容 - AcWing

好了，说了这么多，希望对各位大一萌新有所帮助，文章长度限制，有许多问题没有涉及到，欢迎大家在评论区补充。如果有不懂或者有疑问的地方，欢迎在评论区讨论，也可以给博主发私信，看到必回。算法竞赛是一个很好的机会，希望各位大一新生把握此次机会，好好的体验一把，过了这个村就没这个店了。写此篇博客的目的是为了帮助大一新生进行算法入门解答，希望学弟学妹们少走博主走过的弯路。

执笔至此，感触彼多，全文将至，落笔为终，感谢各位读者的支持，如果对你有所帮助，还请一键三连支持我，我会持续更新创作。

标签：学习,竞赛,复杂度,新生,ACM,蓝桥,算法,大一
From： https://blog.csdn.net/m0_73633807/article/details/141431395