【Day 03】如何评估演算法的效率? Big O 与时间复杂度

一、如何判断演算法的效能 ?

当同样的问题，可以用不一样的演算法来解决时，要如何判断哪个演算法比较好 ?
可以使用以下两个评量指标：

当然花的时间越少、用的记忆体越少，就是更好的演算法，而我们在讨论演算法的执行时间 ( Runtime ) 时，会使用大 O 符号 ( Big O Notation ) 来表示演算法的速度。

我们先透过一个情境，来了解不同演算法之间的执行时间，如何依不同的速率增长。

今天 Elaine 正在为 NASA 写一个搜寻演算法，会在火箭快登入月球前起动，协助计算着陆地点。
Elaine 正思考要如何从简易搜寻法跟二进位搜寻法之间做出正确的决定，这次任务的演算法要快且精准，要在 10 秒内确认着陆地点，否则火箭将偏离轨道或失事：

谨慎的 Elaine 决定用一份有 100 个元素的清单作测试，假设查一个项目耗时一毫秒：

Elaine 根据这次的测试结果，发现二进位搜寻法比简易搜寻法快 15 倍。而正式清单会有 10 亿个元素，二进位搜寻法大约耗费 30 毫秒，如此推算，简易搜寻法大约会耗费 30 x 15 也就是 450 毫秒，在 10 秒内的安全范围。

因此，Elaine 决定采用简易搜寻法作位此次任务的演算法。但这个选择正确吗 ?

简易搜寻和二进位搜寻的执行时间，并非以相同速率成长 !

用简易搜寻法搜寻 10 亿个元素，是需要花费 10 亿毫秒的 ! 当搜寻次数增加时，简易搜寻相较二进位搜寻的执行时间是大幅增加的。

Big O Notation 可以指出演算法的快慢，让我们了解执行时间随处理资料的大小所增长的幅度。举例来说：

假设清单大小为 n。使用简易搜寻法查找每个元素，必须操作 n 次，它的执行时间就是 O(n)

不是以秒数表达速度，而是比较操作步骤次数，代表的意涵是演算法的增长幅度。

而且 Big O 是建立在最坏情况的执行时间。以 O(n) 来说，代表的就是，简易搜寻法的执行时间，永远不会比 O(n) 慢。