博文

目前显示的是 六月, 2013的博文

分治算法的时间复杂度

这周末我把分治算法重新学了一下。假设某问题的输入是一个长度为n的数组,解决这个问题所需花的时间是T(n)假设分治算法总是把原问题分解成q个规模为n/2的子问题,划分和merge所需的时间是f(n)那么 T(n)=qT(n/2)+f(n)\(T(n)=q^2T(\frac{n}{4})+qf(\frac{n}{2})+f(n)\)于是有\( T(n) = q^kT(\frac{n}{2^k})+f(n)+qf(\frac{n}{2})+q^2f(\frac{n}{4})+...+q^{k-1}f(\frac{n}{2^{k-1}}) \)令 \( 2^k = n\) , \(r=\log_2{q}\) 则\(q^k = n^r \)则:\( T(n) = n^rT(1)+f(n)+qf(\frac{n}{2})+q^2f(\frac{n}{4})+...+q^{k-1}f(2) \)下面分析几种特例:f(n)是常数假设f(n)是常值函数,如f(n)=c。则当q大于1:\( T(n) = n^rT(1)+ c\frac{q^k-1}{q-1}=O(n^r) \)当q等于1:\( T(n) = T(1)+ c\log_2{n}=O(\lg n) \) 对应算法:二分查找、单峰数列求最大值。f(n)是一阶线性函数假设f(n)是一阶线性函数,如f(n)=cn,则当q等于1:\( T(n) = T(1)+cn+\frac{cn}{2}+\frac{cn}{4}+...+\frac{cn}{2^{k-1}}=T(1)+2cn=O(n) \)。当q等于2:\( q^{k-1}f(\frac{n}{2^{k-1}}) = 2^{k-1}\frac{cn}{2^{k-1}}=cn \)\( T(n) = nT(1)+ n\log_2{n} =O(n\lg n) \),对应算法:merge sort。当q大于2:\( T(n) = O(n^r) \) 对应算法:大整数乘积。嗯,于是类似的可推出,只要f(n)是多项式,那么原问题就是多项式时间可解的。当输入集是二维或高维时,分析工作就复杂很多。等我遇到对应的问题,再具体分析吧。先列一个:Longest Common Subsequence(LCS)问题。假设两个字符串,长度分别是m和n。它们的LCS的长度已知,求这个序列本身。那么在原来的…

UVA小结

总结一下最近在uva和spoj上做的题目。很少,反正就是挑最简单的开始做。uva上只做了3道题目。100 - The 3n + 1 problem没任何难度的入门题,完全就是适应下如何使用这个系统。按照题目所写的,反复循环即可。102 - Ecological Bin Packing穷举所有可能性即可。struct Check{ constchar* name; unsignedchar pos[9]; }; //B1 G1 C1 B2 G2 C2 B3 G3 C3 conststatic Check checks[]={ {"BCG",{1,0,0,0,0,1,0,1,0}}, {"BGC",{1,0,0,0,1,0,0,0,1}}, {"CBG",{0,0,1,1,0,0,0,1,0}}, {"CGB",{0,0,1,0,1,0,1,0,0}}, {"GBC",{0,1,0,1,0,0,0,0,1}}, {"GCB",{0,1,0,0,0,1,1,0,0}}, {NULL,{0,0,0,0,0,0,0,0,0}} }; 但是我花了0.055秒才完成。112 - Tree Summing先解析成一棵树,然后做二叉树遍历,把所有叶子都找出来,然后从叶子到根回溯一遍。写完,提交,运行时间0.089秒。然后我想,我为什么非得做二叉树遍历呢?我在解析这个二叉树的时候,需要构造Node,那么这个时候,我把所有的leaf Node都放在一个容器(vector或者list)里,到时候直接遍历这个容器不就行了?好吧,改代码,提交。运行时间0.132毫秒,更长了啊!为什么?我发现花了大量的时间在vector的push_back方法里。我并不知道最多会有多少Node,所以就不能给这个vector一次性预留足够的内存。然后我想了一下,给每个Node加了一个next指针。然后用这个ne…

2013-06-22

