algorithm - 算法的时间和空间复杂度 - 大 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;
}

1. 如果您分配一个变量或集合，在这种情况下，复杂性根据大 O 的规则确定为 O (1)。所以第一阶段将是O(1) - 这意味着无论输入大小是多少，程序都将执行相同的时间和内存空间。

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

3. 在此步骤中，我们定义了一个变量来确定条件检查(请参阅编码中的步骤 3)。在这种情况下，根据大 O 规则，复杂度为 O(1)。

4. 同理，第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

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

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

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

如果我们忽略常量(这是有道理的，因为它们取决于程序运行的特定硬件)和增长较慢的项，我们可以说“T(n)”以 n^2 的顺序增长并写成: 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 次，而内循环将运行 n 次

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