算法等于数学吗?
1.算法概念引入
毕达哥拉斯骄傲地说:“任意给我一个直角三角形,只需告诉我两个直角边的长度,不用拿尺子量,我就知道第三边的长度了,神不神奇?”这一句看似不经意的话却惹怒了坐在旁边的这位沉思者。“毕达哥拉斯前辈,我很敬仰你的智慧,但我又不得不怀疑你是否抄袭了古中国的勾股定理,要知道,你并不是第一个人发现它的。然而我还只是个孩子的时候,大约只需要2分钟的时间就能算出1+2+3……+100了”。毕达哥拉斯正想要反驳,却被接下来的声音掩盖住了。
“给我一个支点,我将撬动整个地球。”阿基米德大喝一声。周围的一切骚动突然静了下来,显然身边的人们被他这突然的一声惊吓住了。不再沉默中死亡就在沉默中爆发,显然阿基米德选择了后者。他额头上暴起的一道道青筋也终于慢慢平静了下来,身边的人们似乎一致认为,这个长满胡子的老头如果不爆发就要开始发疯了。
爆发过后就是寂静,寂静……这时一个身穿褴褛的年轻人终于站了起来,想要打破这个尴尬局面,他淡定而又平静地说道:“一个方程如果没有神的旨意,则对我来说全是无意义的。”所有人的目光又都转移到了这个其貌不扬的印度人身上,这句平静的话中,每个字却无不渗透着坚定的力量,仿佛只有在此时此景,人们才能深刻的感受到宗教信仰的强大,这强大的力量是忠诚的信徒毫无保留地把自己的一切奉献给了上帝,然后就是绝对的虔诚。
屋中弥漫的雪茄烟雾似乎也停止了扩散。然而这位印度人的原本打破尴尬局面的目的却并没有达到,相反,令他万万没想到,他的一句随口而出的话,却让这个一度失控的场面变得雪上加霜,因为更多的学者都开始探讨自己心中上帝的模样了,甚至部分人认为,数学是上帝的语言,而人类只不过是通过数学的桥梁,来理解上帝的旨意罢了……场面由寂静也逐渐变得骚动起来。
主持人高德纳连忙站起,说道:“拉马努金先生,各位,今天我们跨过时间之线,有幸聚集在这里开一个讨论会,主要的目的有三个:一是为了解决如何能更好的给算法下定义,将算法与数学在学术上的界限加以区分。二是讨论算法的真正意义所在,将算法的神秘之处公之于众。三是在其意义的基础上提出对算法开展研究的方法,而不是让想进入算法之门的人望而止步。当然再次感谢简书网对本次讨论会的独家赞助。广大简友如果对算法感兴趣,可以在评论区提出个人的独特见解。最后让我们一起见证算法诞生这一伟大的历史时刻吧!”
2.什么才是算法?
算法就是为了解决一个问题而采取的方法和步骤。
An algorithm is a series of mathematical steps, especially in a computer program, which will give you the answer to a particular kind of problem or question.
而这个方法和步骤从大的方面可以是软件的开发,从小的方面又可以是一个函数的独特设计。如果说程序是一个人的话,那算法就是这个人的灵魂了。我当时学习网站开发时,就把HTML看作成一个人的骨架,CSS看作成这个人的外貌长相,而JS则看成是这个人的能力。这也很好的自我安慰在计算机界能力大于外貌(//∇//)
如果把数据比喻为一个个人的话,则数据结构就是这个人的骨架,而程序语言是这个人的肉体,算法则是这个人的灵魂。
很明显,我们每个人的骨架都是大体相当的,有头、身体和四肢。而每个人的长相外貌则是不尽相同的,为什么?只是我们在用肉身填充我们骨架上时,有的填多了,有的却填少了。于是,有胖也有瘦,有高也有低,该凸的没有凸起,就显得不美观了。那么对于程序,每个人用的程序语言不一样,可以是C、C++、Java、Python等等,只是说肉身不一样了,各个语言有各个语言的美,但它们都有一个共同特点:相似的骨架。
又有人会问了,为什么我写程序没有感觉用到数据结构呢?我想说,你听别人说话时,你感觉到了你是在用耳朵在听吗?当然你是无意识的。那什么时候能感觉到,只有当声音很微弱时你才真正能感觉到。相对于程序语言,为什么你感觉不到数据结构,不是没有,只是这个语言在被设计出来时,它就已经被内嵌到这个语言骨架里了,因为这个程序语言就是照着这个骨架设计的。当这个程序语言被设计出来之时,它的骨架也就成为了肉身的一部分。就比如说一个婴儿在出生之时他的肉身就已经在妈妈的胚胎里完美的结合到了骨架上。程序语言中一个很好的例子就是C++或Java语言里的String类型,因为你认为它是字符串类型,你可以想当然的定义一个变量,其实这个类型就是它的骨架,只不过这个String也成为了程序语言的一部分(声明变量),然后像下列这样:
String s = "LostArt";
说了这么多,终于说到算法了。还用人比喻,一个人如果没有灵魂会怎么样?当然是死人了。那程序没有算法,又会出现什么情况呢?不言而喻,没有算法的程序只是一堆散乱的指令,不知道要干什么,如同一个行尸走肉。
例如下面这段简单的求和函数,你可能会这样写:
void Sum(int n) {
int i, sum = 0;
for(i=1; i<=n; i++) {
sum = sum + i;
}
}
然而,有人却这样写了出来:
void Sum(int n) {
int sum = n*(n+1) / 2;
}
看了这个函数或方法,有人疑惑,算法不就是数学嘛!那为什么不把“算法”直接叫“数学”呢?为什么又非要另外起一个名字呢?可能用地球人都知道的算法想必看完不过瘾,那再来上一个有意思的。
求任意两个正整数的最大公约数(公因数)LCD(Largest Common Division)
小学的时候都做过的题,用算法怎么实现呢?
假设,m=8251, n=6105
短除法
int LCD_ShortDiv(int m, int n) {
int i, time;
int f = 1; //相同因子的乘积
for(time=0; time<100000000; time++) { //做100000000次运算
for(i=2; i<=m&&i<=n; ) {
while(m%i==0&&n%i==0) {
f *= i; //将该因子与 前面的因子相乘
m /= i;
n /= i;
}
i++;
}
}
return f;
}
然而你还真的停留在了小学水平,看看下面的:
辗转相除法(欧几里得算法)
int LCD_EucAlgorithm(int m, int n) {
int i, f, time;
for(time=0; time<100000000; time++) { //做100000000次运算
i = m % n; //取余数
while(i) {
m = n; //将小的n替换成m
n = i; //将余数i替换成n
i = m % n; //再次取余,直到i=0
}
}
return n; //把最后除数返回
}
两个算法做一次运算,效果并不明显,那我们让它们分别做一亿次运算试试,Oh,my god!电脑不是很给力啊!稍等会……
跑分成绩终于出来了:
LCD_ShortDiv用的时间为:72.804s
最大公约数为:37
LCD_EucAlgorithm用的时间为:0.438s
最大公约数为:37
相差倍数:166
是不是不相信,但事实就是现实。有些人对数字几乎没有概念。我举个励子,你一天赚了10快钱,结果还有人一天赚了1660块,什么概念,贫富差距太TM悬殊了。
回到开头,算法是解决问题的方法和步骤,换句话说,必须满足了方法和步骤的特性才能被叫做算法。那这些特性是什么,我相信大家刚接触程序语言时就已经知道了,有穷性、确定性、输入性、输出性、可行性。
1.有穷性:在执行有限的步骤之后,算法必须能够终止。
2.确定性:算法的每一个步骤都具有确定的含义,不会出现二义性。
3.输入性:在算法中可以有零个或者多个输入。
4.输出性:在算法中至少有一个或者多个输出。
5.可行性:算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成。
也就是说,不满足这五条特性,是不能被叫做是算法的。数学公式显然不是,只有把数学公式转换成满足这五条特性的步骤(指令)后,才能称作是算法。那我们怎样才能写出一个好的算法呢?看下面第四条,该如何学习算法?
3.算法的意义是什么?
既然把算法和数学区分开来了,那么算法的真正用武之地是什么呢?将数学知识变现成生产力是对算法最高的奖赏在不为过了。我们知道有很多数学知识,但应用到社会成产中的却是冰山一角了。
-
提高时间效率,加快问题解决的速度
-
降低数据在存储器上空间的占用
4.该如何学习算法?
步骤如下:
1.学习相关数学知识
《线性代数》《概率论与统计》《离散数学》《算法设计与分析》《算法导论》《组合数学》《具体数学》等等
2.将数学知识与算法相联系
(1) 竞赛:参加一些竞赛,例如ACM等等
(2) 书:《数学建模算法与应用》
3.用工具表示算法
自然语言
流程图
伪代码
程序语言[Python, Matlab等]
4.时刻想着4条评定标准
(1) 正确性:算法应当能够正确地解决求解问题。
(2) 可读性:算法应当具有良好的可读性,以助于人们理解。
(3) 健壮性:当输入非法数据时,算法也能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。
(4) 效率与低存储量需求:效率是指算法执行的时间,存储量需求是指算法执行过程中所需要的最大存储空间,这两者都与问题的规模有关。
注:第一次用文学的手法与理工博客技术贴相结合,将技术贴从知识点的奴隶中解放出来,意在快乐学习,增加兴趣,启发思考,记录灵感。