Day 12, Coursera-Algorithm toolbox- Big O 时间複杂度

Big O 时间複杂度

一个用来思考，这个演算法能否快狠準计算完成的好工具，有别于刚开始学程式的人，先能做出程式来用，就能欢天喜地，开心好几天，知晓Big O之后，世界就不再那么单纯了，而那纯粹的快乐也渐渐离我们远去... ...，就好像离开童年的单纯岁月一样，你，如果可以，还会想要回到小时候吗? 当然，不要。大人有选择生活的能力，小孩才没有。
时间複杂度是个粗估运作时间的好方法，为甚么说粗估呢?

举个例子，如果你有一个公式:

100n^3+2n+2
我们会说，该公式的时间複杂度是O(n^3)

如果是

99999999999n+1
我们会说，该公式的时间複杂度是O(n)
藉由时间複杂度，我们能忽略电脑计算性能、记忆体配置大小等问题，就纯粹从演算法公式来估算、比较花费时间，当输入数字变的庞大时，在同单位时间数下，时间複杂度显现的影响就更加震撼。

图片来源自维基百科
举我从Day9~Day10之间的公式，两者都是找出最大相乘数，然而一个会造成time limit exceed，一个却依然能快速算出正确数值，这就归功于从时间複杂度角度的思考，若使用双迴圈，会造成时间複杂度为O(n^2)，若只使用单迴圈，就是O(n)。很明显的，O(n)所花费的时间较少，我们就谈到这。