这两种伪算法的执行时间是否不同

Question

// -- Algorithm A
    int a = 1, b = 2;
    for (int n = 0; n < 100; n++)
    {
        int c = a + b + n;
        int d = a - b - n;
    }
// -- Algorithm B
    int a = 1, b = 2;
    for (int n = 0; n < 100; n++)
    {
        int c = a + b + n;
    }
    for (int n = 0; n < 100; n++)
    {
        int d = a - b - n;
    }

我应该尝试使用现有循环进行必要的操作吗？还是最终结果是一样的？

Answer 1

在 O（n） 表示法中，它们将是相同的。据此：

您将有一个总和：

O(n) + O(n) = O(2n)

然后乘以常量：

O(2n) = O(n)

所以最后它将是 O（n）

Answer 2

在复杂性方面，两种算法都是O（n）。即使你考虑乘法常数，你也可以说一个是 n * 2，另一个是 n + n，这是完全相同的。

但实际上，这取决于。有人可能会争辩说，由于第二个执行两倍的分支，性能可能会更差（参见这个著名的问题），但最终它取决于编译器、特定输入、操作系统等。

Answer 3

在当前的实现中

  int a = 1, b = 2;
  for (int n = 0; n < 100; n++)
  {
      int c = a + b + n;
      int d = a - b - n;
  }

你什么都不做：c和d都是本地的 vairable，它们存在仅在for循环范围内;如果优化器足够聪明，可以发现整数溢出的可能性（1 + 2 + 100和 1 - 2 - 100在[int.MinValue..int.MaxValue] ）范围内，它可以很好地消除整个循环，并向开发人员发出警告。

真实世界的例子是

 for (int n = 0; n < N; n++)
 { 
   f(n);
   g(n);
 }

对

 for (int n = 0; n < N; n++)
   f(n); 
 for (int n = 0; n < N; n++)
   g(n); 

f(n)和g(n)都没有副作用，N足够大。到目前为止一切顺利，在第一种情况下，执行时间是

 T = f(0) + g(0) + 
     f(1) + g(1) + 
     ...  
     f(N - 2) + g(N - 2) +
     f(N - 1) + g(N - 1) 

在第两种情况下

T = f(0) + f(1) + ... f(N - 2) + f(N - 1) +
    g(0) + g(1) + ... g(N - 2) + g(N - 1)  

如您所见，执行时间是相同的（不仅是O(...)）。在现实生活中，两个实现之间的差异可能很小：循环初始化和实现细节，CPU寄存器利用率等。

Answer 4

当然，第一个算法会更快，但由于复杂性只是线性增加，第二个还不错。只要你不去二次，两者都很好，

但是如果你最终写了n个这样的循环，那么你就有n^2的复杂性，这很糟糕