如何衡量程序的好与坏？浅谈时间复杂度

刷题的重点在於写出「好的」程序码

就如同前两天提到的，比起盲目地刷题更重视的是如何写出好的程序码品质。但是，程序码品质该如何定义，又该要怎麽判断自己写出来的程序码是好还是坏呢？我们在第二天 LeetCode 解题的思考策略与解题地图 中有提到「刻意优化」的重要性，对於没有开发的初学者来说，解题时很容易陷入既有的思考框架，也就是说面对相同的题目时很容易进入同一个解法泥淖。透过刷题的练习经验中，增加自己对於问题与解法的「多元观点」是相当重要的。所以除了大量刷题之外，适度的进行优化与重构绝对是这个过程里不可或缺的。除此之外，我也会建议可以参考其他人的解法，去观察同一个题目的不同切入点。

怎麽评估程序写得好不好？

「评断程序能力到什麽阶段？」最快的方式就是透过刷题来，不管是帮助开发者确认自己的能力到什麽阶段或是提供面试方作为筛选的标准。这边顺带一提，很多人在学程序的过程花太多时间在吸收但缺乏输出，当遇到一个比较大的问题时很容易就会卡关。写程序就跟国高中的数学学习是很类似的，当你背了很多公式但忽略了范例练习，面对到复杂的应用题时反而会不知道公式该如何应用。虽然现在吸收知识的方式变得更容易，也更容易误以为自己学会了的假象。根据我的经验，花多少时间吸收知识（例如看书或影片），你至少应该花一到两倍的时间进行输出与应用（例如实作或解题）。

一般来说，程序的优化可以分为「更精简的程序码」或「更快地执行速度」两个角度下去着手。资料结构就是在讨论怎样更好的使用变数的方法，实现有效在程序中储存资料与使用空间；演算法是从时间的角度进行优化，设计一些更精简、更高效的程序码与执行流程。

时间复杂度与空间复杂度

接下来，我们更近一步来量化所谓的优化，也就是到底怎样算「更精简的程序码」或「更快地执行速度」。其实好的程序码不外乎就是从储存空间与花费时间来衡量，常见的量化方式称为复杂度，可以再细分成时间复杂度（Time Complexity）与空间复杂度（Space Complexity）。

复杂度 = 程序增长的「趋势」

时间复杂度是指演算法执行时所需花费的时间，我们通常会用程序指令执行的次数来表示。换句话说，一个程序需执行越多次的程序码，就表示花费时间越多。空间复杂度用来表示所占用的记忆体空间，包含固定空间（例如：程序码、变数与常数）和变动空间（函数呼叫、动态配置或是所需的堆叠空间）。但是实务上我们不会用绝对的「执行次数」 来衡量演算法的执行效率，单纯就执行次数可能会因为不同的硬体效能或是不同的指令难度影响，用绝对的「执行次数」 容易失准。

时间复杂度会根据不同的输入大小，来定义该演算法所执行的指定执行次数（运算次数）。而我们实际上会利用等级（或称为渐近式表示）的方式来量化这个次数，也就是当程序在不同输入时执行时所花费的时间都能维持的上限值。其中一个渐近式表示算法称为 Big O ，是指当程序执行时所花费的时间成长在最差的情况的上限值。换句话说，可以想成一个算法当 n 很大时，所花时间的增长趋势为何（如下图）。

我们会将不同的 BigO 分成不同的等级，用来表示可以接受与需要改进：

面对题目的注意事项

最後一段，当我们面对一个题目的时候有三个重点需要确认：

① 题目的输入与输出范围
② 输入范围中极端的边界条件（或是特例）
③ 所可以接受的时间/空间复杂度

有些题目并不会把这三个重点写得很明确，可能需要多方推敲。所以不管你是在面试当下面对面试官的解题或平常在练习刷题时，透过「对话」厘清需求、发想解法都有助於对题目有更深的了解。

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。