O八岁?

这个问题在这里已经有了答案:

  • “大O”符号的简单英文解释是什么? 36个答案

  • 思考的一种方式是:

    O(N ^ 2)表示每个元素,你正在对其他元素进行一些操作,比如比较它们。 泡沫排序就是一个例子。

    O(N log N)表示对于每个元素,您正在做的事情只需要查看元素的log N。 这通常是因为你知道一些关于让你做出有效选择的元素。 最有效的排序就是一个例子,比如合并排序。

    O(N!)表示为N个元素的所有可能排列做些事情。 旅行推销员就是这样一个例子,那里有N! 访问节点的方式,而强力解决方案则是查看每个可能排列的总成本以找到最佳排列。


    Big-O符号对您的代码意味着的重大事情是,当您将其操作的“事物”数量加倍时,它将如何扩展。 这里有一个具体的例子:

    Big-O       |  computations for 10 things |  computations for 100 things
    ----------------------------------------------------------------------
    O(1)        |   1                         |     1
    O(log(n))   |   3                         |     7
    O(n)        |  10                         |   100
    O(n log(n)) |  30                         |   700
    O(n^2)      | 100                         | 10000
    

    因此,取O(n log(n))与O(n ^ 2)的冒泡排序的快速排序。 排序10件事时,快速排序比泡泡排序快3倍。 但是当分拣100件东西时,速度要快14倍! 清楚地选择最快的算法是非常重要的。 当你到达有数百行的数据库时,它可能意味着你的查询在0.2秒内执行,而不是花费数小时。

    要考虑的另一件事是,一个不好的算法是摩尔定律无法帮助的一件事。 例如,如果你有一些科学的计算结果是O(n ^ 3),并且它可以计算一天100件事情,那么处理器速度加倍只会让你在一天中得到125件事情。 然而,敲那个计算到O(n ^ 2),你每天做1000件事。

    澄清:实际上,Big-O在相同的特定尺寸点上没有提到不同算法的比较性能,而是关于相同算法在不同尺寸点的比较性能:

                     computations     computations       computations
    Big-O       |   for 10 things |  for 100 things |  for 1000 things
    ----------------------------------------------------------------------
    O(1)        |        1        |        1        |         1
    O(log(n))   |        1        |        3        |         7
    O(n)        |        1        |       10        |       100
    O(n log(n)) |        1        |       33        |       664
    O(n^2)      |        1        |      100        |     10000
    

    您可能会发现将其可视化很有用:

    大O分析

    此外,在LogY / LogX规模下,函数n1 / 2,n,n2都看起来像直线,而在LogY / X尺度2n上,en,10n是直线,而n! 是linearithmic(看起来像n log n)。

    链接地址: http://www.djcxy.com/p/6739.html

    上一篇: O for Eight Year Olds?

    下一篇: Java code optimization tips and tricks