今天总结一下广度优先搜索(BFS). BFS是树/图的遍历的常用算法之一, 对于没有边权重的图来说可以计算最短路径.
由于树的BFS只是图的BFS的一种特殊情况, 而 …
Here is a mindmap of the common algorithms and data structures, it can give an overview of the algorithmic terms.
I shall update its content later on. And maybe write some blog entries on some of the items.
This mindmap is drawn using xmind.
approximate retrieval(相似搜索)这个问题之前实习的时候就经常遇到: 如何快速在大量数据中如何找出相近的数据.
问题描述: 假设有N个数据, 并 …
当年装mint 17.1的时候心想我的电脑有4GB内存怎么可能不够用, 于是果断没有分一个swap分区, 呵呵...
然后就看到chrome这几年来吃内存越来越严重, 导致我开多几个标签页再开eclipse的话电脑就很有可能直接卡死... 郁闷啊 ! 于是决定给系统增加一 …
几乎所有的ml课都是从线性回归讲起, ETH的课也不例外. 不过这次老师用了贝叶斯的视角讲这个问题, 自从高中接触丁老师讲的线性回归以来 第一次听到一个 …
python科学计算包的基础是numpy, 里面的array类型经常遇到. 一开始可能把这个array和python内建的列表(list)混淆, 这里简单总结一下列表(list), 多维数组(np.ndarray)和矩阵(np.matrix)的区别.
list列表
列表属于python的三种基本集合类型之一, 其他 …
Can we do better than BST if we do not need ordered operations ?
(No compare methods, use equals method)
Idea: save items in an array.
Hash function: method for calclulating the array index of a key.
Issues:
- computing hash function
- equality tests
- collision resolution
Classic space-time tradeoff.
1. Hash Functions …
1. 1d Range Search
Goal: intersections of geometric objects.
Solution: BST
1d range search
operations required:
- insert
- search
- delete
- range search: all keys between k1 and k2
- range count: how many keys are between k1 and k2
→ find points on an interval
implementation by BST
range count
using the rank …
goal: lgN for insert/search/delete operations (not necessarily binary trees..)
3 algo: 2-3 tree, (left leaning) red-black tree, B-tree
1. 2-3 Search Trees
def. 2-3 tree
- allow 1 or 2 keys per node, & 2 or 3 children per node:
- 2-node: one key, 2 children (ordinary BST node)
- 3-node: 2 …
(BST是锻炼递归代码的好题目)
1. Binary Search Trees
def. BST
A binary tree where each node has a key:
for every node, the key is larger than all nodes in left subtree, smaller than all nodes in right subtree.
Fields: key, val, left, right
Implementation
An inner class of BST nodes:
private class …