c# - c# if else 语句的时间复杂度

Question

从处理/时间复杂度的角度来看，以下两者中哪一个更有效 - 抱歉，我只是想了解一下时间复杂度以及对计算机处理时间的潜在影响:

选项 1

if (condition1) {
  function1();
  function2();
} 
else {
  function3();
}

选项 2

if (condition1) {
  function1();
}
else {
  function3();
}

if (condition1) {
  function2();
}
else {
  function3();
}

假设 function1() 和 function2() 都是 O(N)，我认为选项 1 和选项 2 的时间复杂度都是 O(N)。但是，如果我们可以测量这两个选项在同一台计算机上运行的速度，选项 1 会更快还是差异很小？

谢谢!

Answer 1

if 的时间复杂度是常数，即 O(1)。两个 if 的复杂性也是如此。

如果函数的复杂度为 O(N)，则整体复杂度为 O(N)。

---

时间复杂度不是衡量效率的标准，而是衡量可扩展性的标准。它没有说明算法需要多少资源(CPU 周期、内存等)，而是说明当输入大小加倍时它将占用多少资源。

请先将头围在上面；时间复杂度讨论的问题与单个操作的成本不同。别把它搞混了。

---

至于实际性能差异:

选项 2 将调用 function3() 两次，因此比较取决于此。

如果函数进行任何显着的处理，则两个选项之间的差异将可以忽略不计，它将由函数的波动主导。

通常，如果没有上下文，就无法讨论简单操作(如 if)的性能。

对于条件跳转，首要问题是:它们的可预测性如何？
即他们大部分时间都使用同一个分支吗？两次可预测的条件跳转比一次预测错误的条件跳转要好得多。