allen6432
allen6432
这里探讨一下时间复杂度 如果用楼上楼上的recursive way的话，时间复杂度是O{[(5^1/2)+1]^n/2^n}. 首先可以很容易看出一个上阶，那就是O（2^n). 如果要精确这个上阶，我们要回来看一下这个递推公式f(n+1)=fn+f(n-1)； 这个递推可以用正常的配系数的方法解，比较麻烦，这里不详细介绍了； 还有一个方法是用特征方程来解，这个递推的特征根是x^2-x-1=0; 得到两个特征根，然后可以得到复杂度的表达式。 如果要说到更好的code, 我能想到的就应该就只要矩阵的那个。在recursive 前提下能达到 lgn级别。 对于
@GingerBear @dianadujing 不好意思，这几天没来逛。 我争取今晚写写怎么算时间复杂度的东西
code很棒！！！但是有个小错误：这个代码找出来的是第k小的元素
不好意思是我搞错了。没有问题！！！
这个code真心很牛掰啊！自己代码能力确实太差！我这里算了一下它的时间复杂度，确实竟然是O(n)!!!!果然迅猛！！！ 我把过程贴下来，有错误请指出！！！ [2014-01-20 00 34 10](https://f.cloud.github.com/assets/5376304/1951905/e24455ba-8194-11e3-88e2-449d7d859fd8.jpg)
 不好意思。。。刚图没有贴上
我大致算了一下，如果我们不取中间点为pivot,取任意random,其实这个的平均时间复杂度应该没有影响。不过我暂时不确定，明天算算再发上来。ps： 这个code真心简洁
@GingerBear @dianadujing 大神们，来一期关于tries的类容？有没有想法？？？
@dianadujing cc150是哪本书？
@dianadujing 你是对的！！！非常抱歉，那个入的两个值应该是[1+5^(1/2)}/2和[1-5^(1/2)}/2。 后面那个值因为绝对值比第一个小，所以它的幂方除以前面那个正直的幂方会随幂方增大而慢慢趋近于0，所以只用取前面那个正值。 火眼精金！！！给力！！！