介绍

参加了Laioffer 2018年底11月的Data班，整理了一下学习笔记。Laioffer学费不菲，但是提供的思路还行。像其他网课一样，我一如既往的虎头蛇尾，兴趣全无。

课程问题

课下时间：至少70%放在python coding。课下不需要看统计知识

机器学习：

告诉老板，我们大概有5%的人要退订服务了
告诉老板，不知道有多少人会退订服务，但是可以告诉你为什么这些人要退订服务

如果P值等于0.05：

因为0.05是type1，所以可以反问为什么我们要把犯一型错误的概率定在0.05？如果很严重的话我们可以定的再小一点，如果不在乎的话可以定的大一点。

MLE在什么时候不work:

样本量太小会有问题。【100万人中求样本方差/样本均值，但是只有一个观测值】【均匀分布的估计】

常见问题

问：选定模型需要理由吗？

答：根据不同的Assumption会有不同的模型

问：所有loss-function都是关于 $\epsilon = y-\hat{y}$

答：有些模型写不出来loss-function（比如Tree-based）。但是如果能写出loss的，都是要优化xxx，就会跟error有关系。

问：均值和期望不同吗？

答：mean和expectation两者是完全不同的概念. 即使对应的数值一样，他们表达的意义是完全不同的. 简单地说, mean是针对实验样本来讨论的统计量, 是与具体数据有关的, 你的数据不同，Mean就不一样. 而expectation是对一个随机变量的数学特点的描述, 它更多表达的是在样本无穷的情况下会体现出的特点. 无论你某一次的样本数据是什么样，无论你某一次计算出来的mean多么不靠谱, 这个随机变量的expectation应该都是不变的. 但是如果你可以找到整个Population的所有情况来计算mean (这件事应该是不可能发生的), 那么它应该与expectation是一样的.

问：为什么线性回归的loss用平方？

答：直接对应线性方程噪声的高斯假设 。如果写出来似然函数然后用MLE的方法, joint pdf :

$f(y_1,...y_n|x_1,...x_n) = (\frac{1}{\sqrt{2\pi}\sigma})^nexp\{-\frac{1}{2\sigma^2}\sum(y_i-x_i\beta)^2 \}$

会发现最后的部分是平方损失，而MLE就是让那部分最小。

做题写代码之前，先想一些特殊的（test）case，让自己的code至少可以满足我们能想到的case。

一般的证明算法正确的方法：数学归纳法

问：L1 L2 loss的区别以及应用场景：

字典的空间复杂度：key + value

Q: 如何解决Confounder：

A: 如果是regression model的话，要把可能的confounder都包含在model里；如果是two group test的话，要matching on confounder或者segment by confounder。

P-values under the null are uniformly distributed

广泛的知识

机器学习的能力范围：

给定一个x，并不能给定一个具体y【这也是为什么模型会犯错误】其实给的是y的一个分布【第一步】。然后我们再从y的分布中获得一个y的具体值【第二步】。
所以有的时候结果不好，可能模型是对的，并且已经做到了极限。是我们自己搞砸了第二步

模型不能脱离与数据而存在【不能单独讨论好坏】

理解：考试成绩[error] = 平均水平[bias2]+某次具体发挥[var]

Bias表示的是大量实验中的平均偏差[model在训练数据有稍微变化下的平均输出结果与真实值相比，得到的平均准确性]
Var更强调的是某一次出现的偏差[某一次model的数据结果与这个model的平均水平的差距的平方的期望]
Bias和Variance是无法被计算的
模型越复杂，var越大。因为提取的信息不具有代表性，数据和模型之间的gap就会越来越大
女娲造人。先骨骼再填肉。骨骼就是model的assumption，填肉就是不同的training data. 每个靶图都是很多次不同的填肉，然后再观测眼睛的颜色。
Jason认为 $\lambda$ 属于骨架的一部分，虽然他是个参数…

我们最小化training error 是暗含了一个假设：最小化training error就是最小化testing error。但这个假设不成立，这也是过拟合的来源。我们发现过拟合的时候造成不稳的原因是var比较大，所以我们可以加一项来控制方差：Regularization

