如何在时间与空间权衡

没有上过大学的话,你也可以成为一个好的程序员,但你不知道基本的计算复杂度理论的话,你不可能成为一个好的进阶程序员。你不需要知道‘O’的定义,但我个人认为你应该理解‘常量时间’,‘nlogn’,'n²'的区别。你可能可以不靠这方面的知识,凭直觉知道如何在时间和空间之间权衡,但没有这种知识,你将不会有一个和你同事交流的稳固基础。
在设计或理解算法的过程中,算法花费的时间有时候是一个以输入量为自变量的函数。当这种情况发生时,如果运行时间与输入量的对数的 n 倍成正比,我们可以说一个算法的最坏/期望/最好情况运行时间是'nlogn',这个定义和阐述的方式也可以被应用在数据结构占用的空间上。
对我来时候,计算复杂度理论是美妙的,并且与物理学一样意义深远,并且可能还有很长的路要走!
时间(处理器周期)和空间(内存)可以相互交易。工程是关于妥协的,这就是一个好的例子。它并不总是有条理的,然而,编码一些东西时更加紧凑可以节省空间,但要以解码时花费更多的处理时间为代价。你可以通过缓存节省时间,也就是,花费空间去存储某些东西的一个本地副本,但要以维持缓存的一致性为代价。你偶尔可以通过把更多信息放在一个数据结构里来节省时间。这通常只会有较小的空间占用,但可能会使算法复杂化。
提高时间空间转换经常把它们中的一个或另一个戏剧性地改变。然而,在你开始做这个工作前,你应该问你自己,你将要优化的是否是最需要优化的?研究算法是有趣的,但你不能让这遮蔽了你的双眼让你看不到这样一个冷酷的事实:优化一些不是问题的问题将不会带来任何明显的区别,但却会造成测试的负担。
现代计算机内存越来越便宜,因为不像处理器时间,你在达到边界前你不能看见它,但这种失败是灾难性的。使用内存也有隐藏的代价,比如你影响了其他需要被保留的程序,以及你分配和释放内存的时间。在你想要花更多空间去换取速度之前,请仔细考虑这一点。