switch ... case a if ... else ....

Przecież napisałem wszystko w pseudokodzie...
Dobrze, napisałeś że umiesz assembler.
Tak wygląda typowy switch. Żadne wyszukiwanie logarytmiczne...
Można się o tym przekonać np. czytając kod wynikowy po kompilacji (wynik zależny od flag optymalizacyjnych, optymalizacja na rozmiar z małej ilości danych zrobi if..else if itd...).

To była ilość dodatkowych porównań, które byłyby potrzebne w switchu dla naprawdę rozstrzelonych danych, tak mała _średnia_ liczba porównań oznacza praktycznie stałą złożoność dla każdych danych.
Nieprawda, taki mov/movzw/movsw/neg/not/nop/add/sub/test/and/or/xor/cmp/dec/inc to 0.5 cykla (zależnie od modelu procesora).
Jeden argument jako pobranie wartości z adresu zazwyczaj dodaje jeden cykl.
fxch/fdecstp/fincstp/fldz zajmują... 0 cykli.

Dodatkowo nawet kilkanaście instrukcji jest wykonywane jednocześnie... ;)

Ale to tak btw...

http://www.iaii.we.po.opole.pl/dmdocuments/dyplomy/Arch_komp/cwicz1.html

Twoje rozumowanie sugeruje, iż wykonanie instrukcji fxch 10^1000 razy zajmie 0 milisekund :) co jest bzdurą :)

Zgodnie z tym co manfred mówi, switch ma złożoność liniową O(n), a nie jak można było przypuszczać logarytmiczną O(log(n)). Stałej złożoności nie uzyskasz. Zapewne za kilka lat switch będzie miał złożoność O(log(n)), jeśli ktoś tam z tych programistów od kompilatora 'zauważy', że można to zoptymalizować.

@manfred: A wygeneruj wartości po kolei. I co widzisz? No właśnie.
Gcc jest tutaj prosty:
(definicja gęstości zależy od flag optymalizacyjnych)
Visual C++ ma aż 5 trybów: jedna tablica, zwykłe if..else, wyszukiwanie binarne, wyszukiwanie binarne dla rozrzuconych wartości a później switche (kilka ciasnych grup), jeden switch a później porównania/switch dla reszty (to co napisałem).
Ostatnie jest najbardziej uniwersalne.

I jaki z tego wniosek?... Switch zawsze będzie albo szybszy, albo taki sam jak if..else. Niezależnie od kompilatora. Czyli dokładnie to co napisałem.
Złożoność jest stała. Tylko czasami stała złożoność jest wolniejsza (przez dużą tablicę) od porównań - i kompilator wybiera tą drugą. To takie trudne?

@Piotr Szawdyński: Nie, bo załadowanie pamięci z instrukcjami trochę zajmie. Dekodowanie też.
Strona, którą podałeś, ma czasy dla pentium1. Poczytaj "Intel Architecture Optimization Reference Manual".
fxch/fincstp/fdecstp nie są w ogóle wykonywane, są tylko brane pod uwagę przez dekoder.
fxch akurat zajmuje 0 cykli ale może być wykonany tylko raz na cykl (to znaczy że nie zabiera cykli innym instrukcjom), pozostałe dwie już bez ograniczeń.

Dobrze wiem, że są instrukcje, które można wykonać dodatkowo w trakcie życia jednego cyklu, jednak jak już napisałem tak czy siak musi istnieć cykl w którym instrukcja się wykona. Innymi słowy wszystkie polecenia, które podałeś potrzebują minimum jednego cyklu, żeby mogły zaistnieć. To, że dwie instrukcje potrafią się wykonać w jednym cyklu nie oznacza, że taka sytuacja będzie miała miejsce. Przykład już Ci podałem wystarczająco dobitnie 10^1000 ta sama instrukcja pod rząd.

