帖子

目前显示的是 五月, 2014的博文

quick sort的时间复杂度的定量分析

对quick sort算法的复杂度做一下更精确的分析。quick sort是典型的分治(divide-and-conquer)算法。算法描述如下:从待排序数组中选取一个作为划分元素(pivot)用pivot把待排序数组分成两部分,使得一部分大于pivot,一部分小于pivot。对这两个子数组分别递归调用此算法示例代码:选取数组的第一个元素做pivot。template <typename Iterator> void quick_sort(Iterator begin, Iterator end) { auto len = end - begin; if (len <= 1) return; auto p = *begin; typedef decltype(p) T; Iterator iter = std::partition( begin + 1, end, [&p](const T & d)->bool { return p>=d; }); std::iter_swap(iter - 1, begin); quick_sort(begin, iter - 1); quick_sort(iter, end); } 基本上是个程序员都知道quick sort的平均时间复杂度为O(nlogn),最坏为O(n^2)。昨天我又重新看了一下Hoare在1962发的那篇关于quick sort的论文,下面对quick sort所需的比较次数做一下精确分析。quick sort的效率与划分是否平衡息息相关。假设我们选取的pivot恰好是这个数组的第k大元素, 那么由它划分而得到的两个子数组的长度分别为k-1和n-k。假设pivot是第k大的元素的概率是\(p_k\)。假设对n个元素进行quick sort所需要的平均比较次数为\(Q_n\),那么有$$ Q_n=n-1+\sum_{k=1}^n{p_k * (Q_{k-1} + Q_{n-k})} $$上式前面的n-1是指划分成两个子数组需要进行n-1次比较,后面是对不同的\(p_k\)计算数学期望。随机取pivot的quick sort继续假设pivot是从输入的数组均匀随机选取的,那么有\(p_k=1/n\)$…

用牛顿迭代法求整数的平方根

这是一个挺常见的面试题,解法也五花八门。下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数,所以只要前后两项相差小于1,就可以终止了intsqrt(int x){ if (x < 0) abort(); if (x == 0) return0; if (x == 1) return1; double t = x >> 1; t = (t + x / t) / 2; while (true) { double v = (t + x / t) / 2; if (fabs(v - t) < 1) { t = v; break; } t = v; } t=floor(t); if (t * t > x) t--; return t; } 我本来想用有理数运算来代替double,后来发现不行,迭代次数过多后,如果分子分母约分约不下去,就溢出了。上面这段代码其实也就只能应付面试,实际有很多比这个更优的方案,比如打表

一套适用用App的自动登录协议

很多App都是在启动的时候就自动给用户注册一个账号,先用着,稍后再绑定邮箱和密码。因此,我在前人的基础上设计了这样一套协议注册:客户端用不对称密钥算法(如RSA、ECDSA)生一对密钥,然后把公钥发给服务器,服务器把公钥插入到数据库中,返回一个新生成的userid登录:服务器发给客户端一个32位随机数r1客户端自己再生成一个32位随机数r2,然后把r1,r2,userid用memcpy的方式合起来,用私钥计算出一个签名s1,然后把r1,r2,userid,s1发给服务器。服务器收到答复后,先看那个随机数r1是不是刚才它发给客户端的。然后根据userid从数据库里面查出客户端的公钥,用它验证数字签名是有效的。(可选) 在完成前三步后,服务器把r2,r1用memcpy的方式合起来,用私钥计算出一个签名s2,然后把s2发给客户端。客户端收到后用服务器的公钥验证下签名,这样它就相信这个服务器不是假冒的。这要求服务器的公钥证书要实现内置在客户端中。 以上注册和登录的过程都可放在后台,不需要用户交互。不对称加密算法推荐使用ECDSA,比如ECDSA-128,因为它的公钥很短,计算很快。 但是,其实,生随机数很耗费CPU的。我在想怎样修改它让它能更好的避免DDOS攻击。

中信银行的理财产品不要买,我被骗了

我最近手上有点闲钱,想做点低风险的投资。于是就考虑了以下四种方式:货币基金 (余额宝之类),大部分都在4%-5%之间。国债逆回购(204001等),28天的最近3%-4%左右。银行的理财产品,大部分在5.2%到6%左右。P2P信贷。我只看了一下招行的,半年期5.8%到6%左右,一发售就告罄,抢不到。上面的名词看不懂没关系,看懂结论就行了:余额宝的收益率最高、流动性最高,且风险几乎最低。表面上看银行的理财产品收益率最高,比货币基金高大约1个百分点呢。1个百分点的差距,50个万的资金每3个月就相差1000块钱,够给女朋友买个包了。请先假设我有50万,并继续假设我有女朋友,不然后面没得聊了。下面主要分析银行理财产品的收益率和风险。收益率的骗局我在网上搜了一下发现中信银行有一个半年期收益率6%的理财产品,我就立马跑去了要求开户。你好,我叫王大锤,万万没想到中信银行的理财经理告诉我,他们网站标的有问题。半年期6%的理财产品实际上5.8%。因为他们有两个代码,一个是百万起售的,那个真的是6%,另一个是5万起售的,那个是5.8%,如果你仔细阅读产品说明书,能发现这个差别。他一边给我讲这个我一边瞄了一眼理财部坐着的客户,发现全是头发花白的大妈和奶奶,我有点担心我是不是来错了地方,怎么看着这么像诈骗场所。我要是真有100万,我才不买理财呢,我干嘛不直接买信托?你银行拿了我的钱不也是去买信托了,我还得给你交50-60%的手续费,我傻啊我?但是我觉得5.8%还是比余额宝什么的高,买吧。我小心翼翼的多问了一句:起息日什么时候?他告诉我,一周后。我大吃一惊!还是按50万来算,每天的利息是80块钱,7天就是560。尼玛这不是钱啊!理财经理告诉我,你可以办7天通知存款嘛。利率1%点几,可以弥补一下。事实证明他又在忽悠我,根本不可能,因为资金来回转需要时间,剩下实际不够7天,恰好不够7天!接着,我又问,有没有明天就起息的。他说有1个月和2个月的,后天起息的,你明天买也来得及。我觉得他说的对,于是我就买了。但是预期收益率只有5.4%,因为期限短。好吧,反正来都来了,卡都办了,怎么说也还是比余额宝高。于是我就买了。等我回来之后仔细阅读了下产品说明,发现,实则不然。我还是被银行骗了。我买的产品代码是B140A0104,名义收益计算天数35天,募集期5月7日到5月8日,扣款日5月9日,到期日6月13日,…

字符串匹配(1): 朴素字符串匹配的实现及复杂度分析

问题描述:在字符串t中寻找字符串p第一次出现的位置实现:C语言版本://Find the first occurrence of find in s. char *strstr(const char *t, const char *p) { char c, sc; size_t len; if ((c = *find++) != '\0') { len = strlen(p); do { do { if ((sc = *t++) == '\0') return (NULL); } while (sc != c); } while (strncmp(t, p, len) != 0); s--; } return ((char *)t); } C++版本:(下面这段代码仅仅是为了做算法分析而写的demo,不要在实际项目中使用它,因为它效率很差。)#include <string> #include <iostream> std::string::size_type find(const std::string &t, const std::string &p) { if (t.length() < p.length()) return std::string::npos; std::string::size_type end = t.length() - p.length(); for (std::string::size_type i = 0; i <= end; ++i) { bool mismatch = false; for (std::string::size_type j = 0; j != p.length(); ++j) { if (t[i + j] != p[j]) { mismatch = true; break; } } if (!mismatch) { return i; } } return std::string::npos; }…