939

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

但我很好奇，你如何计算或近似算法的复杂性？

4

24 回答 24

1526

我将尽我所能在这里用简单的术语来解释它，但请注意，这个主题需要我的学生几个月才能最终掌握。您可以在 Java 中的数据结构和算法一书的第 2 章中找到更多信息。

没有可用于获得 BigOh 的机械程序。

作为一本“食谱”，要从一段代码中获取BigOh，您首先需要意识到您正在创建一个数学公式来计算在给定一定大小的输入的情况下执行了多少计算步骤。

目的很简单：从理论角度比较算法，无需执行代码。步数越少，算法越快。

例如，假设您有这段代码：

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
}

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

Number_Of_Steps = f(N)

所以我们有f(N)一个计算计算步数的函数。函数的输入是要处理的结构的大小。这意味着调用此函数，例如：

Number_Of_Steps = f(data.length)

参数N取值data.length。现在我们需要函数的实际定义f()。这是从源代码完成的，其中每个有趣的行都从 1 到 4 编号。

有很多方法可以计算 BigOh。从这一点开始，我们将假设每个不依赖于输入数据大小的句子都采用恒定C数量的计算步骤。

我们将添加函数的单独步数，并且局部变量声明和返回语句都不依赖于data数组的大小。

这意味着第 1 行和第 4 行各需要 C 步，函数有点像这样：

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

下一部分是定义for语句的值。请记住，我们正在计算计算步骤的数量，这意味着for语句的主体得到执行N次数。这与添加C,N次相同：

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

没有机械规则来计算for执行主体的次数，您需要通过查看代码的作用来计算它。为了简化计算，我们忽略了for语句的变量初始化、条件和增量部分。

为了得到实际的 BigOh，我们需要对函数进行渐近分析。大致是这样完成的：

  1. 带走所有的常数C。
  2. 从f()得到它的多项式standard form。
  3. 将多项式的各项除以增长率并对其进行排序。
  4. N留着靠近时变大的那一个infinity。

我们f()有两个术语：

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

去掉所有C常量和冗余部分：

f(N) = 1 + N ^ 1

由于最后一项是在f()接近无穷大时变大的项（考虑限制），这是 BigOh 参数，并且该sum()函数的 BigOh 为：

O(N)

有一些技巧可以解决一些棘手的问题：尽可能使用求和。

例如，可以使用求和轻松解决此代码：

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。

第for一个句子的陈述很棘手。当索引以 结束时2 * N，增量是 2。这意味着第一个for只执行N步骤，我们需要将计数除以二。

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，然后for执行第二个：N 次第一个，N - 2 第二个，N - 4第三个......直到 N / 2 阶段，第二个for永远不会被执行。

在公式上，这意味着：

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

同样，我们正在计算步数。根据定义，每个求和应该始终从 1 开始，并以大于或等于 1 的数字结束。

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

（我们假设这foo()是O(1)并采取了C措施。）

我们这里有一个问题：当i取值N / 2 + 1向上时，内部求和以负数结束！这是不可能的，也是错误的。i我们需要将总和分成两部分，这是关键时刻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 执行复杂度恒定。

现在可以使用一些恒等规则来简化求和：

  1. 求和（w 从 1 到 N）( C ) = N * C
  2. 求和(w 从 1 到 N)( A (+/-) B ) = 求和(w 从 1 到 N)( A ) (+/-) 求和(w 从 1 到 N)( B )
  3. Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C 是一个常数，独立于w)
  4. 求和（w 从 1 到 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²)
于 2011-01-31T15:33:54.120 回答
209

Big O 给出了算法时间复杂度的上限。它通常与处理数据集（列表）结合使用，但可以在其他地方使用。

几个如何在 C 代码中使用的示例。

假设我们有一个包含 n 个元素的数组

int array[n];

如果我们想访问数组的第一个元素，这将是 O(1)，因为无论数组有多大，获取第一个元素总是需要相同的常数时间。

x = array[0];

如果我们想在列表中找到一个数字：

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

这将是 O(n)，因为我们最多必须查看整个列表才能找到我们的号码。Big-O 仍然是 O(n)，即使我们可能会在第一次尝试中找到我们的数字并运行一次循环，因为 Big-O 描述了算法的上限（omega 表示下限，theta 表示紧界） .

