当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 > 如何提升数据结构方面的算法能力

如何提升数据结构方面的算法能力 时间:2020-11-09      来源:华清远见

如果要写出简洁而高效的程序,每个程序员都绕不开数据结构和算法这部分。那么怎么提升数据结构方面的算法能力呢?我认为主要是从基础和应用这两方面着手。

基础部分指的是对于基本概念是否清晰理解,基本的数据结构是否完全掌握。

例如:

什么是线性表。线性表的顺序表、单链表、双链表、循环链表的结构定义和操作是否能够代码实现;

什么是栈、顺序栈和链式栈的结构定义和操作是否能够代码实现。

什么是队列、顺序队列和链式队列的结构定义和操作是否能够代码实现。

什么是树、二叉树的各种遍历是否能够代码实现。

什么是图、图的表示和遍历算法。。。。

数据结构的知识掌握了才正式的深入算法知识。因为算法是基于某种选择的数据结构的。

对于算法的时间复杂度和空间复杂的的理解和计算,对于常见算法的掌握。需要掌握基本的排序算法和查找算法,例如查找的二分查找、索引查找、哈希查找;经典的十大查找算法,选择排序,冒泡排序、插入排序、堆排序、快速排序等等,常用要能够代码实现。

数据结构知识和算法知识是我们实际解决解决问题的基元,如何提高算法能力就涉及如何将数据结构和算法应用于特定的场景,以及在实际使用中该如何选择对应算法。

算法的精髓在于分析和比较,要想清楚在什么时候,为什么使用这个算法。

比如说平衡搜索树,我们为什么要平衡呢?因为平衡可以减小树的最大深度,从而减小搜索时的最坏时间复杂度。但我们不做平衡又会怎么样呢?又适合哪些场景呢?平衡的代价和搜索的代价如何权衡?比如说我们的数据结构不在内存中,那这个时候重新平衡的代价就要大的多,这也是为什么多数数据库系统并不采用avl和红黑树的原因之一。那我如果就要用avl做个disk的数据库又会怎么样呢?可不可以呢?其实也可以,但我们算法和数据结构也要作出相应的调整。

又比如说二叉堆的插入操作的最坏时间复杂度是O(log n), 因为有可能一直换到根结点,但平均时间复杂度是多少呢?是O(1), 想想看是为什么?为什么会是收敛的呢?十分类似的思路,在n个数中找出top K个数的复杂度是O(n)。我觉得这些思考和证明的过程才是算法的精华。

当然了知道了问题的解决核心思路又给出了具体的解决方案,剩下就是不断去实现,不断去多见多解决其他问题的重复过程,你会发现实际应用中存在某些结构变化或者是算法方面的平衡,是考虑时间优先、空间优先、为了效率牺牲稳定等等问题。比如最简单的一维数组排序。最最简单的方法就是冒泡,这就是一种穷举,所以复杂度很高。箱式排序复杂度就降低了,但是他的代价是需要额外空间了,这就是空间换时间。再接下去还有二叉树排序,他的空间代价更大,结构更复杂, 所以就会更快。再接下去,如果我牺牲稳定度,采取不稳定排序,我还能采取更快的快速排序。那么在遇到实际应用时该如何抉择。

只有基础与应用并行,那么数据结构方面的算法能力就会不断提升。

上一篇:有嵌入式基础的毕业生可以做嵌入式工程师吗?

下一篇:C++相比其他语言到底难在哪里?除了性能优势,还有什么优点?

热点文章推荐
华清学员就业榜单
高薪学员经验分享
热点新闻推荐
前台专线:010-82525158 企业培训洽谈专线:010-82525379 院校合作洽谈专线:010-82525379 Copyright © 2004-2022 北京华清远见科技集团有限公司 版权所有 ,京ICP备16055225号-5京公海网安备11010802025203号

回到顶部