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

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's.

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

---

时间复杂度不是衡量效率，而是衡量可扩展性。它并不是说一个算法需要多少资源（CPU周期、内存......），而是说一个算法需要多少资源。更多 当你把输入大小增加一倍时，它就会抓取。

请先搞清楚这一点，时间复杂度讨论的问题和单个操作的成本不同。不要把这两者混为一谈。

---

至于实际的性能差异。

方案二会调用 function3() 两次，所以比较取决于此。

如果函数做任何siginificant的处理，两个选项之间的差异将ne可以忽略不计，它将被函数的波动所主导。

一般情况下，琐碎操作的性能（如an if)不能脱离背景来讨论。

对于条件跳跃，首要的问题是：它们的可预测性有多高？ 即它们是否在大多数时间都走同一个分支？两个可预测性好的条件跳转比一个预测性差的条件跳转要好得多。

Answer 2

方案 2 不可能比方案 1 更快，因为严格来说，它至少要做同样多的工作来计算要调用哪些函数。还请注意，当条件1为假时，方案2的结果是两次调用function3，所以在这种情况下，它要做两倍的工作（假设函数所做的工作比所示的片段要多得多，后者只是找出要调用的函数）。

在实践中，这些可能会有完全相同的性能（忽略对function3的重复调用），因为一个优化的编译器会认识到为选项2渲染二进制代码的机会，它看起来更像你对选项1的期望。在没有优化的情况下，你会看到多了一个条件分支，我认为在合理的假设下，这可以被安全地描述为一个最小的额外开销。现在，如果这是在一个紧密的循环中，优化被关闭，并且条件1几乎总是假的，那么也许你会看到更多的问题（由于许多遗漏的分支预测打断了管道），但我对此表示怀疑。