Я хотел бы знать, какая сложность выполнения в худшем случае для оператора switch, если у вас есть n случаев.
Я всегда предполагал, что это O (n). Я не знаю, умеют ли компиляторы что-нибудь умное. Если ответ специфичен для реализации, я хотел бы знать следующие языки:
В худшем случае O (n). Иногда (и это зависит от языка и компилятора), он преобразуется в поиск таблицы перехода (для "приятных" переключателей, у которых нет слишком большого диапазона событий). Тогда это O (1).
Если компилятор хочет быть напуганным, я могу думать о том, как сложность может быть реализована как нечто между собой (например, выполнить бинарный поиск в случаях, для logn). Но на практике вы будете получать линейное время или постоянное время.
Большая сложность оператора switch не является действительно важным моментом. Запись Big-O относится к производительности с ростом n до бесконечности. Если у вас есть оператор switch, достаточно большой, чтобы асимптотическая производительность была проблемой, она слишком велика и должна быть реорганизована.
Помимо проблемы с читабельностью, в Java и С# я думаю, что вы скоро ударите некоторые внутренние ограничения для максимального размера одного метода.
Для относительно небольших операторов switch, которые часто вызываются, вероятно, было бы более информативно измерить фактическую производительность оператора switch для других подходов, которые вы могли бы использовать вместо этого. Это измерение может быть выполнено путем многократного выполнения операции в цикле.
Для более крупных операторов switch я бы предложил рефакторинг для использования словаря или подобной структуры данных, которая имеет приблизительно O (1) производительность, даже имеет n очень большой и не будет сталкиваться с проблемами с ограниченным размером метода.
Компиляторы С++ могут превращать операторы switch в таблицу переходов (т.е. построить массив смещений скачка, затем взять значение и использовать его в качестве индекса в таблице). Это O (1).
Компилятор С# использует аналогичный подход, за исключением того, что он может собирать хеш-таблицу.
В худшем случае может быть O (n), но, по крайней мере, для таких языков, как C/С++, Java и С#, где случаи - это константы времени компиляции, часто можно использовать (и нередко использовать) таблицу перехода получить сложность для O (1).
Я не знаю, будут ли более динамичные языки, такие как PHP или Javascript, пытаться настроить таблицы перехода или нет.
C с gcc-компилятором имеет O (1) для ограниченного диапазона (таблица перехода) или в худшем O (log N) для свободного диапазона (двоичный поиск).