发表了博客
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

Bluestein's Algorithm

网上很少有人提到,写的也很简单,事实上就是很简单... $Bluestein's\ Algorithm$,用以解决任意长度$DFT$。 考虑$DFT$的形式:$$\begin{aligned}y_k&=\sum_{i=0}^{n-1}a_i\omega_n^{ki}\&=\sum_{i=0}^{n-1}a_i\omega_{2n}^{k^2+i^2-(k-i)^2}\&=\omega_{2n}^{k^2}\sum_{i=0}^{n-1}a_i\omega_{2n}^{i^2}\omega_{2n}^{-(k-i)^2}\end{aligned}$$ 注意到$\sum$是个卷积,可以用$FFT/NTT$计算。所以$Bluestein$的复杂度是$O(n\log n)...

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

AdaGrad Algorithm and RMSProp

AdaGrad全称是Adaptive Gradient Algorithm,是标准Gradient Descent的又一个派生算法。标准Gradient Descent的更新公式为: 其中Learning Rate α对于Cost Function的各个feature都一样,但同一个α几乎不可能在各个feature上都表现完美,通常为了收敛,会选择较小的α。 而AdaGrad的主要思想是:在各个维度上使用不同的learning rate,从而加快函数收敛的速度。其公式为: gt是t时刻目标函数的梯度,可以看到,依旧为各个fea...

0
0
发表了博客
2013/11/22 20:41

Apriori Algorithm 笔记

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

0
3
发表了博客
2018/04/15 20:45

[模拟]Assignment Algorithm

题目描述 A low-budget airline is designing a sophisticated algorithm that will assign more desirable seats to passengers who buy tickets earlier. Their airplane has r rows of seats, where r is an even integer. There are also 3 exit rows in the airplane; those rows do not contain any seats but only provide access to the emergency exits. One exit row is in the very front of the airplane (before t...

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

Algorithm: 移动盒子

题目意思是说,给出一个数n,表示存在一个整数序列1……n,然后进行四种操作: 操作一:输入x,y,表示将x移到y的左边(若x本来就在y的左边则忽略); 操作二:输入x,y,表示将x移到y的右边(若x本来就在y的右边则忽略); 操作三:输入x,y,表示交换x和y。 操作四:将整个序列倒置。 最后要求的是操作后的整个序列奇数项的和。 数据为100000,直接模拟肯定超时,用STL的链表也会超,我的想法是用数组模拟链表,left[i]和rig...

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
没有更多内容
加载失败,请刷新页面
点击加载更多
加载中
下一页