三个经典问题

求第K小的数

一般的方法是:先对数列进行一次排序,然后找到第k小的数。假如用快排来做排序的话,时间复杂度为O(nlogn)。O(nlogn)看起来貌似效果也不错,但是否还有比它更高效的算法呢?答案是肯定的。我们先来看下第k小的数有什么特点:一个数列中第k小的数,在这个数列中一定有k-1个数比它小,[......]

Read more

求解斐波那契函数的精确解

解题思想来自《算法引论》,是一个很巧妙的解题方法,又是一个收获。

先来看下斐波那契函数:F(n)=F(n-1)+F(n-2), F(1)=1, F(2)=1
一眼看上去,仅根据这样一个递推函数,以及两个初始值,根本无从下手。合理的猜测也是一种科学方法。许多定理最初都是由猜测引出来的。印度有一[......]

Read more

求最近点对算法

关于最近点对距离计算问题是一个很金典的问题,在很多关于算法的书上都能看到。上个月我刚看完《算法引论——一种创造性方法》,里面就有关于最近点对算法的讲解。书上介绍了两种算法:
1、直接法 :也就是迭代法求出所有点对之间的距离。但这个方法只适合点对数不多的情况。假设有n个点对,用直接法,共需计算n(n[......]

Read more