算法与数据结构初学概览

发表于 | 分类于 | 阅读数

从最初接触IT行业的时候就已经开始了解数据结构与算法相关的知识了。但无奈没有学习过，只是知道零零散散的知识。借着朋友学习这方便的东西，带动我也想重新系统的学习下这方面的知识了。但不是为了应试，而是能真正学习到解决问题的详细方法和锻炼自己的思考方式。

在18年开始读专升本的时候，学校的课程其实已经讲过数据结构的知识了。但记的并不牢固。自己也有买过很厚的数据结构和算法相关的书籍，但是真的提不起兴趣学习。最主要的学习内容应该主要来源于源码相关的知识，比如近一段时间学习redis object中encoding的11种数据结构，学习其中的quicklist、skiplist等等。但是了解学习的非常浅。

这次主要学习也是以极客时间上课程的指引进行学习的，有覃超（他很懂星际争霸）和王争两个课程。但更多的还是自己要多看书、多练习吧。

接下来的学习学习中，我会尽量将学习到的数据结构和算法的知识记录下来，并且提供我对于一些问题的解法和思路。

Data Structure 数据结构

  • Array 数组
  • Stack/Queue 栈 队列
  • PriorityQueue(heap) 优先队列 堆
  • LinkedList(single/double) 链表 单/双向
  • Tree/Binary Tree 树 二叉树
  • Binary Search Tree 二叉搜索树
  • HashTable 哈希表
  • Disjoint Set 并查集
  • Trie 字典树
  • BloomFilter
  • LRU Cache

Algorithm 算法

  • General Coding 没有用归纳好的方法
  • In-order/Pre-order/Post-order traversal 基于树的遍历 前序 中序 后序
  • Greedy 贪心算法
  • Recursion/Backtrace 回溯 递归
  • Breadth-first search 深度优先
  • Depth-first search 广度优先
  • Divide and Conquer 分治算法
  • Dynamic Programming 动态规划
  • Binary search 二分查找
  • Graph 图

时间复杂度/空间复杂度

略过数学方面的基础知识

Big O notation

  • O(1) Constant Complexity:Constant常数复杂度
  • O(log n) Logarithmic Complexity 对数复杂度
  • O(n^) Linear Complexity 线性时间复杂度
  • O(n^2) N square Complexity 平方
  • O(n^3) N square Complexity 立方
  • O(2^n) Exponential Growth 指数
  • O(n!) Factorial 阶乘

注：只看最高复杂度算法

master theorem 主定理

Application to common algorithms

01

算法脑图

02

数据结构脑图

03

学习方式

《outlier》一万小时训练法

  1. 拆分知识点
  2. 刻意练习
  3. 寻求反馈
  • Clarification 充分理解题目
  • Possible solutions 更多的解决方案，并不只是用思考到的第一种解法进行解题
    • compare （time/space） 从时间/空间复杂度进行学习
    • optimal 加强训练（至少刷五次）
  • Coding 多写
  • Test case 给程序的正确性（场景）进行尽可能多的测试

至少五遍刷题法

第一遍

  • 五分钟，最多十五分钟，读题、思考
  • 如果没有思路，直接看。看多种解法，比较优劣
  • 背诵和默写

第二遍

  • 马上自己写
  • 多种解法比较、体会->优化

第三遍

  • 一天后重复做题
  • 不同解法的熟练成都->专项练习

第四遍

  • 一周后进行练习

第五遍

  • 面试前一周的恢复性练习
投食入口