大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。

但我很好奇,你是如何计算或近似你的算法的复杂性的?


当前回答

虽然知道如何计算出特定问题的大O时间是有用的,但了解一些一般情况可以在很大程度上帮助您在算法中做出决策。

以下是一些最常见的案例,摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) -确定一个数字是偶数还是奇数;使用常量大小的查找表或哈希表

O(logn) -用二分搜索在排序数组中查找一个项

O(n) -在未排序的列表中查找一个项;两个n位数相加

O(n2) -用一个简单的算法乘以两个n位数字;添加两个n×n矩阵;冒泡排序或插入排序

O(n3) -用简单的算法乘以两个n×n矩阵

O(cn) -使用动态规划找到旅行商问题的(精确)解;使用蛮力判断两个逻辑语句是否等效

O(n!) -通过暴力搜索解决旅行推销员问题

O(nn) -通常用来代替O(n!)来推导更简单的渐近复杂度公式

其他回答

经常被忽视的是算法的预期行为。它不会改变你的算法的大o,但它确实与“过早优化.. ..”的声明有关

你的算法的预期行为是——非常简单——你期望你的算法在你最有可能看到的数据上工作的速度有多快。

例如,如果你在一个列表中搜索一个值,它是O(n),但如果你知道你看到的大多数列表都有你的值在前面,你的算法的典型行为会更快。

为了真正确定它,你需要能够描述你的“输入空间”的概率分布(如果你需要对一个列表排序,这个列表已经被排序的频率是多少?有多少次是完全相反的?多长时间进行一次排序?)这并不总是可行的,但有时你知道。

大O符号很有用,因为它很容易使用,并且隐藏了不必要的复杂性和细节(对于一些不必要的定义)。求解分治算法复杂性的一种好方法是树法。假设你有一个带有中值过程的快速排序版本,所以你每次都将数组分割成完美平衡的子数组。

现在,构建一个与所使用的所有数组对应的树。根结点有原始数组,根结点有两个子数组。重复此步骤,直到底部有单个元素数组。

由于我们可以在O(n)时间内找到中位数,并在O(n)时间内将数组分成两部分,因此在每个节点上所做的功为O(k),其中k是数组的大小。树的每一层都包含(最多)整个数组,所以每层的功是O(n)(子数组的大小加起来是n,因为每层有O(k),我们可以把它加起来)。树中只有log(n)层,因为每次我们将输入减半。

因此,我们可以将功的上限设为O(n*log(n))。

然而,大O隐藏着一些我们有时不能忽视的细节。考虑计算斐波那契数列

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

假设a和b在Java中是biginteger或者其他可以处理任意大数字的东西。大多数人会毫不犹豫地说这是一个O(n)算法。理由是,在for循环中有n次迭代,而O(1)工作在循环的一侧。

但是斐波那契数列很大,第n个斐波那契数列是n的指数级,所以仅仅是存储它就需要n个字节。对大整数执行加法将花费O(n)个工作量。所以在这个过程中所做的总功是

一加二加三……+ n = n(n-1)/2 = O(n)

所以这个算法在二次时间内运行!

小提示:大O符号是用来表示渐近复杂度的(也就是说,当问题的大小增长到无穷大时),它隐藏了一个常数。

这意味着在O(n)和O(n2)的算法之间,最快的并不总是第一个算法(尽管总是存在一个值n,这样对于大小为>n的问题,第一个算法是最快的)。

注意,隐藏常数很大程度上取决于实现!

此外,在某些情况下,运行时并不是输入大小为n的确定函数。以快速排序为例:对n个元素的数组进行排序所需的时间不是一个常数,而是取决于数组的初始配置。

有不同的时间复杂度:

最坏的情况(通常是最简单的,但并不总是很有意义) 一般情况下(通常很难弄清楚…) ...

一个很好的介绍是R. Sedgewick和P. Flajolet的《算法分析导论》。

正如你所说,过早的优化是万恶之源,(如果可能的话)在优化代码时真的应该总是使用分析。它甚至可以帮助您确定算法的复杂性。

对于第一种情况,内部循环执行了n-i次,因此执行的总次数是i从0到n-1(因为小于,而不是小于或等于)的和。你得到最后n * (n + 1) / 2,所以O (n²/ 2)= O (n²)。

对于第二个循环,i在0到n之间。然后,当j严格大于n时执行内循环,这是不可能的。

不要忘记考虑空间的复杂性,如果内存资源有限,这也是一个值得关注的问题。例如,你可能听到有人想要一个常数空间算法,这基本上是说算法所占用的空间量不依赖于代码中的任何因素。

有时,复杂性可能来自于某个东西被调用了多少次,循环执行的频率,内存分配的频率,等等,这是回答这个问题的另一部分。

最后,大O可以用于最坏情况、最佳情况和摊销情况,其中通常用最坏情况来描述算法可能有多糟糕。