Ridge Regression: L2-penalty LASSO: L1-penalty
实际用的时候LASSO不是很稳定，作为最大缺点，二阶在工业界更常用

CV：

可以用来hyperparameter tuning，来选 $\lambda$ [grid search/ random search]
可以来 validate model selection 【只能选定某一种模型，而决定不了参数】

Encoding 的方式：

Label-Encoding 把factor变成数字 ordinal的情况
One-Hot-Encoding

问：如何判断两个连续变量是否独立？

答：把连续变量离散化，根据range划分成小格子

问：如何判断一个连续一个离散变量是否独立？

答：试着去证明两个CDF是一样的。KL-divergence

Map-Reduce存在的问题：

多个任务串联的时候，需要将中间文件写入磁盘，又得读出来。比较慢。

未解决问题

线性回归的线性到底如何定义？指数分类组？

问：为什么选择残差平方作为loss，为什么不是四次方？

答：好像跟什么高斯分布有关系？

问：为什么不用垂直距离做误差？

什么叫OA？

什么是Backtracking？公共课Class40讲了

Linear Regression

线性回归 $y = ax+b$

如果给一个点，欠定方程under-determined equation
两个点：适定方程well-determined equation
多个点：超定方程over-determined equation

五个Assumption: ？？？

关于factor的coding有很多种，不仅有one-hot-coding.(Label encoding/target encoding 比较fancy)

One-hot-encoding: 保证了各个factor之间的距离都是一样的（ $\sqrt{2}$ ）
followup：等边三角形也保证了三个factor距离一样啊，并且还是二维的
答案：one-hot-encoding 想要的更多的是方便interpret

followup:出现了很多里面没有的新类别该怎么办
答案：1.新增一个other列

followup：如果有一个class有非常多的值，还可以做one-hot-encoding吗？
答案：产生原因：Feature过多的时候，overfitting（需要更多的数据）
	解决办法：1. 其他encoding（frequence-based encoding）
			2.做个聚类，重新用更小的类别数字代替原先的class

问题：为什么不能直接将ABC三个班级code成为123？
答案：这个model基于距离的（线性模型就是）。但是概率模型（比如Tree-based）就没事

朴素贝叶斯： 是否是花？给定feature (F1,…Fn) 现在要求花是哪一类？需要计算P(C|F1,…Fn) 但是这些Feature同时出现的情况可能不存在。
Assumption: P(Fi|C) 和 P(Fj|C)是独立的【条件独立】
实际例子：Fraud Activity Detection, 为了分类

统计中的随机性（randomness）：

每一次出现都是随机的不可预测的
这些随机的背后存在着特定规律 （所以如果一个参数属于某个参数空间，传统统计中认为就不属于随机变量）【参数不是随机变量】
不是所有不知道的量都是随机变量

如何用random(5)[取值0,1,2,3,4]实现一个random(25)？

可以把它写成一个方块，看成面积, $5X_1+X_2$
random(7)怎么办?

CLT的来源背景：大量相互独立的叠加，并且每部分对在综合影响中所起的作用差不多。

为什么正态的误差服从正态分布？我觉得是因为好算F或者t之类的检验，Jason说有可能是因为我们认为大自然的噪声是独立同分布的，所以他们叠加是一个正态…

高斯假设是关于 $\epsilon$ 的，或者是关于 $y|x$ .

Logistic Regression

当y是离散的时候，为什么不能用linear regression？
遇到的问题：

y|x的分布不符合高斯分布

解决办法：

将y=0/1 变成0~1的概率p，再用线性拟合

遇到的问题：

很远的地方的数据会变成leverage point，将线拉的很扁。【可以思考赋予leverage点不同的权重】很确定的点可以小一些权重，而那些模糊区/0和1交叉点的地方需要给一些大的权重。

解决办法：

变成一条折线，早早的就到了1然后一直是平的。【图形角度入手】发现logistic正好符合sigmoid形式，并且指数组也有很多好性质

