一个switch语句的运行时间复杂度是多少？

Question

我想知道一个switch语句在最坏情况下的运行时间复杂度，假设你有n个case。

我一直认为它是O(n)。但我不知道编译器是否会做一些聪明的事情。如果答案与实现相关，我想了解以下语言的情况：

• Java
• C/C++
• C#
• PHP
• Javascript

- Fragsworth

---

答案不仅与语言相关，甚至不是与编译器相关的。它取决于实际的代码。一些编译器将某些开关语句转换为跳转表。 - Sven Marnach

在另一个极端，这些值可能会导致调用其他函数。例如，在 Ruby 中，使用“===”运算符来检查值，它可以执行任何操作。其中一个常见的用途是正则表达式，在某些情况下可能非常昂贵 - 因此，开关的成本取决于值本身，而不是它们的数量。 - Ken

有没有任何情况下它可能比O(n)更大（对于switch中的n个案例）？ - FrustratedWithFormsDesigner

@沮丧 哎呀，希望不是这样。 - Josh Lee

@jleedev：也许可以作为某种邪恶的反优化编译器选项...那将是一个令人讨厌的愚人节玩笑 ;) - FrustratedWithFormsDesigner

Answer 1

最坏情况下时间复杂度为O(n)。有时（这取决于语言和编译器），它会转换为跳转表查找（对于“好的”开关，其case范围不太大）。然后时间复杂度为O(1)。

如果编译器想要更加神奇，我可以想到一些方式来实现复杂度在两者之间（例如，在case中执行二分搜索，则为logn）。但是，在实际中，您将得到线性时间或常数时间。

- lijie

Answer 2

switch语句的大O复杂度并不是重点，大O符号表示当n趋近于无穷时的性能。如果你有一个足够大的switch语句，渐进性能成为问题时，它就太大了，需要进行重构。

除了可读性问题外，在Java和C#中，单个方法的最大尺寸限制可能很快就会达到。

对于调用频繁的相对较小的switch语句，更有意义的做法可能是测量该语句的实际性能，并与其他可替代方案进行比较。可以通过在循环中重复执行操作来进行此测量。

对于较大的switch语句，建议重构以使用字典或类似的数据结构，即使n非常大，其复杂度也约为O(1)，并且不会遇到有限方法大小的问题。

- Mark Byers

---

如果一个包含10个case的switch语句被频繁调用，那么尝试理解其内部工作原理是否有意义？ - Fragsworth

@Fragsworth 是的，你绝对应该尝试理解它内部的工作原理。但是Big-O只告诉你在很多情况下（例如100个以上）它有多快。Mark的观点是，除了查看其Big-O之外，还有更好的方法来分析switch语句的内部，比如编译器如何优化它以及使用其他方法（如查找表）将如何进行比较。 - Gordon Gustafson

如果答案是O(n)，那么我会知道我可以通过将更频繁的情况放在前面来进行优化；如果答案是O(1)，那么我会知道这样做没有帮助。因此，了解运行时复杂度至少能够阐明一些事情。 - Fragsworth

@Fragsworth：它可能是O(n)，但不使用文本顺序。它可能会获取值的哈希值并与常量的哈希值进行线性比较，或者可能重新排列代码以优化其他内容（例如寄存器分配或堆栈使用），破坏您的排序，或者进行许多其他操作。 - Javier

@Fragsworth: 考虑O(n)符号的另一个问题是编译器可能会对只有很少入口的switch语句进行一些巧妙的优化，但对于更多入口则使用不同（较差）的策略。然后，O(n)符号将告诉您更差策略的渐近性能，这根本不是您想知道的。您应该停止考虑大O符号，而是思考在实际数据上的实际性能。此外，当您进行微调时，应该进行分析。 - Mark Byers

Answer 3

C++编译器可以将switch语句转换为跳转表(即构造一个跳转偏移量的数组，然后将值用作索引来访问该表)。这是O(1)。

C#编译器采用类似的方法，只不过它可以组装哈希表。

- Tim Robinson

Answer 4

使用gcc编译的C语言，在范围紧密的情况下具有O(1)的时间复杂度（跳转表），在范围较宽的情况下最坏情况下为O(log N)（二分查找）。

- Smit Johnth

---

有趣 +1 但是你能提供一下来源吗？ - yO_

@yO_ 有一个网站可以打印你的 C 代码的反汇编代码，但我忘了它的名字。你可以去那里试试看。 - Smit Johnth

Answer 5

最坏情况可能是O(n)，但至少对于像C/C++、Java和C#这样的语言，其中情况是编译时常量，通常可以使用跳转表（并且经常被使用）将复杂度降低到O(1)。

我不知道更动态的语言如PHP或Javascript是否尝试设置跳转表。

- Michael Burr

---

对于 PHP，case 表达式不需要是常量；即使 expr 不是常量，switch(true) { case expr: doSomething(); } 也是有效的。如果我没记错的话。因此，像这样的东西可能不太可能使用跳转表。 - user314104