我想知道一个switch语句在最坏情况下的运行时间复杂度,假设你有n个case。
我一直认为它是O(n)。但我不知道编译器是否会做一些聪明的事情。如果答案与实现相关,我想了解以下语言的情况:
- Java
- C/C++
- C#
- PHP
- Javascript
我想知道一个switch语句在最坏情况下的运行时间复杂度,假设你有n个case。
我一直认为它是O(n)。但我不知道编译器是否会做一些聪明的事情。如果答案与实现相关,我想了解以下语言的情况:
最坏情况下时间复杂度为O(n)。有时(这取决于语言和编译器),它会转换为跳转表查找(对于“好的”开关,其case范围不太大)。然后时间复杂度为O(1)。
如果编译器想要更加神奇,我可以想到一些方式来实现复杂度在两者之间(例如,在case中执行二分搜索,则为logn)。但是,在实际中,您将得到线性时间或常数时间。
switch语句的大O复杂度并不是重点,大O符号表示当n趋近于无穷时的性能。如果你有一个足够大的switch语句,渐进性能成为问题时,它就太大了,需要进行重构。
除了可读性问题外,在Java和C#中,单个方法的最大尺寸限制可能很快就会达到。
对于调用频繁的相对较小的switch语句,更有意义的做法可能是测量该语句的实际性能,并与其他可替代方案进行比较。可以通过在循环中重复执行操作来进行此测量。
对于较大的switch语句,建议重构以使用字典或类似的数据结构,即使n非常大,其复杂度也约为O(1),并且不会遇到有限方法大小的问题。
C++编译器可以将switch语句转换为跳转表(即构造一个跳转偏移量的数组,然后将值用作索引来访问该表)。这是O(1)。
C#编译器采用类似的方法,只不过它可以组装哈希表。
使用gcc编译的C语言,在范围紧密的情况下具有O(1)的时间复杂度(跳转表),在范围较宽的情况下最坏情况下为O(log N)(二分查找)。
switch(true) { case expr: doSomething(); }
也是有效的。如果我没记错的话。因此,像这样的东西可能不太可能使用跳转表。 - user314104