Mówiąc, jak mogę powiedzieć, że porządek złożoności czasowej algorytmu to O (N log N)?

22

Jakiego terminu mogę użyć do opisania czegoś o złożoności O (N log N)?

Na przykład:

  • O (1): Stała

  • O (log N): Logarytmiczny

  • O (N): liniowy

  • O (N log N): ??????

  • O (N 2 ): Kwadratowy

  • O (N 3 ): Sześcienny

algorithms algorithm-analysis big-o matiascelasco
źródło
5
Często używam tutaj szerokiego terminu „quasi-liniowy”, oznaczającego O(n · f(n))gdzie f(n) << n. Ale to pasuje również do rzeczy takich jak O(n · log log n)i O(n α(n))gdzie α(n)jest odwrotność funkcji Ackermanna.
Bakuriu
en.wikipedia.org/wiki/…
Ry-
34
„Oh enn log enn” jest prawdopodobnie wystarczająco dobre.
user253751,
Duplikat między witrynami: Jak nazywa się klasa funkcji opisanych przez O (n log n)?
martin

Odpowiedzi:

60

„N log N” jest tak dobry, jak to tylko możliwe, i powinien być dobrze zrozumiany przez profesjonalnych programistów. Nie można oczekiwać, że będzie jedno słowo opisujące każdą istniejącą klasę złożoności.

Philip Kendall
źródło
6
„Nie mogę oczekiwać, że będzie jedno słowo opisujące każdą klasę złożoności” - na pewno nie. Ale 𝓞 ( n ⋅ log n ) jest tak ważną klasą, że zasługuje na swoją własną nazwę, IMO; i jak powiedział Steve Jessop, linearithmic jest już dość powszechny.
leftaroundabout
@leftaroundabout Rzeczywiście jest dość powszechne, że można argumentować, że zasługuje na nazwę. Ale „n log n” jest wystarczająco krótkie, aby wymówić (tylko trzy sylaby), że działa dobrze jako nazwa. Dla porównania „Logarytmiczny” to cztery sylaby. Bardziej interesujące jest przejście do zewnętrznych algorytmów, w których większość algorytmów „n log n” ma złożoność $ N log_B (N / B) $, z pewnością byłaby to klasa złożoności warta krótszej nazwy.
kasperd
10
Jako student magistra informatyki słyszałem „enn log enn” na studiach. Nigdy nie słyszałem „linearithmic” i na początku nie rozumiem, co to znaczy.
Kevin - Przywróć Monikę
@Kevin: Logarytmika to cztery sylaby, ale „log-enn” to tylko dwie. Podobnie O (N ^ 2) jest „enn-kwadrat”, a nie „kwadratowy”. Przypuszczam, że „sześcienny” ma mniej fonemów niż „enn-cubed”, ale myślę, że ten drugi termin byłby jeszcze bardziej powszechny.
supercat
51

Istnieje żargonowe określenie liniowo- matematyczne, które właśnie to oznacza.

Nie wierzę, że jest to powszechnie rozumiane przez wszystkich programistów, więc jeśli nie będziesz ostrożny, ukryje więcej, niż informuje. Osobiście zwykle go nie używam, a gdybym to zrobił, prawdopodobnie zdefiniowałbym go przy pierwszym użyciu, na przykład „w tym artykule rozważane są O(N log N)algorytmy linearithmic ( )”.

Steve Jessop
źródło
11
Nigdy nawet nie wiedziałem, że istnieje!
David mówi Przywróć Monikę
12

Czasami nazywa się to „loglinear”, chociaż to słowo w rzeczywistości oznacza coś innego. Pozostałbym jednak przy „N log N”, jak sugeruje odpowiedź @ Philipa .

Jörg W Mittag
źródło
1
Jakie jest alternatywne znaczenie log-linear? Gdybym chciał nazwy innej niż „N log N”, użyłbym log-liniowy.
Jonathan Leffler,
2
@JathanathanLeffler: Zakładam, że en.wikipedia.org/wiki/Log-linear_analysis czasami jest pisane bez myślnika. Oczywiście przy odpowiedniej przestrzeni nazw możesz z powodzeniem używać tego samego słowa dla klasy złożoności.
Steve Jessop,
@ SteveJessop: Z pewnością to właśnie przyszło przez wyszukiwarkę Google. Nie jestem pewien, czy chcę zaakceptować kombinację Google / Wikipedia jako wiarygodną, ​​chociaż nie mam wątpliwości, że analiza log-liniowa jest taka, jak opisano.
Jonathan Leffler,
1
@JonathanLeffler: może również oznaczać coś, co nazwałbym działką log-log lub log-lin (lub, ponieważ jestem leniwy, tak naprawdę często nazywałbym je działką logarytmiczną inną niż log-log). Możemy zapytać, jakie alternatywne znaczenie ma ta odpowiedź :-)
Steve Jessop,
2

Ponieważ czynnik log nrośnie powoli, opis jakościowy dla „ O(n log n)byłoby liniowy”. W zależności od odbiorców klasa O(n log n)algorytmów może być dobrze znana, jak na przykład w przypadku szybkiego sortowania nelementów według porównań.

matematyka
źródło