Big O Notation: A Few Examples


通过在算法中执行的基本操作(基本操作=一个花费固定时间执行的操作)的数目统计来测量时间复杂度。

时间复杂度由函数T(n)表示。O代表函数,(n)表示作用于元件的数目。

渐进时间复杂度,对于任何的有效输入它可能花费的最长时间,是表达时间复杂度最常见的方式。

当你讨论大0符号,通常指的是最坏的情况。

例如,如果我们有两个列表搜索常见条目,我们将计算条目在每个列表花费的最长时间,我们不低估可能需要多长时间是为了安全起见。

O(1)——确定一个数字是奇数或偶数。O(1)是一个静态的时间常量,不管有多少信息或有多少用户它都是一样的不改变。

O(log N)——发现一个字在字典里(使用二分法检索)。二分法检索是一个典型的“分而治之”的算法。

O(N)——看一本书

O(N log N)——排序一副扑克牌(使用归并排序)

O(N ^ 2)——在你购物车上检查你的购物清单的每一样东西

O(∞)-掷硬币,直到它落在头上

作为一个经验法则,任何用N ^ 2或其他指数对于多个用户的网站来说都不是好的算法。

如果你的算法降低在输入上降低指数,你应该找一个更有效的方法来解决这个问题。

当你编码循环内循环,你要特别注意时间复杂度。

大O备忘单是当你分类算法时的一个查看平台,像“合并排序”或“快速排序”。

bigocheatsheet.com/

普林斯顿Coursera课程不是一颗卑微的心。通过在java的例子和实践中,这门课程将涵盖java的迭代数据,排序,和搜索算法。

coursera.org/course/algs4partI