Złożoność wykładnicza algorytmu

Witam. Mam pytanie o złożoność wykładniczą.

Przykładowo złożoność logarytmiczna jest wtedy gdy mamy zbiór i aby dojść do wyniku dzielimy zbiór na mniejsze części z każdą iteracją i dochodzimy do wyniku np. dziel i zwyciężaj.

Złożoność liniowa jest wtedy gdy z danego zbioru sprawdzamy każdy element w zbiorze.

A jak to wygląda ze złożonością wykładniczą ? Tak obrazowo przedstawiając jak ja to zrobiłem dla liniowej i logarytmicznej ?

Jeszcze jedna wątpliwość w kwestii złożoności n!, bo z tego co rozumiem to taka złożoność to inaczej każdy z każdym, czyli iloczyn kartezjański aka permutacje bez powtórzeń, tak ?

Problem 1:
Mamy iloczyn dwóch liczb pierwszych podobnego rozmiaru, np n cyfr dziesiętnych. Szukasz tych liczb najprostszą pętlą. Oczekiwana liczba dzieleń to c * 10^n, czyli wykładnicza.

Problem 2:
Mamy wektor liczb i chcemy go uporządkować. W tym celu w pętli odpalamy next_permutation, aż sekwencja będzie posortowana, czyli inaczej mówiąc sprawdzamy wszystkie permutacje po kolei.

@BOBIK1 chcesz prosty przykład na wykładniczą? Gra connect the walls w przypadku ogólnym jest 2^n.
http://home.agh.edu.pl/~faliszew/toizo/ tutaj masz krótki opis problemu.
Ogólnie chodzi o to że stawiasz na planszy albo / albo
Dla każdego pola masz więc 2 możliwości. Żeby ułożyć całą planszę mógłbyś na przykład robić taką rekurencję:

• wstaw w pierwsze wolne pole / i jeśli jest to poprawny ruch to przejdź do następnego
• jeśli nie można wstawić / to wstaw \ i jeśli jest to poprawny ruch to przejdź do następnego
• jeśli ani / ani \ nie są poprawne to cofnij się o jeden poziom
  W efekcie uzyskujesz pesymistycznie O(2^n)

liczenie n-tej liczby ciągu fibonacciego, można wykonać praktycznie w każdej złożoności od wykładniczej (rekurencyjnie), przez liniową do logarytmicznej (podnoszenie macierzy do potegi)

Bardzo łatwo można zauważyć jak może działać algorytm o złożoności wykładniczej w algorytmie rozwiązywania problemu wież hanoi.

Złożoność tego algorytmu to 2^n - 1 i przeniesienie n - tego krążka wymaga tyle ruchów ile przeniesienie (n - 1) + (n - 2)+...+ 2 + 1 krążków plus ruch, który wykonujemy przenosząc ten krążek, czyli jeszcze dodajemy 1, tyle że aby przenieść n - ty krążek, to musisz wcześniej przenieść n - 1 krążków (aby je przenieść musimy wykonać o 1 ruch mniej niż przy przeniesieniu n - tego), w analogiczny sposób, co daje łącznie złożoność wykładniczą.