Jeśli

13

Właśnie znalazłem to zdanie na stronie 6 „Komputerów i nienaruszalności” Garey i Johnsona.

Każdy algorytm, którego funkcja złożoności czasowej nie może być tak ograniczona, nazywa się algorytmem wykładniczym w czasie (chociaż należy zauważyć, że ta definicja obejmuje pewne funkcje nieliniowej złożoności czasowej, takie jak , które zwykle nie są uważane za funkcje wykładnicze).nlogn

Moje pytanie brzmi następująco:

Jeśli nie jest wielomianem ani wykładnikiem, to jak nazywa się ta funkcja? Czy to ma nazwę lub specjalne przypadki, czy nie?nlogn

Dziękuję Ci.

użytkownik777
źródło

Odpowiedzi:

12

Nie ma ustalonej terminologii dla tego typu funkcji. Czasami może się zdarzyć, że „podwykładniczy” lub „wielobiegunowy” użyty w odniesieniu do tego rodzaju zachowania.

Tom van der Zanden
źródło
7
Innym popularnym terminem jest quasipolynomial .
Yuval Filmus,
3
cn11+γ
clog1+γn
c,γ>0