使用代码解释Big O概念

在计算机科学中，Big O是用来描述算法的性能表现或复杂度的概念。Big O描述了最坏情形下，算法执行所需的时间或空间（比如内存或磁盘）。

O(1)

如果算法的执行总是需要相同的时间（或空间），而与输入数据的规模无关，那这个算法的复杂度为O(1)

bool IsFirstElementNull(String[] strings)
{
    if(strings[0] == null)
    {
        return true;
    }
    return false;
}

O(N)

复杂度为O(N) 的算法，其执行所需的时间或空间呈线性增长并与输入数据的规模成正比。下面的例子说明了Big O应用在最坏情形下：在for循环的任何一次迭代中，匹配的字符串都可能被提前找到并使函数返回，但是Big O概念表示的是最坏情形下的算法复杂度，所以总是假定算法执行上限次数的运行，即最大次数的迭代。

bool ContainsValue(String[] strings, String value)
{
    for(int i = 0; i < strings.Length; i++)
    {
        if(strings[i] == value)
        {
            return true;
        }
    }
    return false;
}

O(N²)

O(N2)表示算法的复杂度与输入数据的规模的平方成正比。这在涉及嵌套循环的算法中常见。更深层次的循环则会使复杂度增加为O(N³), O(N⁴)……。

bool ContainsDuplicates(String[] strings)
{
    for(int i = 0; i < strings.Length; i++)
    {
        for(int j = 0; j < strings.Length; j++)
        {
            if(i == j) // Don’t compare with self
            {
                continue;
            }
            if(strings[i] == strings[j])
            {
                return true;
            }
        }
    }
    return false;
}

O(2^N)

O(2^N)则表示算法随输入数据规模的每增加一个，其复杂度也会翻番。其执行时间也会迅速地增加。

对数复杂度O(log N)

下面会通过一个例子说明对数复杂度。

二分法搜索（Binary search）是一项用于搜索已排序数据的技术。它通过选出数据的中项，与目标数值相比较。如果两数值相匹配，则返回成功。如果目标数值大于中项，则取出数据集合中大于中项的部分进行上面的操作。类似地，如果目标数值小于中项，则取出小于中项的部分进行相同的操作。这样，程序不断地二等分分数据集合，直到数值匹配或数据集合无法分解为止。

这种算法被描述为O(log N)。

重复地二等分数据集合的过程，如果绘制成图表，会发现开始时会达到一个顶峰，然后随着数据的增加，曲线会逐渐趋向平缓。使数据集合加倍对效率的影响也会很小，因为在一次迭代之后，所需处理的数据量会减少一半。这样使算法在处理规模较大的数据集合时会非常有效率。