/edit:
Ty zakładasz, że zawsze uzyskujesz optymistyczną złożoność, co w Twoim rozumowaniu oznacza jednoznacznie, że dla Ciebie QuickSort ma złożoność O(n). Takie rozumowanie jest błędne, jednak jeśli Ty tego nie widzisz to nie wprowadzaj chociaż innych w błąd.

Akurat odwrotnie, im więcej wartości tym częściej będzie tablica.
Wyszukiwanie binarne po wartościach jest realizowane przez zwykły if..else if.
A teraz, po polsku nie rozumiesz, to może matematycznie zrozumiesz:
n - ilość warunków
T(algorytm) - czas wykonania (ilość pamięci, instrukcji, optymalne wykorzystanie cache)
jeśli T(switch O(lg n)) < T(switch O(1))
to kompilator wygeneruje implementację z porównaniami, bo tak jest szybciej.
Z tego wynika że switch ma zawsze złożoność stałą i zawsze jest albo lepszy, albo taki sam jak ręcznie napisane ify.

Tak samo jak quicksort - zawsze O(n lg n). Jeśli podstawowa implementacja degeneruje się do n^2 (albo jest po prostu za wolny) następuje przełączanie na algorytm heapsort (albo inny).
Już jaśniej napisać nie można, jesli ciągle nie rozumiesz, nic na to nie poradzę. Dlatego z mojej strony eot.

Czas wykonania instrukcji to czas wykonania tej jednej instrukcji, nie załadowania pamięci do cache a później do dekodera - bo tego nie mierzy się w cyklach, tylko w ns/ms.
Jeśli będzie ta sama instrukcja pod rząd, procesor nie wykona nic. Cykl będzie pusty.

Sam sprawdź, intel podaje, że instrukcja zajmuje zawsze 0 cykli.

No to zrobię podsumowanie:
1) ja twierdziłem, że złożoność pesymistyczna switch'a jest O(log(n)). Po testach, które przeprowadził manfred okazało się, że o dziwo złożoność switcha jest O(n) - jest na to namacalny dowód.
2) manfred - twierdzi, że złożoność pesymistyczna switch'a jest liniowa, czyli O(n). Wykonał do tego testy, przedstawił argumenty i poparł to de'facto dowodami.
3) pompom - twierdzi, że złożoność pesymistyczna switch'a jest zawsze stała O(1), na co przytaczał różne argumenty.

Konkludując wątek - myślę, że prawda może leżeć po środku, czyli dla wyboru wartości, która nie istnieje w switch'u:
1) Optymistyczna wersja: złożoność switch'a jest O(1), gdy będą ustawione flagi optymalizacyjne (Visual C++ 2005) i wartości w switch'u nie będą przypadkowe i będą one blisko siebie.
2) Pesymistyczna wersja: złożoność switch'a jest O(n), czyli jest zamieniana de'facto na if...else. Wersja ta została potwierdzona przez manfred'a na kompilatorze GCC jak i na Visual C++ 2008.
3) To co wynika ze zdrowego rozsądku: złożoność switcha w najgorszym przypadku powinna być O(log(n)) - czyli zbudowane zrównoważone drzewo binarne. Okazało się jednak, że ten przypadek nie zaszedł nigdy w praktyce.

Na koniec dodam, że w algorytmach wnętrze pętli przyjmuje się, że ma stałą złożoność O(1) chyba, że występują tam jawnie pętle. Tak więc złożoność obliczeniowa switch'a nie ma istotnego znaczenia z praktycznego punktu widzenia, tj. z punktu widzenia złożoności obliczeniowych algorytmów.

podczas gdy switch - zawsze stałą

Tja, dobre :D. Wiesz, że dzwoni, ale nie wiesz w którym kościele. Switch ma złożoność stałą w nielicznych przypadkach, kiedy wartości skoków są blisko siebie, w przeciwnym razie jest logarytmiczna (wyszukiwanie binarne) / liniowa (przerabiany na if..else if..else). A czytelności to mu zarzucić nie można.