Jak nazywa się klasa funkcji opisanych przez O (n log n)?

W „Big O” popularne notacje mają wspólne nazwy (zamiast mówić „Och jakiegoś stałego czynnika”):

O (1) to „Stała”

O (log n) to „Logarytmiczny”

O (n) oznacza „liniowy”

O (n ^ 2) jest „kwadratowe”

O (n * log n) to ???

Czy to po prostu „n log n”, czy ma specjalną nazwę jak wyżej?

Nazywa się to czasem liniowo-rytmicznym i jest szczególnym przypadkiem bardziej ogólnej klasy znanej jako quasi-liniowa . Jak sama nazwa wskazuje, algorytmy należące do tej klasy prawie działają w czasie liniowym; w rzeczywistości mają mniejszą złożoność niż algorytmy działające w przy .$O(n^k)$$k > 1$

linearithmic: przym.

Algorytmu, którego czas działania wynosi O (N log N). Stworzony jako portmanteau „liniowego” i „logarytmicznego” w Algorytmach C autorstwa Roberta Sedgewicka (Addison-Wesley 1990, ISBN 0-201-51425-7).

http://catb.org/jargon/html/L/linearithmic.html

Zawsze słyszałem O (n log n) opisywane jako „log-liniowy”, co wydaje mi się właściwe.

To było za długie na komentarz, więc napisałem odpowiedź. Nie dodałem tego do mojej pierwszej odpowiedzi, ponieważ wiele osób już głosowało za moją pierwszą odpowiedzią i nie jestem pewien, czy zgadzają się z tą odpowiedzią.

• Nie sądzę, aby linearithmic to dobrze ustalony termin, jak stwierdzono w komentarzu do przyjętej odpowiedzi. Przeszukałem kilka dość młodych artykułów, używając tego terminu, kursu CS oraz innej książki Sedgewick, która używa tego terminu i wielu słowników internetowych.
• Termin quasilinear znalazłem w dwóch artykułach:

  Zgodność jest quasilinear pełna w NQL
  CP Schnorr
  Journal of the Association for Computing Machinery,
  tom 25. nr 1, styczeń 1978, s. 136–1,15

oraz w artykule cytowanym w Wikipedii, który dotyczy tego artykułu Schorra. Schnorr wprowadza klasy złożoności quasilinear (QL) i niedeterministyczny quasilinear (NQL).
Quasilinear wydaje się być również stosowany w teorii równań różniczkowych cząstkowych.

• Termin loglinear jest również używany w innym kontekście

Podsumowując, wydaje się, że jeden lub więcej wikipedystów chciało podać nazwy dla tej funkcji, która nie ma powszechnie akceptowanej nazwy. Ale nawet teraz wydaje mi się, że żadna z nazw nie jest powszechnie akceptowana (poza tym myślę, że jest to rodzaj manipulacji, której Wikipedia nie powinna robić). Myślę, że trzeba być ostrożnym, jeśli używa się Wikipedii do pytań terminologicznych. I dla tej funkcji nie jest to wystarczające źródło. Myślę, że jedyną powszechnie akceptowaną nazwą tej funkcji jest n log n .