switch 语句的运行时复杂度是多少？
我想知道 switch 语句最坏情况的运行时复杂度是多少，假设您有 n 种情况。
我一直认为它是O(n)。不过，我不知道编译器是否做了什么聪明的事情。如果答案是特定于实现的，我想知道以下语言：
- Java
- C/C++
- C#
- PHP
- Javascript
I'd like to know what the worst-case runtime complexity of a switch statement is, assuming you have n cases.
I always assumed it was O(n). I don't know if compilers do anything clever, though. If the answer is implementation-specific, I'd like to know for the following languages:
- Java
- C/C++
- C#
- PHP
- Javascript
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
最坏的情况是 O(n)。有时（这取决于语言和编译器），它会转换为跳转表查找（对于没有太大大小写范围的“好”开关）。那么那就是O(1)。
如果编译器想要变得时髦，我可以想办法将复杂性实现为介于两者之间的任何值（例如，对 logn 的情况执行二进制搜索）。但在实践中，您将获得线性时间或恒定时间。
It is at worst O(n). Sometimes (and this is language and compiler dependent), it translates to a jump table lookup (for "nice" switches that don't have too large a case range). Then that is O(1).
If the compiler wants to be funky, I can think of ways that the complexity can be implemented to be anything in between (e.g. perform binary search on the cases, for logn). But in practice, you're going to get eiher linear time or constant time.
switch 语句的大 O 复杂性并不是真正的重点。 Big-O 表示法是指 n 向无穷大增加时的性能。如果您的 switch 语句足够大，以至于渐近性能成为问题，那么它就太大了，应该重构。
除了可读性问题之外，在 Java 和 C# 中，我认为您很快就会遇到单个方法最大大小的一些内部限制。
对于经常调用的相对较小的 switch 语句，根据您可以使用的其他方法来衡量 switch 语句的实际性能可能会提供更多信息。该测量可以通过在循环中重复执行该操作来进行。
对于较大的 switch 语句，我建议重构为使用具有大约 O(1) 性能的字典或类似数据结构，即使 n 变得非常大，也不会遇到方法大小有限的问题。
The big-O complexity of a switch statement is not really the important point. Big-O notation refers to the performance as n increases towards infinity. If you have a switch statement big enough that the asymptotic performance is an issue then it is too big and should be refactored.
Apart from the readability issue, in Java and C# I think you would soon hit some internal limits for the maximum size of a single method.
For relatively small switch statements that are called often it would probably be more informative to measure the actual performance of the switch statement against other approaches that you could use instead. This measurement could be made by repeatedly performing the operation in a loop.
For larger switch statements I'd suggest refactoring to use a dictionary or similar data structure that has approximately O(1) performance even has n gets very large and it won't run into problems with the limited method size.
C++ 编译器可以将 switch 语句转换为跳转表（即构造一个跳转偏移量数组，然后获取该值并将其用作该表的索引）。这是 O(1)。
C# 编译器使用类似的方法，只不过它可以组装哈希表。
C++ compilers can turn switch statements into a jump table (i.e. construct an array of jump offsets, then take the value and use it as an index into the table). This is O(1).
The C# compiler uses a similar approach, except that it can assemble a hash table.
使用 gcc 编译器的 C 对于严格范围（跳转表）具有 O(1)，对于宽松范围（二分搜索）最坏情况下具有 O(log N)。
C with gcc compiler has O(1) for tight range (jump table) or at worst O(log N) for loose range (binary search).
最坏的情况可能是 O(n)，但至少对于像 C/C++、Java 和 C# 这样的语言，这些情况是编译时常量，通常可以使用跳转表（而且经常使用）来获得复杂性为 O(1)。
我不知道像 PHP 或 Javascript 这样的动态语言是否会尝试设置跳转表。
The worst case might be O(n), but at least for languages like C/C++, Java and C# where the cases are compile-time constants, a jump table can often be used (and quite often is used) to get the complexity to O(1).
I don't know if the more dynamic languages like PHP or Javascript try to set up jump tables or not.