当我们进入嵌套循环时：

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

这是 O(n^2)，因为对于外循环 ( O(n) ) 的每次传递，我们必须再次遍历整个列表，因此 n 的乘法使我们得到 n 的平方。

这几乎没有触及表面，但是当您开始分析更复杂的算法时，涉及证明的复杂数学就会发挥作用。希望这至少能让您熟悉基础知识。

于 2008-08-06T13:34:13.753 回答
108

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

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

O(1) - 判断一个数是偶数还是奇数；使用固定大小的查找表或哈希表

O(logn) - 使用二分搜索在有序数组中查找项目

O(n) - 在未排序的列表中查找项目；将两个 n 位数字相加

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

O(n 3 ) - 通过简单算法将两个 n×n 矩阵相乘

O(c n ) - 使用动态规划找到旅行商问题的（精确）解；使用蛮力确定两个逻辑语句是否等价

O(n!) - 通过蛮力搜索解决旅行商问题

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

于 2008-09-05T19:09:48.837 回答
43

小提醒：该big O符号用于表示渐近复杂度（即当问题的大小增长到无穷大时），它隐藏了一个常数。

这意味着在 O(n) 中的算法和 O(n 2 ) 中的算法之间，最快的并不总是第一个（尽管总是存在 n 的值，因此对于大小 >n 的问题，第一个算法是最快的）。

请注意，隐藏常量在很大程度上取决于实现！

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

有不同的时间复杂度：

  • 最坏的情况（通常最容易弄清楚，但并不总是很有意义）

  • 平均情况（通常更难弄清楚......）

  • ...

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

正如您所说，优化代码时确实应该始终使用premature optimisation is the root of all evil, 和（如果可能的话）分析。它甚至可以帮助您确定算法的复杂性。

于 2008-08-23T20:43:50.357 回答
30

看到这里的答案，我想我们可以得出结论，我们大多数人确实确实通过查看算法的顺序并使用常识而不是使用例如我们在大学时认为的主方法来计算它。话虽如此，我必须补充一点，即使是教授也鼓励我们（后来）实际考虑它，而不仅仅是计算它。

另外我想补充一下它是如何为递归函数完成的：

假设我们有一个类似（方案代码）的函数：

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

它递归地计算给定数字的阶乘。

第一步是尝试确定函数主体的性能特征，仅在这种情况下，主体中没有做任何特别的事情，只是乘法（或返回值 1）。

所以身体的表现是：O(1)（常数）。

接下来尝试确定递归调用的数量。在这种情况下，我们有 n-1 个递归调用。

所以递归调用的性能是：O(n-1)（顺序是 n，因为我们扔掉了无关紧要的部分）。

然后把这两者放在一起，你就可以得到整个递归函数的性能：

1 * (n-1) = O(n)

彼得，回答您提出的问题；我在这里描述的方法实际上处理得很好。但请记住，这仍然是一个近似值，而不是一个完整的数学正确答案。这里描述的方法也是我们在大学里教授的方法之一，如果我没记错的话，它用于比我在这个例子中使用的阶乘更高级的算法。
当然，这一切都取决于您对函数体的运行时间和递归调用次数的估计程度，但对于其他方法也是如此。

于 2008-08-07T08:10:04.780 回答
27

如果您的成本是多项式，只需保留最高阶项，不要使用乘数。例如：

O((n/2 + 1)*(n/2)) = O(n 2 /4 + n/2) = O(n 2 /4) = O(n 2 )

请注意，这不适用于无限系列。一般情况没有单一的方法，但对于一些常见情况，以下不等式适用：

O(log N ) < O( N ) < O( N log N ) < O( N 2 ) < O( N k ) < O(e n ) < O( n !)

于 2011-01-31T13:30:15.113 回答
23

我从信息的角度考虑。任何问题都包括学习一定数量的比特。

您的基本工具是决策点及其熵的概念。决策点的熵是它会给你的平均信息。例如，如果一个程序包含一个具有两个分支的决策点，则它的熵是每个分支的概率乘以该分支的逆概率的log 2的总和。这就是你通过执行该决定学到的东西。

例如，if具有两个分支的语句，两者的可能性相同，其熵为 1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1. 所以它的熵是 1 位。