【从值域的角度理解】

开始的是离散的0和1，我们假设服从伯努利分布Ber§变成probability属于[0,1]，然后变成odds $\frac{p}{1-p}$ 属于[0,inf] ,然后 $log(\frac{p}{1-p})$ 属于[-inf,inf]

多分类问题可以用

one vs all
softmax

局限性：仅支持一种非线性。

loss function，通过似然函数（joint pdf）计算出来：

$min\ log(p) = \sum_{i=1}^n[-y_ilog(\frac{1}{1+e^{-\beta x}})-(1-y_i)log(1- \frac{1}{1+e^{-\beta x}})]$

Sss

Binary Search

二分查找/折半搜索，针对已经排好序的序列。

用两个指针left和right进行操作，每次都比较mid = (left+right)/2 和目标值

时间复杂度log(N) 空间复杂度 constant（每次只在操作left right mid 三个指针）

如果mid < target, left = mid + 1
如果mid = target, 找到了
如果mid > target, right = mid -1
如果left >= right，就退出。如果left = right = target就返回left/right，如果不等于就退出。

如果是多维的情况，也变成一维的情况，用两个指针来做。

Followup1: 寻找数列中最接近某个数值的数的index:

此时，原本的 left = mid + 1/ right = mid -1 就要变成let = mid/ right = mid 因为保不齐目前这个mid虽然不是答案，但是是和答案最近的那个，所以不能轻易抛弃他
但是这样的话有时候会进入死循环，因为mid根本不变。所以至少保证三个数再开始跑，left < right - 1
并且需要postprocessing，因为循环结束的时候，两个指针有可能不重合，而是距离为1，所有要对left和right再检测一遍
python三目运算符：return left if 左小于右 else right

Followup2: 寻找数列中最先出现某个数的index:

要用followup1的判断方法: left < right - 1 为什么呢？
如果mid < target, left = mid。否则， right = mid
最后postprocessing, 先检测left，再检测right。【反过来不行，因为我们要返回第一次出现的index】

Classic判断方法：left <= right. 变种：left < right - 1. 判断是否可以用classic就是看循环中有没有mid = right 或者 mid = left 这种危险语句

Followup3: 寻找数列中最后出现某个数的index:

跟2差不多
如果mid > target, right = mid。否则， left = mid
最后postprocessing, 先检测right，再检测left。

Followup4：Search in rotated sorted array:

rotated sorted array就是原本一个有序的数列，从中间砍成两半，然后调换他们的位置
有个好性质，那就是无论切掉几部分，剩下的拼起来还是一个rotated sorted array
通过left right 和mid的相对大小来确定mid左面/右面是一个sorted array

Linked List

线性数据结构

Linked List在内存中不一定是紧密相连的（不需要）

单链表：特点是链表的链接方向是单向的…只能访问下一位。单链表的定义还包括有头有尾，最后一个node.next = None 不会出现首尾相连的情况

Linked List 包含

一个数据域，存放了数据
一个链域，存放了链表下一个地址位置

刚开始创建的时候，self.next = None 因为还没有被链进链表…而在创建节点的时候肯定需要给一个val。所以init(self,val)就可以了

做swap的时候有时候想改变Node的val，但这样其实不符合职业操守，建议把val看成read-only

Singly Linked List

遍历Traverse

问：关于为什么这个函数要写成在class外面的free function而不写在class里面？

答：我的理解是因为Traverse这个功能并不是针对某一个具体的链表而设定的，所以不应该被定义在某个class的内部。定义成free function，也还可以遍历其他的链表。

Add

添加元素的话一定要返回头结点head，要不然修改会找不到【如果在头前面加的话，没办法知道新的head】

要加fakehead，因为头结点不存在前驱节点，万一要在0位置操作的话

可以插入fake_head，整个代码清晰起来，因为所有节点都存在了前驱节点

Remove

如果删除之后将node.next = None,就会直接被Garbage collection清除掉。因为它没有被任何node指向，也没有指向任何node。

