什么是switch语句的运行复杂性？ [英] What is the runtime complexity of a switch statement?

问题描述

我想知道什么是switch语句的最坏情况下的运行时间复杂度，假设你的 N 的情况下。

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）。但在实践中，你会得到eiher线性的时间或一定时间。

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屋！