假设您正在搜索包含 N 个项目的表，例如 N=1024。这是一个 10 位问题，因为 log(1024) = 10 位。因此，如果您可以使用具有同样可能结果的 IF 语句来搜索它，那么它应该做出 10 个决定。

这就是二进制搜索所得到的。

假设您正在进行线性搜索。您查看第一个元素并询问它是否是您想要的元素。它是的概率是 1/1024，不是的概率是 1023/1024。该决定的熵是 1/1024*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * 约 0 = 约 0.01 位。你学的太少了！第二个决定也好不了多少。这就是线性搜索如此缓慢的原因。事实上，你需要学习的位数是指数级的。

假设你正在做索引。假设表被预先排序到很多箱中，并且您使用键中的所有位中的一些位来直接索引表条目。如果有 1024 个 bin，对于所有 1024 个可能的结果，熵为 1/1024 * log(1024) + 1/1024 * log(1024) + ...。这是 1/1024 * 10 乘以 1024 个结果，或该索引操作的 10 位熵。这就是索引搜索速度快的原因。

现在考虑排序。你有 N 个项目，你有一个列表。对于每个项目，您必须搜索该项目在列表中的位置，然后将其添加到列表中。所以排序大约需要 N 倍于底层搜索的步数。

因此，基于具有大致相同可能性结果的二元决策的排序都需要 O(N log N) 步骤。如果基于索引搜索，则可以使用 O(N) 排序算法。

我发现几乎所有的算法性能问题都可以用这种方式来看待。

于 2009-03-10T13:24:13.873 回答
22

让我们从头开始。

首先，接受对数据的某些简单操作可以及时完成的​​原则，O(1)即与输入大小无关的时间。C 中的这些原始操作包括

  1. 算术运算（例如 + 或 %）。
  2. 逻辑运算（例如 &&）。
  3. 比较操作（例如，<=）。
  4. 结构访问操作（例如 A[i] 之类的数组索引，或带有 -> 运算符的指针）。
  5. 简单的赋值，例如将值复制到变量中。
  6. 调用库函数（例如，scanf、printf）。

这一原则的合理性需要对典型计算机的机器指令（原始步骤）进行详细研究。每个描述的操作都可以用少量的机器指令来完成；通常只需要一两条指令。因此，C 中的几种语句可以及时执行O(1)，即在与输入无关的某个恒定时间内执行。这些简单的包括

  1. 在其表达式中不涉及函数调用的赋值语句。
  2. 阅读声明。
  3. 编写不需要函数调用来评估参数的语句。
  4. 跳转语句 break、continue、goto 和 return 表达式，其中表达式不包含函数调用。

在 C 中，许多 for 循环是通过将索引变量初始化为某个值并在循环中每次将该变量递增 1 来形成的。当索引达到某个限制时，for 循环结束。例如，for循环

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

使用索引变量 i。它在循环中每次将 i 递增 1，当 i 达到 n-1 时迭代停止。

但是，目前，关注简单形式的 for 循环，其中最终值和初始值之间的差异除以索引变量的递增量告诉我们循环了多少次。这个计数是准确的，除非有办法通过跳转语句退出循环；在任何情况下，它都是迭代次数的上限。

例如，for 循环迭代((n − 1) − 0)/1 = n − 1 times，因为 0 是 i 的初始值，n - 1 是 i 达到的最高值（即，当 i 达到 n-1 时，循环停止并且 i = n- 不发生迭代1)，并且在循环的每次迭代中将 1 添加到 i 中。

在最简单的情况下，每次迭代在循环体中花费的时间都是相同的，我们可以将循环体的 big-oh 上限乘以循环的次数。严格来说，我们必须添加 O(1) 时间来初始化循环索引和 O(1) 时间来首次比较循环索引和 limit，因为我们测试的时间比我们绕循环多一次。但是，除非可以执行循环零次，否则初始化循环和测试一次限制的时间是一个可以被求和规则删除的低阶项。

现在考虑这个例子：

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

我们知道第 (1) 行需要O(1)时间。显然，我们绕着循环 n 次，因为我们可以通过从第 (1) 行找到的上限中减去下限然后加 1 来确定。由于主体，第 (2) 行，需要 O(1) 时间，我们可以忽略增加 j 的时间以及比较 j 与 n 的时间，这两者也是 O(1)。因此，第 (1) 行和第 (2) 行的运行时间是n 和 O(1) 的乘积，即O(n).