要加fakehead，因为头结点不存在前驱节点，万一要在0位置操作的话

Merge two sorted linked list

要添加fake_head 效果很棒

我开始想每次都新建一个listnode，但这样会使得空间复杂度为O(N1+N2)。所以用指针操作比较好，差距还是挺多的

时间复杂度O(N1+N2)；空间复杂度O(1)

Find middle node in singly linked list

先问一下面试官，如果长度是2K，middle node的定义是什么？

Doubly linked list

增添删除操作都是locally

但是还是需要fake_head 解决头结点不存在而需要特殊讨论的问题

add

fake_head.next = head; head.prev = fake_head 注意一定要加上head.prev 这句话也要加上。并且在return之前要加上：fake_head.next.prev = None; return fake_head.next

Recursion

用归约来解决问题

一个小🌰：斐波那契Fibonacci Sequence：找第n位的元素

建立一个list来存放所有的数据
- 时间复杂度：O(n) 空间复杂度：O(n)
用两个数字去模拟过程，a,b = b, a+b
- 时间复杂度：O(n) 空间复杂度：O(1)
Recursion：定义两个基础case F(0) = 0; F(1) = 1

递归一个好处：

平铺直叙，怎么想的，基本上代码就是怎么写，顺序都一样
有些问题用递归来写很清晰，实现起来很快
虽然一般来说性能可能没有直接写好，但是我们可以在实现之后再修改。

Recursion 一个重要的点在于：找到Base Case

对于递归传递参数我一直有个误区：结果传递到了哪里

其实无论是一个数还是一个数据类型，都需要准确的传递地址。一个数的话，一般在函数外先定义，然后函数内部加一行global x 。

如果是List的话应该不用global 因为地址是可以被查找的。

一个有趣的错误：

class Solution:
  def __init__(self):
      self.x = 0
  def add(self,y):
      self.x += y
      return self.x

s = Solution() s.add(3) #打印出来3 s.add(5) #打印出来8:hexoPostRenderEscape–>

这时候相当于用到了global变量，而global变量被存了起来。有一种解决办法是每次都重置这个global变量，但是如果频繁调用s = Solution() 看起来微蠢，可以写一个wrapper包

def ResultWrapper:
    def __init__(self):
        self.max = -1
        self.solution = None
def xxx:
    res = ResultWrapper()
    ......
    return res.solution

判断是否是二叉排序树：

从上到下传递range
中序遍历 + 用一个global最大值
从下往上传递左右子树最大最小值 + 左右子树是不是BST

reverse singly linked list

head.next.next = head 这一步好强啊

有一个重要思想 我们对于多个点的变量（比如node.next.next.prev），一定要看他会不会是None，如果可能会是的话，我们提前加一个判断，以及情况处理。

感觉这个算法厉害之处在于…recursive的部分不影响原来的head部分… 可以通过head.next 来获取recursive链表的最后一位

Non-linear Models

Confusion Matrix

True Positive 这里的True指的是说的错没错。Positive指的是猜的是1还是0
Precision：在你说的正确里面，有多少是真正正确的。（你给出的答案，准确率是多少）
Recall：所有positive里面，有多少被找到了（召回了多少）。recall = 曹操
accuracy：两种正确/四种情况
F1-value = precision 和 recall 的调和平均数

如果是守旧的人，不希望的事情是spam folder里面有重要文件，而可以忍受spam进入邮箱。那么此时分类的时候就是重视recall而觉得precision没那么重要

ROC curve

用logistic的时候我们采用了人为的threshold。而采用这个可以直接反映数值
我们不想人为引入threshold
model不变，testing数据也不变。women画出一个随着threshold变化的准确率曲线
对于imbalance class也可以用
蓝色阴影面积决定了好坏。最差0.5（random），最好1。因为如果小于0.5的话，我们取个反就变成一个大于0.5的好分类器了
这个概率的解释：真实值排在错误值前面的概率（positive example is ranked more highly than a random chosen negative example）

Decision Tree

