如今的咱们对算法可谓并不陌生，由于互联网发展迅猛，哪怕没有体系学习过核算机底层理论的程序员，也接触过无数的算法。
昨日笔者看到一个开放性考虑题，内容是这样的：
假如一个程序只运转一次，在编写它的时分，你是选用最直观但是效率较低的算法，仍是仍然寻觅复杂度最优的算法？
可能你心中已有答案，但这个问题咱们放到文末再聊，本篇首要是科普向的算法入门文章，我将从开端的核算机讲起，用通俗易懂的话来带你重新认识下算法。
前言
图灵提出了核算机的数学模型、冯诺依曼确认了核算机通用的体系结构，而假如要问图灵和冯诺依曼之后对核算机科学奉献最大的人是谁，那就不得不说到高德纳了，正是他奠定了核算机算法的根底。咱们知道，没有操控程序，只要一系列硬件算不上是核算机，程序之于核算机是必不可少的，而程序的灵魂，就在于算法。
核算机诞生之初
在前期核算机范畴里，哪些操控功用要经过开关电路做成硬件，哪些又该由程序操控，这些鸿沟其实不像如今这么明晰。
教科书上对世界第一台通用核算机的界说，是20世纪40年代所研发的电子核算机埃尼阿克（ENIAC），而事实上这台核算机在研发时也没有搞清楚程序是怎样一回事，它说究竟仍是一台专用核算机，首要用于处理远距离导弹发射过程的核算问题。是的，核算机的起源并没有想象中的美好。
其时的冯诺依曼正服务于美国军方，担任氢弹工程，也需要进行大量的核算，听说了电子核算机研发的事情，就跑过去想看看能不能处理氢弹核算问题，而他也马上发现了这台核算机的巨大缺点：假如 ENIAC 要核算其他问题，只能修改线路，但改线路会非常费事，处理一个几分钟就能算好的问题，要几个月的时刻来改线路，效率之低下可想而知。但面对现已造了一半的 ENIAC，冯诺依曼也只能表示无解。
美国军方在了解了这个状况后，于1944年决议再造一台新的通用核算机，这次由冯诺依曼和约翰莫奇利、埃克特（两位 ENIAC 的研发者）一同主导规划，称为 EDVAC (离散变量主动电子核算机)，所以它其实才是世界上第一台由程序操控的通用电子核算机，乃至可以说是今日一切核算机的原型，而 ENIAC 则是一个孤版。
1946年 ENIAC 诞生后，科学家们用它进行了一次核算长程火炮弹道轨道演示，以至于现场观摩的蒙巴顿元帅看的目瞪口呆，说了一句“真快啊，简直是带电的大脑”，“电脑”一词便是这么来的。
算法理论起源
在 EDVAC 之后，客观上核算机现已分为了软硬件两个部分，随后的十多年里，整个职业注重的都是硬件，从电子管、晶体管、再到第三代继承电路，核算机硬件在不断演化，但前期的软件算法却很简单，由于大多数用来进行科学核算，许多程序在编写完结之后其实用不了几回，因而没有人注重它们的质量。
而到了60年代，核算机开端在商业上普及，一个程序是需要提供给用户重复运用的，这时分人们才真实注重起程序规划，而核算机算法理论的缺失，就要有人来弥补了，这个人便是文章最初说到的高德纳。
关于高德纳这个中文名的由来，大部分的英文名咱们一般都会以音译方式来取，但高德纳这个姓名与其英文名 Donald Ervin Knuth（唐纳德尔文克努斯）仍是有必定不同的，在1977年时，高德纳作为最早遭到我国邀请讲学的专家来华访问，临行前他就想给自己起一个中文名，其时姚期智（图灵奖获得者）的夫人储枫便给他起了这个姓名。
高德纳在学生年代对物理和音乐都很有兴趣，1956年，他以各科均匀97.5分的创记载高分从中学毕业，彼时的他选择了攻读物理专业。
在大学时期，他接触到其时最先进的大型电脑 IBM 650，并展现出了在核算机上超凡的才干。其时他写了个程序，用来剖析大学篮球联赛中球员在每场竞赛的得分、助攻、抢断、篮板球、盖帽等数据，然后让篮球队教练以此选择球员，终究带领球队赢得了其时全美大学生篮球联赛冠军（这可能是最早的大数据在体育界的成功应用了）。后来高德纳也成为其时最好的工程科学期刊编辑，获得了国家奖，所以便从主修物理改成主修数学，毕业之后留在加州理工学院任教，并在数学与核算机程序规划范畴取得多项成就。
而说起高德纳对核算机职业最伟大的奉献，就不得不说到他编纂的一部体系地介绍核算机程序规划的巨作《核算机程序规划艺术》，到 2018 年 12 月，该书现已出版了 4 卷，高德纳自己估计第 5 卷将会在 2025 年完稿。其间第一卷是《根底算法》，比尔盖茨曾花了很大精力学通了这一卷，此后便一辈子都在向人推荐这套书，他直言假如没读过这卷《根底算法》，就很难成为一个优秀的程序员。高德纳自己的说辞更狠：“要是这一卷都看不懂，那就别当程序员了”。（对不起，是我不配了）
高德纳在写书的时分，苦于没有好的编辑排版软件，干脆就自己写了个软件，这便是闻名的 Tex，此后便成为了迄今为止大多数科技书籍运用的排版程序。
高德纳曾出资在全世界悬赏能在 Tex 程序中找到 bug 的人，金额从 2.56 美元开端（高德纳说这是”十六进制的1美元”），随之指数式增加（即2.56、5.12、10.24、20.48…..）他开到第三张支票今后，就再也没有人找出过错了，事实上假如软件的过错超过 18 个，高德纳可能就要破产了，他敢冒着破产的风险提出这个悬赏，说明对自己的代码质量有极高的自信。
核算数量级的影响
人们其实本能地对大数没什么概念，比方曾经有一条新闻是这样的：“美国未来 5 年内将投入 20 亿美元开发下一代人工智能”，其实就美国的经济体量来说，20 亿美元底子不算什么，但是这样的音讯为什么会变成一条“震动”的新闻呢，便是由于大家底子数不清这些数究竟有多大，仅仅凭直觉就应该是无穷大的钱。
同样地，人们对核算机的高速也是无感的。比方我说一个页面资源的加载速度本来是 100ms，现在下降到了 1ms，足足快了一百倍。但是绝大多数人的感觉应该是：这两者都足够快了。对咱们来说其实都是一眨眼的功夫，没不同的。
在今日，咱们要衡量算法的好与坏，就必须先明确算法的衡量规范以及测验的方法，一般咱们会想到速度要快，占用空间要小，这两个方向都是对的，关键在于用不同数量级测验的时分，不同算法表现可能会完全不一样。比方以下两个场景：
- 运用 1W 条数据测验时，算法A 运转 1ms，算法B 运转 10ms
- 运用 100W 条数据测验时，算法A 运转 10000ms，算法B 运转 6500ms
假如单从场景 1 来判别，那么显然 算法A 更好，而但从场景 2 来看的话，却是 算法B 更优，那么问题来了，究竟哪个算法才是“好算法”呢？
算法复杂度
在核算机科学发展初期，科学家们对算法的评判观念并不统一，直到1965年尤里斯和查理德首次向世人提出了算法复杂度的概念（二人后来因而获得图灵奖），算法的规范此后才开端统一。而最早将算法复杂度严厉度量化的人，便是高德纳，他也因而被誉为“算法剖析之父”。今日，全世界的核算机范畴都以高德纳的思想为规范。
高德纳的思想首要包括以下原则：
1. 在比较算法快慢时，只考虑数据量特别大，大到无穷大的状况。
为什么要比大数？而忽略掉小数呢？由于核算机的发明便是为了处理大数，那些数据量大到人为无法核算的工作，才是交给核算做的。比方一个商城体系在上线初期往往运转流畅，但是用久了查询就变得很慢，原因便是订单数等等记载一直在日积月累，数据量只会越来越大，处理的数据只会越来越多，而一个体系假如在初期没有考虑到这些，后期就会有处理不完的bug。
2. 决议算法快慢的要素只分为两类：不随数据量变化的要素、随数据量变化的要素。
比方说有两种算法，第一种运算次数是
N 是处理的数据量；第二种则是
N 的巨细没有直接相关，而当 N 非常大的时分，
咱们可以把一种算法的核算量或占用空间巨细写成 N 的一个函数 f(N)，函数的鸿沟可以用数学上的大O概念来约束，假如两个函数设 f(N) 和 g(N)，在N趋近于无穷大的时分比值只差一个常数，那么他们就被看成同一数量级的函数，即 O(f(N)) = O(g(N))，也便是以为具有相同的复杂度。
3. 不同算法在复杂度上差异哪怕只要一点，执行效率也有天壤之别。
比方选择排序的均匀时刻复杂度是 O(n^2)，而快速排序的均匀时刻复杂度是 O(nlogn)，两者在对10亿数据进行排序的时分核算量分别是大约100亿次和大约30亿次。
总而言之，复杂度、数量级、大O概念，理解了这些那么你对算法也就有了必定的了解。
结尾考虑
那么回到最初这个问题：
假如一个程序只运转一次，在编写它的时分，你是选用最直观但是效率较低的算法，仍是仍然寻觅复杂度最优的算法？
首先我以为这道题其实没有一个规范答案，由于大多数人都懂得辩证法，会说具体问题要具体剖析，我也时常是如此，这种思想当然并没有错。仅仅当我回忆这些在核算机范畴的大师们的事迹时，会发现一些特点：冯诺依曼原本只想算题，却发明晰核算机体系结构；高德纳只想写书，却发明晰流行至今的排版软件。为什么大师们偶然为之的事情却常常是别人穷极终身也无法完结的事呢？
其实咱们不难发现，除了个人能力的差异外，他们还有着遇到问题时处理问题的活跃情绪，同时他们身上也有一种爱折腾的精力。高德纳叙述他在学习编程时，由于核算机太慢，内存太小，来回编译和改错太花时刻，所以他总是不断优化算法，力争一次运转没有过错。正因如此，高德纳在硅谷参加编程竞赛与很多顶级大咖同台竞技时，也总是用一台最慢的核算机获得第一名。
核算机是认死理的，但程序员并不是。假如一个程序只运转一次，是选用直观但低效的算法，仍是寻觅复杂度最优解的算法，其实代表的是两种对待问题的情绪，何况谁又能确保一个程序真的只会运转一次呢？而对待问题的情绪假如是活跃的，即便程序只会运转一次，咱们也可以测验去寻觅最优解。人的终身会遇到无数的问题，对待问题的情绪往往决议了个人的命运。即便你没有超凡的才干，不求闻名于世，你所做的每一个活跃的决策，或许都会对你的未来发生深远的影响。
在当今职场反内卷的浪潮中，咱们常常会用“躺平”“摆烂”来作为纾解和释放的情绪表达，其实真实内卷的人，往往是那些自以为非常尽力却尽力错了方向的人，作为程序员的咱们应该坚持独立的考虑，警惕堕入无用尽力傍边，同时也要坚持真实地活跃的情绪。纵观核算机的发展史，只要活跃的情绪与探索求知的精力才干不断拓荒新的路途，与诸君共勉。
本文部分观念与比如参阅自吴军老师编撰的《核算之魂》
往期文章推荐
原生JS手写一个高雅的图片预览功用，带你吃透背后原理
原生拖拽太拉跨了，纯JS自己手写一个拖拽作用，纵享丝滑
如何高雅地编写一个高逼格的JS插件惊艳你的领导和搭档？
Vue3+Node写个免费在线图库生成器，三步将你的手机相册搬到线上