类似地，我们可以限定由第 (2) 到 (4) 行组成的外循环的运行时间，即

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

我们已经确定第 (3) 行和第 (4) 行的循环需要 O(n) 时间。因此，我们可以忽略 O(1) 时间来增加 i 并在每次迭代中测试 i 是否 < n，得出外循环的每次迭代需要 O(n) 时间的结论。

外循环的初始化 i = 0 和条件 i < n 的第 (n + 1) 次测试同样需要 O(1) 时间，可以忽略。最后，我们观察到我们绕过外循环 n 次，每次迭代花费 O(n) 时间，给出总 O(n^2)运行时间。

一个更实际的例子。

在此处输入图像描述

于 2014-02-02T15:30:25.447 回答
16

如果您想凭经验而不是通过分析代码来估计代码的顺序，您可以坚持一系列递增的 n 值和时间。在对数刻度上绘制你的时间。如果代码为 O(x^n)，则值应落在斜率为 n 的线上。

与仅仅研究代码相比，这有几个优点。一方面，您可以查看您是否处于运行时间接近其渐近顺序的范围内。此外，您可能会发现某些您认为是 O(x) 顺序的代码实际上是 O(x^2) 顺序，例如，因为花费在库调用上的时间。

于 2008-12-11T20:49:05.190 回答
12

基本上，90% 的时间出现的只是分析循环。你有单、双、三重嵌套循环吗？你有 O(n), O(n^2), O(n^3) 运行时间。

很少（除非您正在编写一个具有广泛基础库（例如，.NET BCL 或 C++ 的 STL）的平台）您会遇到比仅查看循环更困难的事情（for 语句、while、goto、 ETC...）

于 2008-08-14T15:35:50.200 回答
9

我认为一般来说不太有用，但为了完整起见，还有一个Big Omega Ω，它定义了算法复杂度的下限，还有一个Big Theta Θ，它定义了上限和下限。

于 2008-09-23T07:26:08.710 回答
8

大 O 表示法很有用，因为它易于使用并且隐藏了不必要的复杂性和细节（对于一些不必要的定义）。计算分治算法复杂性的一种好方法是树方法。假设您有一个带有中值过程的快速排序版本，因此您每次都将数组拆分为完全平衡的子数组。

现在构建一个与您使用的所有数组相对应的树。在根你有原始数组，根有两个子数组。重复此操作，直到底部有单个元素数组。

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

因此，我们可以通过 O(n*log(n)) 来限制工作量。

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

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

让我们假设 a 和 b 是 Java 中的 BigIntegers 或可以处理任意大数字的东西。大多数人会说这是一个 O(n) 算法而不会退缩。原因是您在 for 循环中有 n 次迭代，并且 O(1) 在循环侧工作。

但是斐波那契数很大，第 n 个斐波那契数是 n 的指数，因此仅存储它就需要 n 个字节的顺序。用大整数执行加法将需要 O(n) 的工作量。所以在这个过程中完成的工作总量是

1 + 2 + 3 + ... + n = n(n-1)/2 = O(n^2)

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

于 2008-08-08T13:53:20.930 回答
7

熟悉我使用的算法/数据结构和/或迭代嵌套的快速浏览分析。困难在于当您调用一个库函数时，可能会多次调用——您通常不确定您是否有时会不必要地调用该函数，或者它们正在使用什么实现。也许库函数应该有一个复杂性/效率度量，无论是 Big O 还是其他一些指标，都可以在文档甚至IntelliSense中找到。

于 2008-08-06T10:59:40.603 回答
7

将算法分解成你知道大 O 表示法的部分，并通过大 O 运算符进行组合。这是我知道的唯一方法。

有关更多信息，请查看有关该主题的Wikipedia 页面。

于 2008-08-06T11:34:26.803 回答
6

至于“你如何计算”大 O，这是计算复杂性理论的一部分。对于某些（许多）特殊情况，您可能可以使用一些简单的启发式方法（例如将嵌套循环的循环计数相乘），尤其是。当您想要的只是任何上限估计，并且您不介意它是否过于悲观时-我想这可能是您的问题所在。

如果你真的想回答任何算法的问题，你能做的最好的就是应用该理论。除了简单的“最坏情况”分析之外，我发现摊销分析在实践中非常有用。

