Какова сложность во время выполнения оператора switch?

Question

Я хотел бы знать, какова сложность выполнения оператора switch в худшем случае, если у вас n случаев.

Я всегда предполагал, что это было O (n) . Я не знаю, делают ли компиляторы что-нибудь умное. Если ответ зависит от реализации, я хотел бы знать для следующих языков:

• Java
• C / C ++
• C #
• PHP
• Javascript

Answer 1

В худшем случае O (n). Иногда (и это зависит от языка и компилятора), это приводит к поиску таблицы переходов (для «хороших» переключателей, у которых не слишком большой диапазон регистра). Тогда это O (1).

Если компилятор хочет быть шутливым, я могу придумать, как сложность может быть реализована, чтобы быть чем-то промежуточным (например, выполнить бинарный поиск в случаях для logn). Но на практике вы получите линейное или постоянное время.

Answer 2

Сложность big-O оператора switch не очень важна. Обозначение Big-O относится к производительности при увеличении n к бесконечности. Если у вас достаточно большой аргумент switch, что асимптотическая производительность является проблемой, тогда она слишком велика и должна быть реорганизована.

Помимо проблем с читабельностью, в Java и C # я думаю, что вскоре вы достигнете некоторых внутренних ограничений на максимальный размер одного метода.

Для относительно небольших операторов switch, которые часто вызываются, вероятно, было бы более информативным измерить фактическую производительность оператора switch с другими подходами, которые вы могли бы использовать вместо этого. Это измерение может быть выполнено путем многократного выполнения операции в цикле.

Для более крупных операторов switch я бы предложил использовать рефакторинг, чтобы использовать словарь или аналогичную структуру данных, которая имеет примерно O (1) производительность, даже если n становится очень большим, и это не приведет к проблемам с ограниченным размером метода. *

Answer 3

Компиляторы C ++ могут превратить операторы switch в таблицу переходов (т.е. создать массив смещений переходов, затем взять значение и использовать его в качестве индекса в таблице). Это O (1).

Компилятор C # использует аналогичный подход, за исключением того, что он может собирать хеш-таблицу.

Answer 4

C с компилятором gcc имеет O (1) для узкого диапазона (таблица переходов) или в худшем случае O (log N) для свободного диапазона (двоичный поиск).

Answer 5

Худшим случаем может быть O (n), но по крайней мере для таких языков, как C / C ++, Java и C #, где случаи являются константами времени компиляции, таблица переходов часто может использоваться (и довольно часто используется) для получить сложность O (1).

Я не знаю, пытаются ли более динамические языки, такие как PHP или Javascript, создавать таблицы переходов или нет.