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

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


当前回答

大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)

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

其他回答

如果您希望根据经验而不是通过分析代码来估计代码的顺序,您可以插入一系列不断增加的n值,并为代码计时。在对数刻度上绘制你的时间。如果代码是O(x^n),值应该落在斜率为n的直线上。

这比只研究代码有几个优点。首先,您可以看到您是否在运行时接近其渐近顺序的范围内。此外,您可能会发现一些您认为是O(x)阶的代码实际上是O(x^2)阶的代码,例如,因为花在库调用上的时间。

大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)

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

基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。

很少(除非你正在编写一个具有广泛基库的平台(例如,.NET BCL或c++的STL),你会遇到比查看循环(for语句,while, goto等…)更困难的事情。

熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于,当您调用一个库函数时,可能会多次调用—您常常不确定是否在不必要的时候调用了函数,或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量,无论是大O还是其他度量,都可以在文档或智能感知中得到。

将算法分解成你知道的大O符号,并通过大O运算符组合。这是我知道的唯一办法。

欲了解更多信息,请查看有关该主题的维基百科页面。