Big O，你如何计算/近似? [英] Big O, how do you calculate/approximate it?
问题描述
大多数拥有 CS 学位的人肯定知道 Big O 代表什么.它帮助我们衡量算法的可扩展性.
Most people with a degree in CS will certainly know what Big O stands for. It helps us to measure how well an algorithm scales.
但我很好奇，你如何计算或近似算法的复杂度?
But I'm curious, how do you calculate or approximate the complexity of your algorithms?
推荐答案
这里我会尽量用简单的术语解释它，但请注意，我的学生需要几个月的时间才能最终掌握这个主题.您可以在 数据结构和算法的第 2 章中找到更多信息在 Java 书中.
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意识到您正在创建一个数学公式来计算在给定某种大小的输入的情况下执行了多少计算步骤.
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.
目的很简单:从理论角度比较算法，无需执行代码.步数越少，算法越快.
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.
例如，假设您有这段代码:
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)，一个计算计算步数的函数.函数的输入是要处理的结构的大小.表示这个函数的调用方式如:
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 such as:
Number_Of_Steps = f(data.length)
参数N 取data.length 值.现在我们需要函数 f() 的实际定义.这是从源代码完成的，其中每个有趣的行都从 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.
我们将添加函数的单个步骤数，并且局部变量声明和返回语句都不依赖于data数组的大小.
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语句的值.请记住，我们正在计算计算步骤的数量，这意味着 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
没有机械规则来计算for的主体被执行了多少次，你需要通过查看代码做了什么来计算.为了简化计算，我们忽略了 for 语句的变量初始化、条件和增量部分.
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:
- 去掉所有的常量
C. - 从
f()得到 polynomium 在它的标准形式. - 将多项式的项除以并按增长率排序.
- 保持
N接近无穷大时变大的那个.
- Take away all the constants
C. - From
f()get the polynomium in itsstandard form. - Divide the terms of the polynomium and sort them by the rate of growth.
- Keep the one that grows bigger when
Napproachesinfinity.
我们的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() 接近无穷大时会变大的一项(想想 limits) 这是 BigOh 参数，sum() 函数的 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)
<小时>
有一些技巧可以解决一些棘手的问题:尽可能使用求和.
例如，使用求和可以轻松解决此代码:
As an 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，与N 的大小无关.
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.
第一句中的 for 语句很棘手.虽然索引以 2 * N 结束，但增量为 2.这意味着第一个 for 只执行了 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)( ... )
句子编号two 更加棘手，因为它取决于i 的值.看一看:索引 i 取值:0, 2, 4, 6, 8, ..., 2 * N，第二个 for 被执行:N 次第一个，N- 2 第二个，N - 4 第三个......直到 N/2 阶段，第二个 for 永远不会被执行.
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 开始，并以大于或等于 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) 并采用 C 步骤.)
(We are assuming that foo() is O(1) and takes C steps.)
这里有一个问题:当 i 向上取值 N/2 + 1 时，内部求和以负数结束！这是不可能的，也是错误的.我们需要将求和分成两部分，这是 i 取 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>N/2，内部的 for 不会被执行，我们假设它的主体具有恒定的 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:
- 求和(w from 1 to N)( C ) = N * C
- 求和(w从1到N)(A(+/-)B)=求和(w从1到N)(A)(+/-)求和(w从1到N)(B)
- Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C是一个常数，与
w无关) - 求和(w from 1 to N)( w ) = (N * (N + 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 是:
O(N²)
这篇关于Big O，你如何计算/近似?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
