Jika

13

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).ncatatann

Pertanyaan saya sebagai berikut,

ncatatann

Terima kasih.

pengguna777
sumber

Jawaban:

12

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
7
Istilah umum lainnya adalah quasipolynomial .
Yuval Filmus
3
@ user777 Saya pikir subeksponensial adalah bentuk
cn11+γ
sedangkan superpolinomial atau kuasipolinomial adalah bentuk
ccatatan1+γn
dengan c,γ>0tersisa tetap