Data structures & Algorithm

数据结构和算法虽然对于目前的工作貌似没有太大作用,但是自己对这一快不清除,就如一块石头压在心上,所以也必须要解决,虽然很难,但是慢慢攻克吧。

网上一搜算法,绝对是各种文章,视频,还有什么教程培训之类的,暂不谈质量如何,首先对于我这种,时间是有限的,所以只能选择一个,最合适的一个,有些虽然好但是难,因为我也不是要一定深入到什么程度。能写基本的算法,有数据结构有一定认识就好了。

https://github.com/thejameskyle/itsy-bitsy-data-structures 从这开始吧,算是入门启蒙吧。

资源

WIKI

Algorithm为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。
算法中的指令描述的是一个计算,当其运行时能从一个初始状态和初始输入(可能为空)开始,经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。

https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95 WIKI 讲的很清楚
https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA 图灵机的WIKI

基本概念

特征:

  • 输入
  • 输出
  • 明确性
  • 有限性
  • 有效性

设计模式:

完全遍历 -- 不完全遍历

  • 分治法
  • 动态规划
  • 贪婪算法
  • 线性规划
  • 简并法

实现:

  • 递归
  • 迭代
  • 顺序计算、并行计算、分布式计算
  • 确定性算法、非确定性算法
  • 精确求解、近似求解

算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务

复杂度

  • 时间复杂度 算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做

算法执行时间的增长率与f(n) 的增长率正相关,称作渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。

常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

  • 空间复杂度 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

数据结构

思考这些的时候,其实数据是对应在内存中的位置的。

访问accessing 查询searching 插入insert 删除delete

不同的数据结构对应不同的操作有不同的效率。即时间复杂度和空间复杂度是不同的,需要根据自己的应用情况,选择不同的数据结构。

  • LIST
  • 哈希表 HASH TABLES
  • 栈 stack
  • 队列 QUEUES
  • 图 GRAPHS
  • 链表 Linked LIST
  • 树 tree 吼TM多

外在的即写出来的表现形式,与内在的数据结构形式与实现。 注意分开理解。

实践

对不同的数据结构做理解和实现,