大写“O”符号详解

通常您会开发一个测试数据库。它可能只供 10 人访问，所以你的编程和测试工作可以流畅地进行。一旦完成开发和 QA’d (通过质量检验)，它将会正式上线（发布）， 人们开始访问该网站。过了一年左右，该网站的响应速度越来越慢。在添加更多的数据库服务器没有起到作用后，您的系统管理员在my.cnf’s度过了他的” 假期”, 甚至为系统新增了许多内存容量也无济于事。听起来像是在大批量访问网站的情况下程序（代码）结构制约了访问效果。系统对40000人的用户列表信息不能完 成排序或处理，或者数组的元素超过了100万项，甚至简单的校验函数减缓了访问速度。为什么？到底发生了什么？

大多数PHP 开发人员从未听说过Big-O ,然而在Web开发中 Big-O 也许比其他任何部分都更加重要(好吧，也许除了系统和操作系统编程以外:) )。代码块一天也许只被 10个用户执行，但是相同的代码很可能每分钟运行了成千上万次。

 

什么是 Big-O ？

Big-O 或者 landau notation(朗道标记法)是一种 定义一个函数尺度随着参数变化研究函数运行情况 的数学原理。换句话说：Big-O 会告诉你，一个strpos()函数在分别接收 10个和1000000 个 字符长度的字符串参数时运行时间的关系。它不会告诉你明确的运行时间，但是它(Big-O)会告诉你参数和运行时间的趋势关系。

那么，也许你会问：这是怎么回事？

具体来说...

假设您有一个函数，它根据一定的条件将数组中的数据进行排序。例如，按照姓氏的字母顺序排序。 每个人都可以想象出： 对10个用户将会比 对1000万个用户排序快很多。但是（排序）如何更快或更好：后者将会大概花费多长时间？当知道问题的答案后，你会清楚在大量用户访问的环境下你的代码 (系统)运行的速度。您将会明白系统的首要瓶颈因素：您的代码 或 硬件？换句话说，你要开始意识到系统的可扩展性。

示例 1 ：

假设您有一个函数IsEven() ：

 

function isEven ($iNumber) { // 方法a
    return ( ($iNumber & 1) == 0);
}

 

此函数将会判断一个数值是否是偶数，如果是则返回值true, 否则返回值false 。

对于此函数，无论传入的参数是 int(1) 还是int(100000005)，都没关系；如果函数总是使用同样的时间去判断参数并返回值。

现在，假设我们把函数修改成以下形式：

 

function isEven ($iNumber) { // 方法b
    $bEven = true;
    for ($i=0; $i!=abs($iNumber); $i++) {
    if ($bEven == true) {
        $bEven = false;
    } else {
        $bEven = true;
    }
    return $bEven;
}

 

当然，（函数）这种写法没有多大意义。但是我偶尔会看到使用低效率算法的代码，所以上面的例子足以证明我的观点。

当函数（方法b）接收的参数是 int(1) ，for循环语句只执行一次。 函数运行的很快，没有问题出现。然而，当我们想判断数值1000000是否是偶数时(接收的参数是 int(1000000) ) ,我们可能会遇到一点麻烦，因为for循环必须执行1000000次函数才能返回判断结果。

如果我们把函数(方法a)放到一个图表中， X 轴表示参数 $iNumber( 取值范围 ：1 ~ 1000 ) ，Y 轴表示函数得到判断结果所花费的时间，那么我们将会得到一条水平线的图形。这就表明函数无论接收什么样的 int数值，得到判断结果所花费的时间总是相同的。这可以标记为 O(1),这种函数的性能是最优的。无论您传入的参数是什么，函数得到处理结果所花费的时间总是一样。代码(函数)可扩展性的梦想成真了 :)

现在，我们一起来分析函数(方法b) 。同样 X 轴表示参数 $iNumber ， 我们将会看到一条上升的直线。我们用 O(N)标记此函数(N代表参数本身或循环的次数，函数运算规模) 。

参数的数值大小与函数运算时间有直接关系。

 

示例 2 ：

 

function getModuleInfoByID ($iModuleID) { // 方法 c
    foreach ($this->_aModuleInfo as $aInfo) {
        if ($aInfo['id'] == $iModuleID) return $aInfo;
    }
    return null;
}

当参数id在遍历的对象中能匹配上时，函数(方法c)则返回对应的module信息；否则返回null值。这是一种非常常见的方式通过遍历数组来查找数据。 这类函数可以标记为O(N) , 其中N是模块信息的数量，也是集合 $_aModuleInfo 元素的个数。

我们如何来优化这种类型函数的性能呢?

