算法的时间和 Space 复杂度 - 大 O 表示法

Question

我正在尝试分析一个简单算法的 Big-O-Notation，我已经工作了一段时间用它。因此，我进行了一项分析，并试图根据以下代码的规则确定这是否正确：

public int Add()
{
  int total = 0; //Step 1

  foreach(var item in list) //Step 2
  {
    if(item.value == 1) //Step 3
    {
      total += 1; //Step 4
    }
  }
  return total;
}

如果给变量或集合赋值，此时复杂度根据BigO[=52的规则确定=] 是 O(1)。所以第一阶段将是 O(1) - 这意味着无论输入大小是多少，程序都将执行相同的时间和内存 space.

第二步得出foreach循环。循环中有一件事很清楚。根据输入，循环迭代或运行。例如，对于输入 10，循环迭代 10 次，for 20、20 次。完全取决于输入。按照大O的规则，复杂度为O(n) - n 是输入的个数。所以在上面的代码中，循环根据列表中的项目数进行迭代。

在这一步中，我们定义了一个变量来确定条件检查（参见编码中的第 3 步）。在那种情况下，复杂度是 O(1) 根据 Big O规则。

同理，第4步，也没有变化（见编码中的第4步）。如果条件检查为真，则 total 变量将值递增 1。因此我们写 - 复杂度 O(1)。

所以如果上面的计算是完美的，那么最终的复杂度为：

O(1) + O(n) + O(1) + O(1) or (O(1) + O(n) * O(1) + O(1))

我不确定这是否正确。但我想，如果这不是完美的，我希望对此进行一些澄清。谢谢。

Answer 1

您的分析不完全正确。

第 1 步确实需要 O(1) 次操作
第 2 步确实需要 O(n) 次操作
第 3 步采用 O(1) 次操作，但它执行了 n 次，因此它对复杂度的整体贡献是 O(1*n)=O(n)
第4步需要O(1)次操作，但最多执行n次，所以它对复杂度的整体贡献也是O(1*n)=O(n)

整个复杂度为O(1)+O(n)+O(n)+O(n) = O(n)。

Answer 2

您对第 3 步和第 4 步的计算不正确，因为这两个步骤都在 for 循环内。

so step 2,3 and 4 complexity will be O(n)*(O(1) +O(1))=O(n) and when clubbed with step 1 it will be O(1)+O(n)=O(n).

Answer 3

用于描述函数渐近行为的大 O 符号。基本上，它告诉您函数增长或下降的速度

例如，在分析某些算法时，可能会发现完成一个大小为 n 的问题所需的时间（或步数）由

给出

T(n) = 4 n^2 - 2 n + 2

如果我们忽略常量（这是有道理的，因为它们取决于程序运行所在的特定硬件）和增长较慢的项，我们可以说 "T(n)" 以 n^ 的顺序增长2 " 和 write:T(n) = O(n^2)

对于正式定义，假设f(x) 和g(x) 是定义在实数的某个子集上的两个函数。我们写

f(x) = O(g(x))

（或 f(x) = O(g(x)) for x -> infinity 更精确）当且仅当存在常数 N 和 C 使得

|f(x)| <= C|g(x)| for all x>N

直觉上，这意味着 f 的增长速度并不比 g

如果a是实数，我们写

f(x) = O(g(x)) for x->a

当且仅当存在常数 d > 0 和 C 使得

|f(x)| <= C|g(x)| for all x with |x-a| < d

所以你的情况是

O(n) as |f(x)| > C|g(x)|

引用自http://web.mit.edu/16.070/www/lecture/big_o.pdf

int total = 0;
for (int i = n; i < n - 1; i++) { // --> n loop
    for (int j = 0; j < n; j++) { // --> n loop
        total = total + 1; // -- 1 time 
    }
}

}

Big O Notation 给出了一个假设，当值非常大时，外循环将运行 n 次，而内循环是运行ning n 次

假设 n -> 100 比总 n^2 10000 运行次

算法的时间和 Space 复杂度 - 大 O 表示法

Time and Space Complexity of an Algorithm - Big O Notation

algorithm

big-o