我们为什么要学习数据结构和算法?(一)

首先做一个小小的假设

我们假设有一台运行速度足够快,内存足够大的电脑(突破普朗克常量物理极限,达到数学层面的无限),快到可以瞬间做完任何任务,大到可以塞下任何程序栈,那么我们从此似乎不再需要继续钻研数据结构和算法了,暴力求解,暴力递归就是一切,显然,这样的电脑是不存在的。

举这个例子就是想说明:数据结构和算法问题必须放在具体时空条件下,具体情况具体分析,所以我们爱用优化这个词,我们倾向于用更少的空间,更少的时间,做更多的计算,理论上软件优化是有极限的,因为总要给磁盘,内存,cpu 物理工作的时间。

我们碰到的问题无非是在受限的时空条件下,完成目标的计算任务,或是基于源程序做定向优化。

那么总得有个标准吧

定标准看起来是一件比较容易的事:

时间嘛,看程序运行多少毫秒就完事了,快就是好。

空间嘛,看占了多少 bit,少就是好。

似乎很有道理,仔细琢磨一下有这样一个问题:

程序 A 在数据量比较小的情况下时空消耗都还好,感觉数据量增大了也不多,消耗却像细胞分裂一样吃掉了远远高于预期的资源,慢慢尝试后我们会发现,隐隐约约消耗与数据量有着函数关系式的对应,或是线性,或是呈指数。

于是为了抛弃上面那种粗略量化的糟粕,我们有了更精确的定性定量的工具。

引入一个数学工具来帮助我们

离散数学讨论了这样一个问题:y = xy = x ^ 2,当 x 越来越大时,谁增长的更快呢?

显然是 x ^ 2,那么当我们研究一个 y = 2x + 3x ^ 2,这样的问题时,是不是可以忽略 2x 这项的消耗呢?

举个简单的例子,小胖和小美一起吃饭,当两人吃的时间足够长,东西足够多的时候,我们是不是可以断言,伙食费里面的绝大部分都是小胖吃的?

所以一个很聪明的办法是在更大的损耗面前,忽略那些不这么重要的消耗。

而算法导论等著作中,关于时空消耗有着非常清晰且规整的介绍,下篇聊聊!

本作品采用《CC 协议》,转载必须注明作者和本文链接
一只热爱编程的松鼠
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!