Apa nama kelas fungsi yang dijelaskan oleh O (n log n)?

40

Dalam "Big O", notasi umum memiliki nama yang sama (alih-alih mengatakan, "Oh faktor konstan"):

O (1) adalah "Constant"

O (log n) adalah "Logaritmik"

O (n) adalah "Linear"

O (n ^ 2) adalah "Kuadratik"

O (n * log n) adalah ???

Apakah hanya "n log n" atau apakah ia memiliki nama khusus seperti di atas?

terminology asymptotics GlenPeterson
sumber
4
Duplikat lintas-situs untuk referensi: Ketika berbicara, bagaimana saya bisa mengatakan bahwa urutan kompleksitas waktu suatu algoritma adalah O (N log N)?
Philip Kendall

Jawaban:

52

Ini disebut waktu linearitmik , dan merupakan kasus khusus dari kelas yang lebih umum yang dikenal sebagai kuasi linear . Seperti namanya, algoritma yang termasuk dalam kelas ini hampir berjalan dalam waktu linier; pada kenyataannya mereka memiliki kompleksitas yang lebih rendah daripada algoritma yang berjalan dalam dengan k > 1 .HAI(nk)k>1

Roukah
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Gilles 'SO- berhenti bersikap jahat'
17

linearithmic: adj.

Dari suatu algoritma, memiliki waktu berjalan yaitu O (N log N). Diciptakan sebagai portmanteau 'linier' dan 'logaritmik' dalam Algoritma Dalam C oleh Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

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

keajaiban173
sumber
Mengapa saya tidak terkejut bahwa itu berasal dari Sedge ... :)
TextGeek
11

Saya selalu mendengar O (n log n) digambarkan sebagai "log-linear" yang sepertinya benar bagi saya.

Dylan Skola
sumber
4
Yang mengatakan, satu atau dua referensi akan menyenangkan.
Raphael
7

Ini terlalu lama untuk dikomentari, jadi saya menulis jawaban. Saya tidak menambahkan ini ke jawaban pertama saya karena banyak orang sudah meningkatkan vanswer pertama saya dan saya tidak yakin mereka setuju dengan jawaban ini juga.

  • Saya tidak berpikir bahwa linearithmic adalah istilah yang mapan seperti yang dinyatakan dalam komentar atas jawaban yang diterima. Saya mencari beberapa artikel yang agak muda menggunakan istilah ini, kursus CS, dan buku lain oleh Sedgewick yang menggunakan istilah ini dan banyak kamus online.
  • Istilah quasilinear yang saya temukan dalam dua artikel:

    Kepuasan Sepenuhnya Lengkap dalam Jurnal
    Schnorr NQL CP
    dari Association for Computing Machinery,
    Vol 25. No 1, Januari 1978, pp 136-1,15

dan dalam sebuah artikel yang dikutip dalam Wikipedia yang berkaitan dengan artikel Schorr ini. Schnorr memperkenalkan kelas kompleksitas quasilinear (QL) dan quondinear nondeterministic (NQL).
Quasilinear tampaknya juga digunakan dalam teori persamaan diferensial parsial.

Secara keseluruhan, tampaknya satu atau lebih Wikipedian ingin memberikan nama untuk fungsi ini yang tidak memiliki nama yang diterima secara luas. Tetapi bahkan sekarang bagi saya tampaknya tidak ada nama yang diterima secara luas (selain itu saya pikir ini semacam manipulasi yang tidak boleh dilakukan Wikipedia). Saya pikir kita harus berhati-hati jika menggunakan Wikipedia untuk pertanyaan terminologi. Dan untuk fungsi ini bukan sumber yang memadai. Saya pikir satu-satunya nama yang diterima secara luas untuk fungsi ini adalah n log n .

keajaiban173
sumber
1
Sementara legitimasi linearitmik dan loglinear mungkin dapat diperdebatkan, saya percaya bahwa kuasi-linear adalah istilah yang mapan. Tampaknya banyak digunakan dalam makalah penelitian.
Roukah
@Roukah ya, tapi itu tidak berarti hal yang sama; quasilinear lebih umum. - Saya tidak melihat apa yang salah dengan Wikipedia menggunakan nama yang jelas, tampaknya tidak memiliki alternatif yang lebih baik, dan yang digunakan dalam sumber yang cukup terkenal, bahkan jika itu belum banyak menyebar. Bahkan saya akan mengatakan fakta bahwa itu tidak menyebar meskipun kelas kompleksitas yang sangat umum menunjukkan sudah saatnya orang mulai menggunakannya lebih banyak!
leftaroundtentang
+1 "hanya nama yang diterima secara luas untuk fungsi ini adalah n log n" - Semua jawaban lain menghibur dan memperbaiki, tetapi saya pikir Anda mungkin benar. Saya sudah berlatih mengatakan "linearitmik" selama beberapa hari sekarang dan itu masih tidak menggelinding. "En log en" mudah untuk diucapkan, mudah diingat, dan langsung dipahami oleh semua orang yang akrab dengan Big O. Saya akan memikirkannya sedikit, tetapi saya mungkin harus memindahkan penerimaan saya terhadap jawaban ini.
GlenPeterson