xiaolanyan / algolearningnotes

This is the learning note for algorithm

Algorithm Learning Notes

this is my algorithm learning notes

Grokking Algorithm

Chp1 二分查找，大O表示法

二分查找的时间为O(logn)，简单查找的时间为O(n)。需要搜索的元素越多，前者就比后者快得多

算法运行时间不是以秒为单位的，是从其增速的角度度量的。

Chp2 数组，链表，选择排序

• 数组：数组所有元素在内存中是相连的。插入、删除元素的时候需要所有元素移动。数组在提取时具有优势，可以迅速找到数组中任意元素。
• 链表：链表中的元素可存储在内存的任何地方，每个元素都储存了下一个元素的地址。链表在插入元素时有优势。但是链表无法直接访问某个位置的元素，必须先访问元素#1，获得元素#2的地址，访问元素2...然后访问到像访问的元素。
• 选择排序：先遍历序列找出中最大的，放到第一个，再遍历剩下的找到最大的，放到第二个...需要的时间为：O（n^2）

Chp3 递归，栈

• 递归条件：函数调自己
• 基线条件：函数不再调用自己，避免出现无限循环
  def countdown(i)
print(i)
if i <=1: #递归条件
  return
else:#基线条件
  countdown(i-1)
  
• 栈：压入弹出（后进先出），可以思考一些递归函数的调用栈

chp4 D&C(Divide and Conquer), 快速排序

• 快速排序： ** **：
  
  1. 选择基准值
  
  2. 将数组分成两个子数组：小于基准值的元素组成的子数组和大于基准值的元素组成的子数组
  
  3. 对这两个子数组进行快速排序（回到第1步）
  ** 代码：
  

chp5 散列表

chp6 广度优先搜索

• 广度优先搜索
• 队列

chp7 狄克斯特拉算法

步骤：
(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。
(2) 更新该节点对应的邻居节点的开销，其含义将稍后介绍。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。

chp8 贪婪算法

• 步骤：每一步都找这一步的局部最优解
• 优缺点：贪婪算法是一种近似算法，优点是速度快，缺点是可能并不是最优解

chp9 动态规划

• 背包问题：
• 最长公共子串

chp10 KNN