2019/03/20 03:22

[Algorithm] Reservoir Sampling

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability. To solve the problem which n size is unknown, Reservior Sampling is a perfect algorithm to use: Reservoir sampling algorithm can be used for randomly choosing a sample from a stream of n items, where n is unknow. Here we still need to prove that Consider the (i)th item, with ...

0
0

2019/03/10 08:50

0
0

2013/12/05 13:45

Boyer-Moore algorithm

Main features performs the comparisons from right to left; preprocessing phase in O(m+) time and space complexity; searching phase in O(mn) time complexity; 3n text character comparisons in the worst case when searching for a non periodic pattern; O(n / m) best performance. Description The Boyer-Moore algorithm is considered as the most efficient string-matching algorithm in usual applications....

0
0

2014/01/06 17:54

Greedy Algorithm 实例

Algorithm Design Techniques - 1 ====================== ##Greedy Algorithm## > note： > > It works only if local optimum is equal to global optimum ###1. Approximate Bin Packing### ####The Knapsack problem#### > 问题大意：给定n种物品和一个背包，背包容量为Sum，对于每一个物品i，它的重量为W(i)， 价值为p(i)。 要怎样才能使背包装的物品的价值最高。 Example : n = 3, M = 20, (p1, p2, p3) = (25, 24, ...

0
1

2016/11/07 13:03

Point-In-Polygon Algorithm

Figure 1 Figure 1 demonstrates a typical case of a severely concave polygon with 14 sides. The red dot is a point which needs to be tested, to determine if it lies inside the polygon. The solution is to compare each side of the polygon to the Y (vertical) coordinate of the test point, and compile a list of nodes, where each node is a point where one side crosses the Y threshold of the test poin...

0
0

2018/01/12 16:53

[Graph]Doubling Algorithm

Doubling Algorithm——倍增算法 是一种可以优化时间复杂度的神奇的算法，可以用它来求LCA等等。 基本思想： deep[i] 表示 i节点的深度, fa[i,j]表示 i 的 2^j (即2的j次方) 倍祖先，那么fa[i , 0]即为节点i 的父亲， 然后就有一个递推式子：fa[i,j]= fa [ fa [i,j-1] , j-1] 。 那么怎么求LCA呢，我们需先把深度更深的节点往上提直到深度和另一个节点一样，然后我们每次调2^i个节点（从最大可以 跳的步数开始跳，若相反可能会导...

0
0

2018/07/11 15:52

0
0

2013/11/22 20:41

Apriori Algorithm 笔记

Apriori Algorithm(Apriori 算法) 是无监督学习, 它能够在合理的时间范围内找到频繁项集, 它基于 Apriori 原理, 从单元素项集开始, 通过组合满足最小支持度要求的项集来形成更大的集合. 优点 易编码实现 缺点 在大数据集上可能较慢 适用数据类型 数值型, 标称型 基础概念 1. 关联分析(association analysis) 从大规模数据集中寻找物品间的隐含关系, 这些关系可以有两种形式: 频繁项集和关联规则. 首先要找到频繁项集, 然后才能获...

0
3

2018/04/15 20:45

0
0

2019/08/24 19:46

algorithm下的常用函数

algorithm下的常用函数 max(),min(),abs() max(x,y)返回x和y中最小的数字 min(x,y)返回x和y中最大的数字 abs(x)返回x的绝对值，注意x应当是整数，如果是浮点数应当使用math头文件下的fabs函数 swap() swap(x,y)交换x和y的值 reverse() reverse(it,it2)可以将数组指针在[it,it2)之间的元素或者容器的迭代器在[it,it2)范围内进行元素反转。 对于数组中的元素 # include <iostream> # include <algorithm> using namespace std; in...

0
0

2012/12/04 22:32

simple sorting algorithm

# simple sorting algorithm def bubble_sort(sort_list):     ''' (list) -> None     Sort sort_list.     '''     iter_len = len(sort_list)     flag = True     # i is from 0 to iter_len - 2     for i in range(iter_len - 1):         if flag:             flag = False             for j in range(iter_len - 2, ...

0
0

2013/05/05 20:55

Boyer-Moore algorithm

Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。 下面，我根据Moore教授自己的例子来解释这种算法。 1. 假定字符串为”HERE IS A SIMPLE EXAMPLE”，搜索词为”EXAMPLE”。 2. 首先，”字符串”与”搜索词”头部对齐，从尾部开始比较。 这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符肯定不是要...

0
3

2013/06/06 09:25

Nagle's algorithm

Nagle算法是以他的发明人John Nagle的名字命名的，它用于自动连接许多的小缓冲器消息；这一过程（称为nagling）通过减少必须发送包的个数来增加网络软件系统的效率。Nagle算法于1984年定义为福特航空和通信公司IP/TCP拥塞控制方法，这是福特经营的最早的专用TCP/IP 网络减少拥塞控制，从那以后这一方法得到了广泛应用。Nagle的文档里定义了处理他所谓的小包问题的方法，这种问题指的是应用程序一次产生一字节数据， 这样会导致网...

0
1

2016/06/12 18:29

0
1

2012/04/03 14:04

Buddy System Algorithm

To avoid external fragmentation, Linux adopts the approach of keeping track of all free page frames. To achieve this goal, the Kernel uses Buddy System Algorithms. Key data structure and source code area in Kernel struct zone { struct free_area[11]; } struct free_area { struct list_headfree_list[MIGRATE_TYPES]; unsigned longnr_free; }; #define MIGRATE_UNMOVABLE 0 #define MIGRATE_RECLAIMABLE 1 #...

0
0