switch 语句的运行时复杂度是多少? [英] What is the runtime complexity of a switch statement?

问题描述

假设您有 n 个案例，我想知道 switch 语句的最坏情况运行时复杂度是多少.

I'd like to know what the worst-case runtime complexity of a switch statement is, assuming you have n cases.

我一直认为它是 O(n).不过，我不知道编译器是否会做任何聪明的事情.如果答案是特定于实现的，我想知道以下语言:

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

推荐答案

最坏的情况是 O(n).有时(这取决于语言和编译器)，它转换为跳转表查找(对于没有太大大小写范围的好"开关).然后就是 O(1).

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).

如果编译器想要时髦，我可以想办法将复杂性实现为介于两者之间的任何东西(例如，对案例执行二进制搜索，对于 logn).但在实践中，您将获得线性时间或常数时间.

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 语句的运行时复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！