algorithm - Big O，你如何计算/近似？

Question

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

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

Answer 1

我会尽我所能用简单的术语在这里解释它，但请注意，这个主题需要我的学生几个月才能最终掌握。您可以在 Data Structures and Algorithms in Java 的第 2 章中找到更多信息。书。

没有mechanical procedure可用于获取 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
}

此函数返回数组所有元素的总和，我们要创建一个公式来计算 computational complexity该功能的:

Number_Of_Steps = f(N)

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

Number_Of_Steps = f(data.length)

参数 N需要 data.length值(value)。现在我们需要函数的实际定义 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的 body 有多少次没有机械规律可以计算。被执行，你需要通过查看代码做了什么来计算它。为了简化计算，我们忽略了 for 的变量初始化、条件和增量部分。陈述。

要获得实际的 BigOh，我们需要 Asymptotic analysis的功能。这大致是这样完成的:

带走所有的常数 C .

来自 f()获取 polynomium在其 standard form .

将多项式的项除以并按增长率排序。

保持时变大的那个N接近 infinity .

我们的 f()有两个术语:

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

带走所有 C常量和冗余部分:

f(N) = 1 + N ^ 1

由于最后一项是当 f() 时变大的一项。接近无穷大(想想 limits)这是 BigOh 参数，而 sum()函数有一个 BigOh:

O(N)

有一些技巧可以解决一些棘手的问题:使用 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 .
for关于第一句话的陈述很棘手。而指数收于 2 * N ，增量由两个完成。这意味着第一个 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 执行复杂性。

现在可以使用一些身份规则来简化求和:

求和(w 从 1 到 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 从 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²)