如果不使用遍历(迭代)而能实现查找数据的功能，将会是很好的选择。通过优化代码结构提高运算效率(降低 O-line 的斜率)总是麻烦的事情 :) 为了做到这一点，我们要对函数(方法c)做一些修改。例如，如果我们把集合元素存放到一个关联数组中，并且把元素的id 作为key(键)，如下所示：

 

 

function getModuleInfoByID ($iModuleID) { //方法 d
    if(isset($this->_aModuleInfo[$iModuleID]))
        return $this-> _aModuleInfo[$iModuleID];
    return null;
}

 

 

在函数(方法d)中，我们不用担心 $_aModuleInfo 数组的长度是多少。此函数运行时不需要执行遍历操作，而且无论是1个还是 1000000个 moduleInfo 元素都没关系。

然而，我们需要注意以下几点：

● 函数isset()起什么作用？它可以用 O(1)还是用O(N)来标记？或者更糟？您必须要知道函数(包括它调用的函数)的运算性能。

● 您的以上对函数运算性能的检查是基于 PHP-level 。基于 CPU-level，结果也许是另一回事儿。例如：CPU处理数值数组要比处理关联数组快很多(前者不涉及哈希查找)。

然而，在PHP中处理数值数组和关联数组的时间没有多大差别。

 

各种各样的O的区别

O’s的类型有很多并且很复杂 :) 坚持往下看哦，瞧瞧下面哪一种O’s能匹配您编写的函数。您可能从来不需要一个精确的公式，但是只要您知道您的函数运算性能模型类 似 O(log N),而不是 O(N),您已经知道了很多...

下面是O-functions列表，按性能从优到劣依次排序：

 

● O(1)

常数时间，无论参数是什么，函数运算的时间总是相同的。

● O(log N)

对数时间，函数运算时间在开始时快速增长，但是过了一会儿，函数运算时间增长缓慢。这是个好消息，当您知道有许多对象要处理时(例如用户、文章、评论排序)。

● O(n) Linear(线性)

参数的大小与函数运算时间有直接关系。两倍参数大小意味着两倍的运算时间。

 

● O(n^2) Quadratic(平方)

大多数时候，这意味着拥有相同数据集的两个迭代器要参与运算(像许多未优化的排序算法)。

 

● O(n^3) Cubic(立方)

与Quadratic(平方)一样，只是多了一个额外的循环。这对函数的运算性能来说是灾难性的。

 

● O(n!) Factorial(阶乘)

这些图形几乎是直线上升(例如，10的阶乘是 3628800 ，这意味着大量的迭代操作)。如果您的函数性能模型与此类似，建议重写函数，这种函数的运算性能很糟糕。

 

说明：图片来源 -- http://nl.wikipedia.org/wiki/Bestand:Exponential.png

其中，红线是 O(n)线性图，蓝线是O(n^3)立方图，绿线是O(2^n)指数图。

注意，尽管在x<=8范围内绿线的y值(时间)是最优的，但是在x>10范围内，绿线的y值(时间)是最差的。

在读取数据时，我们至少统计查询了一半的数组元素。获取一个在 0 到 100范围内的随机数，有50%的机会这个随机数小于 50，同时有50%的机会这个随机数大于等于50 。然而，Big-O 要考虑最坏的情况。所以按顺序搜索长度为N的数组应该标记为O(N), 而不是 O(N/2) 。

Big-O 注意事项

请注意，O(*)标记没有说任何关于运算速度本身的事情。它只是告诉您函数的运算速度和参数是相对应的。例如，在某些情况下，一个 O(n)性能的函数可能比一个O(log n)或O(1) 性能的函数运算的快。然而，会有一个转折点，其它的函数运算的更快。您需要在函数、算法复杂性以及运算速度之间找一个平衡点。反复测试您函数的运算时间 （性能）并比较结果。它们的运算性能也许没有您想象的那么糟糕(也许比你想的还要差;) )。测试中代码会告诉你结果，但是不经测试您是不知道的 :)

总结

了解您的函数以及它的运算性能。但是要确保优化函数性能不能过度。让每个函数的运算性能达到 O(1)水平是件完美的事情，但是实际上优化工作是没有尽头的，而且总要在开发时间、预算和速度以及优化工作之间寻找一个平衡点。

 

1. 本文由mathew翻译，由程序员学架构校审

2. 本文译自https://www.adayinthelifeof.nl/2009/12/21/big-o-notation/

原文作者：Joshua Thijssen December 21, 2009

3. 转载请务必注明本文出自：程序员学架构(微信号：archleaner )

4. 更多文章请扫码：