以前机器学习，只能convex才可以做。现在non-convex也可以做（比如神经网络）

目的：使得总体混乱程度降低

ID3用了Entropy： $I_e = -log_2p_i$ ; $H = \sum_{i=1}^n p_iI_e$

C4.5用了GainRate

ID3倾向于对那些有很多分类的变量给更高的关注

CART：Gini impurity

为什么说决策树不是线性模型？ $X_i$ 对y的影响只取决于 $X_i$ 的大小以及他前面的系数，与其他X都无关。但是决策树还与他的位置有关（也就是变量之间的关系也很重要spliting and priority）

问题：强烈过拟合。

解决办法：

预剪枝/后剪枝（pre/post-prunning）
Ensemble: 好多棵树一起做 Bagging/boosting(有点复杂)

Random Forest

一棵树容易over-fitting

解决办法：向模型中加入随机性

有放回的抽样——保证每个元素分布一样。选取的K一般是总共feature的平方向下取整

一般来说不需要pruning

Feature importance value in Random Forest: 但从这个公式里面看不出来影响的正负

$Importance(i) = performance(RF) - performance(RF^{random(i)})$

这个performance可以是MSE/Miss classification cost(用OutOfBag的方法，而不是在添加了这个变量之后的entropy变化)

SVM

Maximize the minimum margin

也可以做regression，对应的loss：hinge loss

Intuition : 希望边界直线处，分界更加清晰

缺点：

sparse的情况没有logstic好
正常分类没有random forest好

优点：

没有维度灾难，高维上依旧work
数学上完备

KNN

没有training stage，上来就开始test

也可以做regression，对最近的N个取均值，但正常一般用来classification

K可以被视作一个超参数，无法通过求出来

有个大问题：每一个预测需要O(N)的时间【计算N对距离】
解决办法：以空间换时间，先存好不同颜色的几个区域，local-sensitive-hashing。这是一个approximate的方法，在边界的时候容易出问题

Feature Selection

先用PCA，但是PCA破坏物理意义

目的：

为了减少overfitting
为了找寻重要的变量，去掉useless variable

有时候一个团队可能会选择解释性好而准确性差一点的模型，因为如果哪一天黑箱模型闹脾气不工作了，谁也没办法…

工业届还倾向于多个model来做一件事情，而不是一个model。这样可以多个team一起合作

一个做法：去除变量之间相关性

有人用correlation

Ridge 倾向于把几个相关性高的变量系数取的一样。因为在a+b= constant 的时候， $a^2+b^2$ 最小就是a = b 的情况。

PCA

协方差越大能够增加信息量，在很容易变化的一个量上面，如果我们能给出一个具体的值，那么对不确定性的影响降得会最多

首先保证了原信息损失最小，副产品是去除了相关性。并不是奔着去除相关性去的

记得要scale

K-means 聚类

分类问题：原来有类别，现在新的数据，我们需要知道它是属于哪一类

聚类问题：原先没类别，想知道谁和谁更加接近

具体操作过程：不停地更换中心

另一种LDA（Latent Dirichlet Allocation）

排序算法

冒泡排序Bubble Sort

从第一位开始，相邻的比较大小并交换。第一次一定会将最大的数字移到队列最后面。比较了n-1次，第二次开始要比较n-2次…以此类推

时间复杂度：O(n^2) 空间复杂度：O(1)

选择排序Selection Sort

In-place comparison sort. 不需要额外空间/需要很少额外空间
It has O(n^2) 复杂度，最好最坏都一样，但是比bubble需要的swap的次数更少
甚至比插入排序insertion sort 还要糟糕
When auxiliary memory is limited, 就可以选它了

时间复杂度：O(n^2) 空间复杂度：O(1)

插入排序 Insertion Sort

把第一个数字看成一个有序数列。从第二个数字开始，每次都在有序数列中找到自己的位置并插入。一个一个插入，直到原先全部的数字都被插入到了数列中。

原本硬写，时间复杂度：O(n^2) 空间复杂度：O(n)

改进1：

