First they ignore you
then they ridicule you
then they fight you
then you win
    -- Mahatma Gandhi
Chinese => English     英文 => 中文             
随笔-219  评论-1047  文章-0  trackbacks-0
        每个问题有很多种解法,但其中存在一种最优的算法,据我观察和思考,‘懒人’是写不出那种最优算法的,为什么呢?因为最优算法有一个很明显的特点就是算法本身集结了人类的聪明才智,让我来用一个实例来证明这个观点:

问题:
请计算当参数为 n(n很大) 时, 1-2+3-4+5-6+7+......+n 的值

‘懒人’解法:
public class Lazy {
  public static void main(String[] args) {
    int n = 10000;
    int result = 0;
    for (int i = 0, flag = 1; i < n; i++) {
      result += flag * (i + 1);
      flag = -flag;
    }
    System.out.println(result);
  }
}

‘勤人’解法:
public class Diligent {
  public static void main(String[] args) {
    int n = 10000;
    int result = 0;
    if (0 == n % 2) {
      result = -n / 2;
    } else {
      result = -n / 2 + n;  //由于-n / 2会舍弃小数部分,所以无需写成-(n - 1) / 2
    }
    System.out.println(result);
  }
}

人类的智慧为计算机担负了不少的计算量,“懒人”算法的时间复杂度为O(n),而“勤人”算法的时间复杂度仅为O(1),这题的最优算法出世了!
忠告各位喜爱编程的朋友,在解决问题之前,请可怜可怜您使用的那台精疲力尽的计算机吧,花些时间思考一下,您付出的一分一秒都会有回报的 :-)
posted on 2006-10-14 18:05 山风小子 阅读(1476) 评论(10)  编辑  收藏 所属分类: Algorithm