于 2009-03-10T15:02:13.297 回答
6

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

对于第二个循环，在外循环i之间0并n包含在外循环中；然后当j严格大于时执行内部循环n，这是不可能的。

于 2011-01-31T14:36:02.787 回答
5

除了使用主方法（或其专长之一）之外，我还通过实验测试我的算法。这不能证明达到了任何特定的复杂度等级，但它可以保证数学分析是适当的。为了帮助确保这一点，我将代码覆盖工具与我的实验结合使用，以确保我正在练习所有案例。

作为一个非常简单的示例，假设您想对 .NET 框架的列表排序速度进行健全性检查。您可以编写如下内容，然后在 Excel 中分析结果以确保它们不超过 n*log(n) 曲线。

在此示例中，我测量了比较的次数，但检查每个样本量所需的实际时间也是谨慎的做法。但是，您必须更加小心，您只是在测量算法而不包括来自测试基础架构的工件。

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);
于 2008-09-05T18:33:32.480 回答
5

不要忘记考虑空间复杂性，如果内存资源有限，这也可能引起关注。因此，例如，您可能会听到有人想要一个恒定空间算法，这基本上是一种说法，即算法占用的空间量不取决于代码中的任何因素。

有时复杂性可能来自调用的次数，循环执行的频率，内存分配的频率等等是回答这个问题的另一部分。

最后，大 O 可用于最坏情况、最佳情况和摊销情况，通常它是用于描述算法可能有多糟糕的最坏情况。

于 2008-10-14T20:16:38.760 回答
4

经常被忽视的是算法的预期行为。它不会改变算法的大 O，但它确实与“过早优化......”的陈述有关

你的算法的预期行为是 - 非常愚蠢 - 你可以期望你的算法以多快的速度处理你最有可能看到的数据。

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

要真正确定它，您需要能够描述“输入空间”的概率分布（如果您需要对列表进行排序，该列表多久会被排序一次？它多久完全颠倒一次？如何通常它主要是排序的吗？）你知道这一点并不总是可行的，但有时你会这样做。

于 2009-03-10T14:30:13.263 回答
4

好问题！

免责声明：此答案包含虚假陈述，请参阅下面的评论。

如果您使用的是 Big O，那么您正在谈论更坏的情况（稍后会详细说明这意味着什么）。此外，一般情况下有大写 theta，最佳情况下有大 omega。

查看此站点以获得 Big O 的可爱正式定义：https ://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) 表示存在正常数 c 和 k，因此对于所有 n ≥ k，0 ≤ f(n) ≤ cg(n)。对于函数 f，c 和 k 的值必须是固定的，并且不能依赖于 n。

好的，那么现在我们所说的“最佳情况”和“最坏情况”复杂性是什么意思？

这可能通过例子最清楚地说明。例如，如果我们使用线性搜索在已排序的数组中查找数字，那么最坏的情况是当我们决定搜索数组的最后一个元素时，因为这需要与数组中的项目一样多的步骤。最好的情况是当我们搜索第一个元素时，因为我们将在第一次检查之后完成。

所有这些形容词案例复杂性的关键在于，我们正在寻找一种方法来根据特定变量的大小绘制一个假设程序运行到完成的时间量。但是，对于许多算法，您可以争辩说对于特定大小的输入没有单一的时间。请注意，这与函数的基本要求相矛盾，任何输入都不应超过一个输出。因此，我们提出了多个函数来描述算法的复杂性。现在，即使搜索大小为 n 的数组可能会花费不同的时间，具体取决于您在数组中查找的内容并与 n 成比例，我们可以使用最佳情况、平均情况创建算法的信息描述和最坏情况类。

抱歉，这篇文章写得太差了，而且缺乏很多技术信息。但希望它能让时间复杂度类更容易思考。一旦您对这些感到满意，就可以轻松解析程序并查找依赖于数组大小的 for 循环之类的内容，并根据您的数据结构进行推理在最坏的情况下。

于 2016-08-20T04:57:30.437 回答
3

我想从不同的角度解释 Big-O。

Big-O 只是为了比较程序的复杂性，这意味着当输入增加时它们的增长速度，而不是执行操作所花费的确切时间。