具体code的时候，关键点在于，要提前给那个等待插入的数字预留一个位置。所以如果想不增加额外的空间复杂度的话：

循环从第二位开始走，cur = lst[idx]; k = idx k标记了预留位置
进入一个while loop：每次让lst[k] 跟lst[k - 1]比，如果发现前面更小就跳出while循环
如果前面更大，就把k-1位置的数字移动到k位置，此时空出来的位置是k-1位，所以我们令 k = k - 1

时间复杂度：O(n^2) 空间复杂度：O(1)

这里的时间复杂度：需要n的时间找位置，需要n的时间来做swap： (n+n) * n个数字

改进2：

用binary search找插入的位置

时间复杂度：O(n^2) 空间复杂度：O(1)

这里的时间复杂度：需要log(n)的时间找位置，需要n的时间来做swap： (n+log(n)) * n个数字

快速排序 Quicksort

When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.
It is not a stable sort, meaning that the relative order of equal sort items is not preserved.
Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.
On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.
Quicksort is a divide and conquer algorithm.
The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm’s performance.

如何选择pivot？

Lomuto partition scheme：选择最后一个
- This scheme degrades to O(n2) when the array is already in order.
用随机数，然后跟最后一位换一下。防止一直出现最差情况

优势在于：inplace-sort 每次return都是None 因为不需要创建新空间

时间复杂度：平均/最好是O(Nlog(N)) 最差：O(N2) 但是概率超小【每次pivot都选出极值】

空间复杂度：O(log(N)) 都来自于recursion 最差情况是O(N) 【概率超小】

写代码分为三步：

主函数quickSort(self, alist, left, right)，接受array 传递出quicksort(self, array,0, len-1) 并且还可以用来return
quicksort(self, alist, left, right): 接受左右位置，从partition函数中获得pivot，递归的主函数
partition(self, alist, left, right)：用random.randint(left, right) 来随机产生pivot的位置，进行分类，然后传递pivot的正确位置

归并排序 Mergesort

排序中的王者

核心问题在于，两个长度为N的有序数列合并，复杂度的讨论:

时间复杂度O(2*N) 遍历所有元素
空间复杂度O(2*N) 新建了一个数列

归并排序的合并过程：每一次合并操作，都涉及到n个元素的合并，所以时间复杂度和空间复杂度都是O(N)。但是总共会合并log(N)次[层数]，所以时间空间复杂度都是O(Nlog(N))

归并排序的拆分过程：每个数字都被跑了一遍，产生了新的长度为N的array。总共有log(N)层

空间复杂度：O(N+log(N)) = O(N) 来自于recursion和新产生的数组

N来自于每一层产生的新数组，至于为什么不是Nlog(N) 因为每一层新产生的空间都会被回收掉，空间复杂度指的是在程序运行的时候某个时刻需要的最大空间而不是累计使用了多大的空间【因为这种情况下累积不起来】
log(N)是来自于recursion。每深入一层，就会多一个O(1) 可以理解为【找个地方来存放要运行的代码】其实是存的是地址，要知道每个递归的开始点和结束点。从哪里出来的/回到哪里

Linked-List 版本的sort没有任何的优势 老师说只是为了让我们练练写代码

Bucket Sort/ Bin Sort

Queue 队列

进队enqueue【安Q】出队dequeue【弟Q】

实际意义：排队

用链表比较好，因为如果用list的话，deque时间复杂度是O(N)

定义了一个ADT（Abstract Data Type）High-level上面带来的好处是：

Seperation of Concerns: 使用者开发者不需要互相关心
Readability and maintainability

Python有个内置的队列：deque 这个可以支持两端进两端出

求最小值

开始想只增添一个属性min 但是如果dequeue的时候把最小值删除了，就麻烦了。所以这个min可以用另外一个队列来维护。时间复杂度amortized O(1) 均摊时间

Stack 栈

入栈 push 出栈pop

实际意义：浏览器回退/编辑文档撤销/邮件列表最新出现在最上面/函数的调用本身

可以直接用list

Binary Tree二叉树

