Ketika berbicara, bagaimana saya bisa mengatakan bahwa urutan kompleksitas waktu suatu algoritma adalah O (N log N)?

22

Istilah apa yang dapat saya gunakan untuk menggambarkan sesuatu dengan kompleksitas O (N log N)?

Sebagai contoh:

  • O (1): Konstan

  • O (log N): Logaritmik

  • O (N): Linear

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

  • O (N 2 ): Kuadratik

  • O (N 3 ): Kubik

algorithms algorithm-analysis big-o matiascelasco
sumber
5
Saya sering di sini istilah luas "quasi-linear" berarti di O(n · f(n))mana f(n) << n. Tapi ini cocok juga dengan hal-hal seperti O(n · log log n)dan di O(n α(n))mana α(n)kebalikan dari fungsi Ackermann.
Bakuriu
en.wikipedia.org/wiki/…
Ry-
34
"Oh enn log enn" mungkin cukup bagus.
user253751
Duplikat lintas-situs di sini: Apa nama kelas fungsi yang dijelaskan oleh O (n log n)?
martin

Jawaban:

60

"N log N" sama bagusnya dengan yang Anda dapatkan, dan harus dipahami dengan baik oleh programmer profesional. Anda tidak dapat mengharapkan ada satu kata untuk menggambarkan setiap kelas kompleksitas yang ada.

Philip Kendall
sumber
6
“Tidak bisa berharap ada satu kata untuk menggambarkan setiap kelas kompleksitas” - tentu saja tidak. Tetapi 𝓞 ( n ⋅ log n ) adalah kelas yang sangat penting sehingga ia layak mendapatkan namanya sendiri, IMO; dan seperti yang dikatakan oleh Steve Jessop, linearithmic sudah cukup umum.
leftaroundabout
@leftaroundabout Memang cukup umum bahwa Anda bisa berdebat, bahwa itu memang pantas disebut. Tetapi "n log n" cukup singkat untuk diucapkan (hanya tiga suku kata) yang berfungsi baik sebagai nama. Sebagai perbandingan, "Logaritmik" adalah empat suku kata. Ini lebih menarik ketika Anda sampai ke algoritma eksternal di mana sebagian besar "n log n" algoritma mendapatkan kompleksitas $ N log_B (N / B) $, yang tentu saja akan menjadi kelas kompleksitas yang layak untuk nama yang lebih pendek.
kasperd
10
Sebagai mahasiswa magister sains komputer, saya telah mendengar "enn log enn" selama kuliah. Saya belum pernah mendengar "linearithmic" dan tidak akan mengerti apa artinya pada awalnya.
Kevin - Reinstate Monica
@Kevin: Logarithmic adalah empat suku kata, tetapi "log-enn" hanya dua. Demikian juga, O (N ^ 2) adalah "enn-squared", bukan "kuadratik". Saya kira "kubik" memiliki lebih sedikit fonem daripada "enn-cubed", tetapi saya pikir istilah terakhir masih lebih umum.
supercat
51

Ada istilah jargon yang artinya linearitmik persis ini.

Saya tidak percaya bahwa itu dipahami secara universal oleh semua programmer, jadi jika Anda tidak hati-hati maka itu akan mengaburkan lebih daripada yang diinformasikan. Secara pribadi saya biasanya tidak menggunakannya, dan jika saya melakukannya maka saya mungkin akan mendefinisikannya pada penggunaan pertama, misalnya "artikel ini menganggap linearithmic ( O(N log N)) algoritma".

Steve Jessop
sumber
11
Bahkan tidak pernah tahu itu ada!
David mengatakan Reinstate Monica
12

Kadang-kadang disebut "loglinear", meskipun kata itu sebenarnya berarti sesuatu yang berbeda. Saya hanya akan tetap dengan "N log N", meskipun, seperti jawaban @ Philip menyarankan.

Jörg W Mittag
sumber
1
Apa arti alternatif untuk log-linear? Jika saya menginginkan nama selain 'N log N', log-linear adalah istilah yang saya gunakan.
Jonathan Leffler
2
@JonathanLeffler: Saya berasumsi en.wikipedia.org/wiki/Log-linear_analysis terkadang dieja tanpa tanda hubung. Tentu saja dengan namespace yang tepat Anda dapat dengan senang hati menggunakan kata yang sama untuk kelas kompleksitas.
Steve Jessop
@SteveJessop: Itu pasti yang muncul melalui pencarian Google. Saya tidak yakin apakah saya bersedia menerima kombo Google / Wikipedia sebagai otoritatif, meskipun saya tidak ragu bahwa analisis log-linear adalah seperti yang dijelaskan.
Jonathan Leffler
1
@ JonathanLeffler: bisa juga berarti apa yang saya sebut plot lin-log atau log-lin (atau, karena saya malas, sebenarnya saya sering menyebut mereka plot log sebagai berbeda dari yang log-log). Kita mungkin bertanya, apa makna alternatif jawaban yang ada dalam pikiran :-)
Steve Jessop
2

Karena faktor tersebut log ntumbuh lambat, deskripsi kualitatif O(n log n)akan "hampir linier". Bergantung pada audiens Anda, kelas O(n log n)algoritme mungkin terkenal, seperti misalnya ini halnya dengan pengurutan cepat pada nitem berdasarkan perbandingan.

hardmath
sumber