Jika

Saya baru saja menemukan kalimat ini di halaman 6 dari Garey and Johnson's "Computers and Intractability".

Algoritma apa pun yang fungsi kompleksitas waktunya tidak dapat dibatasi disebut algoritma waktu eksponensial (walaupun harus dicatat bahwa definisi ini mencakup fungsi kompleksitas waktu non-polinomial tertentu, seperti , yang biasanya tidak dianggap sebagai fungsi eksponensial). $n^{\log n}$

Pertanyaan saya sebagai berikut,

$n^{\log n}$

Terima kasih.

algorithms terminology polynomial-time pengguna777
sumber

Jawaban:

Tidak ada terminologi tetap untuk jenis fungsi ini. Terkadang Anda mungkin melihat "subeksponensial" atau "superpolinomial" yang digunakan untuk merujuk pada perilaku semacam ini.

Tom van der Zanden
sumber

Istilah umum lainnya adalah quasipolynomial .

Yuval Filmus

@ user777 Saya pikir subeksponensial adalah bentuk

c^{n^{\frac{1}{1 + γ}}}

$c^{n^{\frac1{1+\gamma}}}$ sedangkan superpolinomial atau kuasipolinomial adalah bentuk

c^{{catatan}^{1 + γ} n}

$c^{\log^{1+\gamma} n}$ dengan

c, γ > 0

$c,\gamma>0$ tersisa tetap