Day 05：到底有多坏？演算法的最坏情况执行时间

讨论演算法的执行时间到现在，我们只提最糟糕的情况，好像不断在强调演算法的效能可以有多差。

你可能会想，就算用线性搜寻玩猜数字，最衰最衰要猜100次，那也会有很多不用猜到100次的情况，或甚至猜一次就中的情况耶，不用考虑那种可能性吗？

在分析演算法时，通常会讨论最坏情况的执行时间，一方面是因为比较好掌握——最坏情况的数字比较不会因为输入的内容而变动；另外一方面也等於是不对输入做任何的预设或限制。也就是即便在输入最大、最乱、最难操作的情况，执行时间最慢也不会慢於大O执行时间，大O时间即是上限。也因为不对输入有任何限制，最坏情况适合不特定主题或情境的开放讨论。

当然除了最坏情况外，还有别种分析演算法的方式，像是平均情况(average-case)的执行时间或针对特定输入的执行时间，但这些通常代表对於输入已有一些预设，例如当开发者已经很清楚某个问题会有哪些常见或典型的输入，这类的分析可能就会特别有用。

另外也有最佳情况(best-case)执行时间，用大Ω符号(big Omega notation)表达，代表演算法需要最少步骤的情况。例如像线性搜寻和二分搜寻最快都可以一次就找到，所以它们的最佳情况执行时间都是Ω(1)。