你当前所在位置:首页 > IT技术探讨 > 学编程必看:这些算法你掌握了吗?

学编程必看:这些算法你掌握了吗?

许多初学软件开发的同学,认为学开发就是学各种编程语言,或者认为能学到最新的编程语言、技术和标准就是最牛叉的。其实这种认知是有失偏颇的。

 

编程语言固然重要,但是计算机算法和理论更为重要,因为计算机编程语言和开发平台更新迭代日新月异,但万变不离其宗的是那些算法和理论。


算法1算法——程序员的内功

 

形象点比喻:

 

算法、数据结构、编译原理、关系型数据库原理和计算机体系结构等这些算法和理论知识体系属于程序员的“内功”。

 

各种各样五花八门的编程语言、技术和标准则更是“外功”。

 

只会追求最新语言,懂些花架子用来炫耀,却没有过硬内功的程序员,是不可能成为高手的。

 

算法内功高手

 

也许有人会问:“今天计算机这么快,算法还重要吗?”

 

其实永远不会有太快的计算机,因为我们总会想出新的应用。

 

在网络时代,信息量越来越大,越来越多的挑战需要靠卓越的算法来解决。

 

关于程序员是否必须懂算法的问题,IT圈流行的这样两张动图足矣给出答案:

 

A、懂算法的程序员:


懂算法的程序员

 

B、不懂算法的程序员:

 

不懂算法的程序员


算法2如何学习算法?

 

一、看书

 

如果你是小白,你连常见的数据结构,如链表、树以及常见的算法思想,如递归、枚举、动态规划这些都没学过,那么,建议你先去找本书,先把最基础的知识搞懂。

 

你需要搞懂的最基础的知识包括:

 

1、常见数据结构:链表、树(如二叉树)。

2、常见算法思想:贪婪法、分治法、穷举法、动态规划,回溯法。

 

这里推荐一本能比较系统的学习算法的书籍:《算法导论》。

 04.jpg

 

这本书深入浅出,全面系统地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。

 

二、刷题

 

学习算法有没有捷径?如果说有,那么这个捷径就是脚踏实地多动手去刷题,多刷题。

 

在做题的时候,我们要追求完美,要力求一题多解。千万不要把一道题做出来之后,提交通过,然后就赶紧下一道。

 

如果自己实在想不出来其他办法了,可以去看看别人是怎么做的,之后,遇到类似的题,你就会更有思路,更知道往哪个方向想。千万不要觉得模仿别人的做法是件丢人的事。

 

可以从简单暴力入手做一道题,在考虑空间与时间之间的衡量,一点点去优化。

 

道理不多说,赶紧举个例题:

 

问题: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?

 

▼方法一:暴力递归


算法-暴力递归


这个方法的时间复杂度很高,达到指数级别了。

 

▼方法二:空间换时间


算法-空间换时间

 

这个用空间换时间的方法可以大大缩短时间。

 

▼方法三:斐波那契数列


算法-斐波那契数列

 


这个方法可以把空间复杂度弄得更小,不需要HashMap来保存状态。


算法3程序员必须掌握的五大基础实用算法

 

算法一:快速排序

 

快速排序是由东尼·霍尔所发展的一种排序算法。

 

在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

 

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

 

算法二:堆排序算法

 

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

 

堆排序的平均时间复杂度为Ο(nlogn) 。

 

算法三:归并排序

 

归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

 

算法四:二分查找算法

 

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。

 

搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜 素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。

 

如果在某一步骤数组 为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为Ο(logn) 。

 

算法五:BFPRT(线性查找算法)

 

BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分 析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂 度,五位算法作者做了精妙的处理。

 

算法图


算法4结束语:

 

算法是程序员在追求高速度,高效率的路上不得不学的“内功”,而且算法几乎是所有大厂技术面试的必考项目。学好算法和数据结构,无论是应对大厂面试,还是职业长远规划,甚至对自己的逻辑能力的提升,都有极大的帮助。

 

小伙伴们,如果你能耐心看到这里,并且能大概看懂本文的50%的内容,那么,恭喜你!你已经走在成为程序员的路上了,你可以选择自学或参加职业培训。

 

如果你看不太懂,但对这些感兴趣,没关系,可以找一家有资质的专业的针对零基础的IT职业培训学校,让老师手把手教你从零学起。

课程预约