今天去北京Open Party贡献了一个topic,介绍Flash的RTMFP协议,这是Adobe发明的一种P2P协议,2010年才发布的,非常新,也非常复杂。我准备了一个40-50页的PPT,但遗憾的是对这个topic感兴趣的人并不多,只有12个人举手表示想听,这其中有5-6个都是专程来给我捧场的朋友。最终实际去听的只有7-8个,有一个还睡着了,鼾声微作。全程认真听完的也就3-4个,有一个坐我旁边的非常认真,在不断的做笔记。我当时选这个话题是因为,我上大学是03、04年那会儿在课堂上学的网络知识,而现在又过去了近10年。发生了很多新的变化。Google这样的公司一直在蠢蠢欲动的试图改变internet的基础部件,做一些疯狂的事情。而我们的知识一直停留在10年前,像那些上学时被我们嘲笑的老头子一样。每次在微博上看见有人对Google的GFS、Map-Reduce推崇备至我就想问:“哥!您穿越来吧?”Flash做了一件很激动人心的事情,花4年的时间,设计一套新的传输层协议,替代TCP,并成功的部署到几十亿台电脑上。假如让你重新设计TCP和internet,你会怎么做?由于RTMFP的设计和产生都比较近代,对于一个在大学里受过良好的计算机科学教育的人来说,它真是很难得的研究对象。比如,在我blog中之前提到过一个问题:在不安全的信道上传输数据,有两点很重要:加密和完整性校验。那我是先加密后计算校验值呢,还是先计算校验值再加密呢? 我通过反汇编,发现RTMFP把这两种方式都做了。它给了一个非常标准的答案: AES_CBC_ENC(seq + body) + HMAC。 通过在body前加seq,并采用CBC加密,使得相同的原文不会产生相同的密文。先加密后HMAC,从密码学上来说也是最安全的,在这一点上,它比SSH和SSL做的都好。同时,它又给出了一个不这么安全,但是又更容易实现的方案,并在交换密钥时协商具体如何加密。上面这些,都是你在RFC中看不到,从网上搜不到的。我想拿出来一起分享,讨论。学习网络协议的设计思想。但是遗憾的是,很难找到具有相同技术背景的人。今天现场问了一下,没有一个人具体了解TCP的内部工作原理,slow start 、fast open这些也讨论不起来。比如我想讨论,为什么tcp要用三次握手,再比如我把某些应用层数据放在第一个SYN包就发出去,会有什…

试用gcov

今天学了一下如何用gcov测试test suite的coverage。我最近在练习写一些算法,然后就在想如何能设计好的测试用例快速、全面的把我的算法测一遍。比如拿排序来说,找一个长度为n的数组,让它的每个元素的取值范围都在[1,n]之间,然后把所有的这样的可能性全部列出来,调用我的排序算法,再和std::sort的结果做对比。把数组长度从1到7的,符合上述要求的数组,全测一遍。够吗?对吗? 不一定啊… 比如我在写qsort的时候,只有当数组长度大于7的时候才会打开median3优化。于是,我很需要一个简单的工具告诉我,我现在的test suite的代码覆盖率是多少。那么最古典的工具就是gconv。当编译、链接C/C++代码的时候,加上--coverage ,如CC=/usr/local/bin/clang CXX=/usr/local/bin/clang++ CXXFLAGS=-g3 -nostdinc++ -I/usr/local/lib/c++/v1 -std=c++11 -stdlib=libc++ -Wall -Wextra -fsanitize=address-full -fno-omit-frame-pointer --coverage LDFLAGS=-g3 -fsanitize=address-full -fno-omit-frame-pointer --coverage LIBS=-ltbb\_debug -lc++ -L/usr/local/lib -lglog all: t .cpp.o: $(CXX) $(CXXFLAGS) -c -o $@ $\< t:test.o $(CXX) $(LDFLAGS) -o $@ $^ $(LIBS) 然后执行我的测试程序 ./t就会得到对应的gcda文件。然后调用gcov$ gcov test.cpp
File 'test.cpp'
Lines executed:93.33% of 45
test.cpp:creating 'test.cpp.gcov'....它会生成一个test.cpp.gcov文件。- : 6 : - : 7 : 26: 8: int start = 0; 26: 9: int end = a.size(); 56…