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

40

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?

terminology asymptotics GlenPeterson
źródło
4
Duplikat krzyżowy dla odniesienia: Jak mówiąc, jak mogę powiedzieć, że porządek złożoności czasowej algorytmu to O (N log N)?
Philip Kendall

Odpowiedzi:

52

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(nk)k>1

Roukah
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Gilles „SO- przestań być zły”
17

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

cud173
źródło
Dlaczego nie dziwię się, że pochodzi od Sedge ... :)
TextGeek
11

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

Dylan Skola
źródło
4
To powiedziawszy, odniesienie lub dwa byłoby miło.
Raphael
7

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.

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 .

cud173
źródło
1
Chociaż zasadność linearithmic i loglinear może być dyskusyjna, wierzę, że quasi-liniowy jest ugruntowane termin. Wydaje się, że jest szeroko stosowany w pracach badawczych.
Roukah
@Roukah tak, ale to nie znaczy całkiem tego samego; quasilinear jest bardziej ogólny. - Nie rozumiem, co jest złego w Wikipedii, która używa nazwy, która jest jednoznaczna, wydaje się, że nie ma lepszej alternatywy i jest używana w dość znanym źródle, nawet jeśli nie ma dużego zasięgu. Powiedziałbym, że fakt, że nie rozprzestrzenił się, mimo że jest niezwykle powszechną klasą złożoności, sugeruje, że nadszedł czas, aby ludzie zaczęli go więcej używać!
leftaroundabout
+1 „tylko powszechnie akceptowana nazwa tej funkcji to n log n” - Wszystkie pozostałe odpowiedzi są zabawne i pouczające, ale myślę, że masz rację. Ćwiczę mówienie „linearithmic” już od kilku dni i nadal nie spływa ono z języka. „En log en” jest łatwe do powiedzenia, łatwe do zapamiętania i natychmiast zrozumiane przez wszystkich znających Big O. Pomyślę o tym trochę, ale być może będę musiał przenieść moją akceptację na tę odpowiedź.
GlenPeterson