经典高斯算法,一起学习数据结构和算法吧!

原创
2015/03/05 11:52
阅读数 476

        对于想提高编程技巧的人,数据结构和算法是必修的,举一个最经典的故事向新手们说明算法的伟大。

话说很久很久以前。。。,一次数学课上,老师让同学们做一个算术:一个小时内算出1+2+3.......+99+100的结果有一位同学,叫做高斯,只用了不到20分钟就算出了结果,老师很惊讶,于是向他请教他是怎么算的。原来,他发现了这些数字有一个规律:第一个数字加上最后一个数字等于101,第二个数字加上倒数第2个数字结果也是101,即:1+100=101,2+99=101,3+98=101......。以此类推,一共就得出50个101,那这个算术题的结果自然就是50*101=5050。

根据规律得出一个公式:n(n+1)/2

就是从1一直加到n的结果

按照传统方法,我们就是傻呼呼地去计算1+2=3,3+3=6,6+4=10......=5050,接下来我们用程序来表示出传统方法与高斯算法的差别

var count,max int
//要加到100
max = 100


//传统方法
count = 0
for i:=1;i<=max;i++ {
    count = count + i
}
fmt.Print(count)

//============= 我是不羁的分隔线 ================

//高斯算法
count = max(max+1)/2
fmt.Print(count)

不难看出,传统方法计算,计算机要做100次循环,而高斯算法只需要一次计算!想像一下如果max=100000000呢?传统的方法就要循环100000000次计算操作,而高斯算法依然只需要一次计算!这就是一个天才算法的差距。

而通过学习数据结构,就会知道两种算法的复杂度为O(n)和O(1)。更深入的东西就需要大家一起去学习了,我也没那个水平,只是抛砖引玉,给未入门的新手讲些粗浅的东西。


展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部