平衡二叉树Balanced：每一个节点的左右子节点深度差 <=1

完全二叉树Complete：除了最后一层，其它层都是满的。并且最后一层是从左往右排的

二叉搜索树Binary Search Tree：左子树都小于node，右子树都大于node，不考虑相等情况

递归中的BaseCase都是叶子节点的下一层：If not root: return

想逐层打印的话：建一个queue每次pop出一个并且把左右节点push进去

发现BFS可以用stack写，DFS可以用queue写

A/B Testing

Quality control in the product iteration 比如说新上线一个功能想测试

堆Heap

目的：快速找到极值

结构：Complete Binary Tree 分为min/maxheap

创建一个heap：从头元素开始不停地sift up（O(Nlog(N))）。Sift up 能保证前面一直是一个heap，sift down只能保证后面一直是heap，所以可以从最后一个开始不停的sift down(O(N))。

时间复杂度小了很多，因为最后一层原来贡献了 $\frac{N}{2}logN$ , 它们现在只贡献了0
并且实际操作的话，可以忽略最后一行，从最后一个有孩子的开始sift down.

Pop的时候先交换array的最前最后，在那个大元素下降的时候，必须要跟左右孩子中较小的那个换，如果跟那个较大的换，会导致root比孩子数值大的问题

Segment Tree

时间复杂度最多是4logN 不能cover连续的四个Node

Search

Graph Search

存储方式

正常存法：是用list分别存储顶点和连线，缺点：

一个很简单的问题都回答不了：给定两个定点A, B。是否存在一条路径连接他们呢？

Adjacency Matrix: 用一个n*n的矩阵存储边的信息，如果直接相连即为1。缺点：

如果是个Sparse矩阵的话，浪费空间
添加一个新顶点会变得很难

优点：

可以自己乘自己，获得是否存在长度为K的路径（以及几条）

Adjacency List: 用字典来存储，每个节点是一个key，每一个与该节点相邻的节点是value。优点：

我们不会为那些不存在的边浪费存储空间
查询一条边是否存在很快速
添加一条边也很简单

一些常见的问题：

给定两点，是否存在通路？
给定一点，找到所有可达点以及所有邻边
给定一幅图，遍历所有点

搜索方式

BFS遍历：Gab的例子：找眼镜，一点点摸

对于一个给定的节点，先遍历所有距离为1的节点，再遍历对所有新节点来说距离为1的节点。

Time Complexity: 对于所有节点V，我们入栈一次出栈一次，并且我们遍历一次他们的邻边。O(V+E)

可以用来找最短路径

DFS遍历：Gab举了个例子：走迷宫。

通过递归来实现，从过一个点出发，算所有能从这个点走到的点。

可以找到所有连通分量

状态：

对于有向图，有四种边的类型：Tree/Forward/Backward/Cross edge

对于无向图，有两种边的类型：Tree/Backward edge

所以在编程的时候我们要对每种情况进行分类讨论，是一个很便捷的思路。

无向图寻找环：找是否有Backward Edge。注意要记录一个父亲

Study Courses Laioffer

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Latex心得上一篇

Java心得下一篇

Laioffer笔记

介绍

课程问题

常见问题

广泛的知识

未解决问题

Linear Regression

Logistic Regression

Binary Search

Linked List

Singly Linked List

遍历Traverse

Add

Remove

Merge two sorted linked list

Find middle node in singly linked list

Doubly linked list

add

Recursion

reverse singly linked list

Non-linear Models

Confusion Matrix

ROC curve

Decision Tree

Random Forest

SVM

KNN

Feature Selection

PCA

K-means 聚类

排序算法

冒泡排序Bubble Sort

选择排序Selection Sort

插入排序 Insertion Sort

改进1：

改进2：

快速排序 Quicksort

归并排序 Mergesort

Bucket Sort/ Bin Sort

Queue 队列

求最小值

Stack 栈

Binary Tree二叉树

A/B Testing

堆Heap

Segment Tree

Search

Graph Search

存储方式

搜索方式