Frank9527 (@lll_Yang) 在 新人入站,发点水货:对算法的优化和平衡的一点思考 中发帖
去年随便写的东西,拿来给佬们看个乐子
0x00.引入
相信很多人在日常的学习中就能发现,很多时候学习的新算法较旧算法不仅仅只是在某些方向有优化,而且还伴随着一些代价(比如空间代价高昂、过程信息缺失),似乎有着某种“平衡”的艺术在其中,笔者今天希望探讨的就是相关问题。
似乎因为人们的时间观念更强,亦或是储存技术的发展快于算力相关领域的进展,无论是在生产生活或是竞赛学习,大家对时间复杂度的重视普遍高于空间复杂度。
所以本篇,笔者着重来讲讲时间复杂度的优化。
本篇只考虑复杂度的优化,并不考虑常数优化。
0x01.综述
开宗明义。笔者大致将算法时间复杂度的优化分为三类,当然因为笔者的才识所限,它们会有交集,或者无法涵盖所有情况。
但大致上笔者认为这三类是没有问题的。
第一类 进行无代价的优化
第二类 以信息损失为代价的优化
第三类 以提高其他功能复杂度为代价的优化
...