大O，你怎么计算/近似它？ [英] Big O, how do you calculate/approximate it?

问题描述

大多数人有一定程度的CS肯定会知道什么大O表示。 它帮助我们衡量如何（中）高效的算法确实是，如果你知道哪个类别你正在试图解决的问题奠定了你可以计算出，如果它仍然是可以挤出一点额外的性能。 ¹

Most people with a degree in CS will certainly know what Big O stands for. It helps us to measure how (in)efficient an algorithm really is and if you know in what category the problem you are trying to solve lays in you can figure out if it is still possible to squeeze out that little extra performance.¹

不过我很好奇，怎么办的您的计算或近似您算法的复杂性？

But I'm curious, how do you calculate or approximate the complexity of your algorithms?

¹ <子>但正如他们所说，不要过分，的 premature优化是一切罪恶的根源，并优化无正当原因应受到的名字。

¹ _{but as they say, don't overdo it, premature optimization is the root of all evil, and optimization without a justified cause should deserve that name as well.}

推荐答案

我是一个教授的助手在我的数据结构和算法课程的本地大学。我会尽我所能在这里解释一下简单的条件，但被警告说，这个话题把我的学生们几个月来最终掌握。你可以找到数据结构和算法在Java中本书的第二章的更多信息。

I'm a professor assistant at my local university on the Data Structures and Algorithms course. I'll do my best to explain it here on simple terms, but be warned that this topic takes my students a couple of months to finally grasp. You can find more information on the Chapter 2 of the Data Structures and Algorithms in Java book.

没有机械过程的，可用于获取BigOh

There is no mechanical procedure that can be used to get the BigOh.

作为一个食谱，以获得 BigOh 由一块$ C $的c您首先需要实现要创建一个数学公式来算多少步的计算得到执行给予一定大小的输入。

As a "cookbook", to obtain the BigOh from a piece of code you first need to realize that you are creating a math formula to count how many steps of computations get executed given an input of some size.

的目的很简单：从理论的角度来看比较算法，而无需执行code。的步骤的较小的数目，更快的算法

The purpose is simple: to compare algorithms from a theoretical point of view, without the need to execute the code. The lesser the number of steps, the faster the algorithm.

例如，假设你有这片code：

For example, let's say you have this piece of code:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

这个函数返回数组中的所有元素的总和，我们要创建一个公式来算计算复杂度该函数的：

This function returns the sum of all the elements of the array, and we want to create a formula to count the computational complexity of that function:

Number_Of_Steps = f(N)

因此​​，我们有 F（N），一个函数来计算的计算步数。该函数的输入是要处理的结构的大小。这意味着，这个函数被调用suchs为：

So we have f(N), a function to count the number of computational steps. The input of the function is the size of the structure to process. It means that this function is called suchs as:

Number_Of_Steps = f(data.length)

参数 N 取 data.length 值。现在，我们需要的功能 F的实际定义（）。这是从源$ C ​​$ C，其中每个感兴趣的线被编号为1至4进行。

The parameter N takes the data.length value. Now we need the actual definition of the function f(). This is done from the source code, in which each interesting line is numbered from 1 to 4.

有很多方法来计算BigOh。从现在开始，我们将假定每一句话，不依赖于输入数据的大小需要一个恒定的 C 数计算步骤。

There are many ways to calculate the BigOh. From this point forward we are going to assume that every sentence that doesn't depend on the size of the input data takes a constant C number computational steps.

我们将添加的步骤的功能的个人号码，和既不在本地变量声明也不返回语句取决于数据的大小阵列。

We are going to add the individual number of steps of the function, and neither the local variable declaration nor the return statement depends on the size of the data array.

这意味着，线1和4需要的每个步骤C量，而且功能有些这样的：

That means that lines 1 and 4 takes C amount of steps each, and the function is somewhat like this:

f(N) = C + ??? + C

接下来的部分是定义的语句中的值。请记住，我们正在点的计算步数，这意味着的身体for语句被执行N次。这是一样的加入 C ， N 时间：

The next part is to define the value of the for statement. Remember that we are counting the number of computational steps, meaning that the body of the for statement gets executed N times. That's the same as adding C, N times:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

没有机械的规则来算多少次的身体为被执行，则需要通过看什么是code做算什么呢。为了简化计算，我们忽略了为声明的变量初始化，条件和增量部分。

There is no mechanical rule to count how many times the body of the for gets executed, you need to count it by looking at what does the code do. To simplify the calculations, we are ignoring the variable initialization, condition and increment parts of the for statement.

要得到我们所需要的渐近分析实际BigOh。这大致是这样做的：

To get the actual BigOh we need the Asymptotic analysis of the function. This is roughly done like this:

1. 带走所有的常量 C 。
2. 从 F（）获得 polynomium 在其标准形式。
3. 除以polynomium的条款和增长率进行排序。
4. 保持一个较大的增长，当 N 办法无限。

1. Take away all the constants C.
2. From f() get the polynomium in its standard form.
3. Divide the terms of the polynomium and sort them by the rate of growth.
4. Keep the one that grows bigger when N approaches infinity.

我们的 F（）有两个方面：

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

考虑了所有的 C 常数和多余的部分：

Taking away all the C constants and redundant parts:

f(N) = 1 + N ^ 1

由于最后一项就是其中之一变大时， F（）接近无穷大（想起的限制）这是BigOh说法，而和（）函数的BigOh：

Since the last term is the one which grows bigger when f() approaches infinity (think on limits) this is the BigOh argument, and the sum() function has a BigOh of:

O(N)

---

有一些技巧来解决一些棘手的：使用求和中时，您可以。有已经被证明是正确的一些方便总和身份。

---

There are a few tricks to solve some tricky ones: use summations whenever you can. There are some handy summation identities already proven to be correct.

作为另一实例，此code可以容易地使用求和解决：

As another example, this code can be easily solved using summations:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

您必须要问的第一件事是执行的foo的顺序（）。虽然通常是要 O（1），你需要问你的教授了。 O（1）办法（差不多，大部分）恒 C ，独立的大小ñ 。

The first thing you needed to be asked is the order of execution of foo(). While the usual is to be O(1), you need to ask your professors about it. O(1) means (almost, mostly) constant C, independent of the size N.

上句头号的为语句是棘手。虽然指数结束2 * N ，增量是由两个完成的。这意味着，在第一个为被执行仅 N 步骤，我们需要两个分计数。

The for statement on the sentence number one is tricky. While the index ends at 2 * N, the increment is done by two. That means that the first for gets executed only N steps, and we need to divide the count by two.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

这句话数量的两个的是更棘手，因为它取决于 i的值。看一看：索引i取值：0，2，4，6，8，...，2 * N，第二个为得到执行：N时代第一个，N - 2第二，N - 4的第三个......到N / 2阶段，在其第二个为从来没有被执行

The sentence number two is even trickier since it depends on the value of i. Take a look: the index i takes the values: 0, 2, 4, 6, 8, ..., 2 * N, and the second for get executed: N times the first one, N - 2 the second, N - 4 the third... up to the N / 2 stage, on which the second for never gets executed.

在公式，这意味着：

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

此外，我们指望的步数。根据定义，每一个总和应始终从1开始，并结束在一些较大的，或相等以上的。

Again, we are counting the number of steps. And by definition, every summation should always start at one, and end at a number bigger-or-equal than one.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

（我们假设 FOO（）是 O（1），并采取 ç步骤。）

(We are assuming that foo() is O(1) and takes C steps.)

我们这里有一个问题：当我取值 N / 2 + 1 向上，内求和结束于一个负号！这是不可能的，错误的。我们需要拆分的总和二，作为关键点的时刻我需要 N / 2 + 1 。

We have a problem here: when i takes the value N / 2 + 1 upwards, the inner Summation ends at a negative number! That's impossible and wrong. We need to split the summation in two, being the pivotal point the moment i takes N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

由于关键时刻 I＆GT; N / 2 ，内层为不会得到执行，我们假设在它的身上常数C执行的复杂性。

Since the pivotal moment i > N / 2, the inner for won't get executed, and we are assuming a constant C execution complexity on its body.

现在的求和可以使用一些身份规则进行简化：

Now the summations can be simplified using some identity rules:

1. 在求和（W从1到N）（C）= N * C
2. 在求和（W从1到N）（A（+/-）B）=求和（W从1到N）（A）（+/-）求和（W从1到N）（B）
3. 在求和（W从1到N）（W * C）= C *求和（W从1到N）（W）（C为常数，独立于是W ）
4. 在求和（W从1到N）（W）=（W *（W + 1））/ 2

1. Summation(w from 1 to N)( C ) = N * C
2. Summation(w from 1 to N)( A (+/-) B ) = Summation(w from 1 to N)( A ) (+/-) Summation(w from 1 to N)( B )
3. Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C is a constant, independent of w)
4. Summation(w from 1 to N)( w ) = (w * (w + 1)) / 2

应用一些代数：

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

而BigOh是：

And the BigOh is:

O(N ^ 2)

这篇关于大O，你怎么计算/近似它？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！