恕我直言，在大 O 公式中，您最好不要使用更复杂的方程式（您可能只使用下图中的方程式。）但是您仍然可以使用其他更精确的公式（如 3^n、n^3、.. .) 但不仅如此，有时还会产生误导！所以最好让它尽可能简单。

在此处输入图像描述

我想再次强调，在这里我们不想为我们的算法得到一个精确的公式。我们只想展示当输入增长时它是如何增长的，并在这个意义上与其他算法进行比较。否则，您最好使用不同的方法，例如基准测试。

于 2019-02-20T10:44:36.433 回答
2

对于代码A，外循环将执行n+1多次，'1'时间表示检查我是否仍然满足要求的过程。内部循环运行n时间，n-2时间.... 因此，0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

对于代码B，虽然内循环不会介入并执行foo()，但内循环将执行n次取决于外循环执行时间，即O(n)

于 2011-01-31T20:07:35.107 回答
2

我不知道如何以编程方式解决这个问题，但人们做的第一件事是我们在完成的操作数量中对某些模式的算法进行采样，比如 4n^2 + 2n + 1 我们有 2 条规则：

  1. 如果我们有一项总和，则保留增长率最大的项，而省略其他项。
  2. 如果我们有几个因素的乘积，则省略常数因素。

如果我们简化 f(x)，其中 f(x) 是完成操作数的公式，（上面解释过 4n^2 + 2n + 1），我们在此得到大 O 值 [O(n^2)案子]。但这必须考虑程序中的拉格朗日插值，这可能难以实现。如果真正的大 O 值是 O(2^n)，我们可能有类似 O(x^n) 的东西，那么这个算法可能不可编程。但是，如果有人证明我错了，请给我代码。. . .

于 2013-05-11T01:32:45.333 回答
1

首先，公认的答案是试图解释漂亮的花哨的东西，
但我认为，故意使 Big-Oh 复杂化并不是
程序员（或至少像我这样的人）寻找的解决方案。

大哦（简而言之）

function f(text) {
  var n = text.length;
  for (var i = 0; i < n; i++) {
    f(string.slice(0, n-1))
  }
  // ... other JS logic here, which we can ignore ...
}

上面的大哦是 f(n) = O(n!)其中n代表number输入集中的项目，f代表operation每个项目完成。

Big-Oh 表示法是算法复杂度的渐近上限。
在编程中：对于输入的大小，假定的最坏情况所用的时间，
或假定的最大逻辑重复次数。

计算

请记住（从上面的意思）；我们只需要受N（输入大小）影响的最坏情况时间和/或最大重复计数， 然后再看一下（接受的答案）示例：

for (i = 0; i < 2*n; i += 2) {  // line 123
    for (j=n; j > i; j--) {     // line 124
        foo();                  // line 125
    }
}

  1. 从这个搜索模式开始：

    • 找到N导致重复行为的第一行，
    • 或者导致执行的逻辑增加，
    • 但无论是否持续，忽略该行之前的任何内容。

  2. 似乎第 123 行是我们正在搜索的内容；-)

    • 乍一看，线似乎有2*n最大循环。
    • 但是再看一遍，我们看到了i += 2（那一半被跳过了）。
    • 所以， max repeat 只是n，把它写下来，就像f(n) = O( n 但不要关闭括号。

  3. 重复搜索直到方法结束，找到与我们的搜索模式匹配的下一行，这里是第 124 行

    • 这很棘手，因为奇怪的条件和反向循环。
    • 但是在记住我们只需要考虑最大重复次数（或最坏情况下所花费的时间）之后。
    • 就像说“反向循环j以 开头j=n，对吗？是的，n似乎是最大可能的重复次数”一样简单，所以，添加n到先前写下的结尾，但是像“ ( n ”（而不是+ n，因为这是在先前的循环）和右括号，只有当我们发现前一个循环之外的东西时。

搜索完成！为什么？因为第 125 行（或任何其他行）与我们的搜索模式不匹配。
我们现在可以关闭任何括号（在我们的记录中左开），结果如下：

f(n) = O( n( n ) )

尝试进一步缩短 " n( n )" 部分，例如：

  • n( n ) = n * n
  • = n 2
  • 最后，只需用 Big Oh 符号包装它，如O(n 2 )或 O(n^2) 而不进行格式化。
于 2021-07-02T10:51:35.063 回答