switch语句的运行时复杂性是多少？

Question

假设您有n个案例,我想知道switch语句的最坏情况运行时复杂性是什么.

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

Answer 1

最糟糕的是O(n).有时(这是语言和编译器相关),它转换为跳转表查找(对于没有太大的案例范围的"漂亮"开关).那就是O(1).

如果编译器想要时髦,我可以想到可以将复杂性实现为介于两者之间的任何方式(例如,对案例执行二进制搜索,对于logn).但在实践中,你将获得更长的线性时间或恒定时间.

Answer 2

switch语句的大O复杂性并不是真正重要的一点.Big-O表示法指的是随着n向无穷大增加的表现.如果你的switch语句足够大,渐近性能是一个问题,那么它太大了,应该重构.

除了可读性问题之外,在Java和C#中,我认为您很快就会对单个方法的最大大小达到一些内部限制.

对于经常调用的相对较小的switch语句,可能更有助于衡量switch语句的实际性能,而不是可以使用的其他方法.可以通过在循环中重复执行该操作来进行该测量.

对于较大的switch语句,我建议重构使用具有大约O(1)性能的字典或类似数据结构,即使n非常大,也不会遇到有限方法大小的问题.

如果足够频繁地调用10个案例的switch语句,那么尝试理解它在内部如何工作是没有意义的吗？ (10认同)
如果答案是O(n),那么我会知道我可以通过先放置更频繁的案例来优化; 如果答案是O(1)那么我就知道这没有用.因此,了解运行时复杂性至少可以阐明一些事情. (6认同)
@Fragsworth:它可能是O(n)但不使用文本顺序.它可能需要值的哈希值并与常量的哈希值线性比较,或者它可能会重新排序代码以优化其他一些东西(如寄存器分配或堆栈使用),破坏您的订购或许多其他事情 (5认同)
@Fragsworth是的,你一定要试着去理解它是如何在内部运作的.但Big-O告诉你的唯一的事情就是它有多快,例如100+.Mark的观点是,有更好的方法可以分析switch语句的内部结构,而无需查看它的big-O,比如编译器如何优化它以及如何与使用其他方法(如查找表)进行比较. (4认同)
@Fragsworth:考虑O(n)表示法的另一个问题是编译器可能对具有很少条目的switch语句进行一些聪明的优化,但对更多条目使用不同(更差)的策略.然后O(n)符号将告诉你**更差**策略的渐近表现,这根本不是你想要知道的.你应该停止考虑big-O而是考虑实际数据的**实际**性能.此外,当你进行这样的微优化时,你应该**描述**. (2认同)

Answer 3

C++编译器可以将switch语句转换为跳转表(即构造一个跳转偏移数组,然后获取该值并将其用作表中的索引).这是O(1).

C#编译器使用类似的方法,除了它可以组装哈希表.

Answer 4

使用gcc编译器的C对于狭窄范围（跳转表）具有O（1）或对于宽松范围具有最差的O（log N）（二进制搜索）。

Answer 5

最坏的情况可能是 O(n)，但至少对于像 C/C++、Java 和 C# 这样的语言，这些情况是编译时常量，通常可以使用跳转表（而且经常使用）来获得复杂性为 O(1)。

我不知道像 PHP 或 Javascript 这样的动态语言是否会尝试设置跳转表。