Apa yang dimaksud dengan batas atas yang asimptotik ketat?

Dari apa yang telah saya pelajari ikatan ketat asimptot artinya terikat dari atas dan bawah seperti pada notasi theta. Tapi apa arti batas atas yang asimptotik ketat untuk notasi Big-O?

Mengatakan bahwa ikatan O-besar "ketat secara asimptot" pada dasarnya berarti bahwa penulis seharusnya menulis . Misalnya, O ( x 2 ) berarti tidak lebih dari beberapa kali konstan  x 2 untuk semua x yang cukup besar  ; "Asymptotically tight" berarti itu benar-benar adalah beberapa kali konstan  x 2 untuk x yang cukup besar  dan tidak, katakanlah, beberapa kali konstan  x 1.999 .$\Theta(-)$$O(x^2)$$x^2$$x$$x^2$$x$$x^{1.999}$

Ini contoh yang menjelaskannya (dan contoh nyata untuk jawaban David yang baik).

Misalkan Anda memiliki algoritma yang diberikan sebagai masukan array bilangan bulat . Algoritme memindai melalui array, dan menambah penghitung awalnya diatur ke nol setiap kali ia melihat elemen yang bahkan bilangan bulat. Kita bisa membuktikan berjalan algoritma dalam katakanlah O ( n 3 ) waktu, di mana n adalah jumlah elemen dalam A . Tapi kita juga bisa memberikan batasan yang lebih ketat , dan mengatakan itu berjalan dalam waktu O ( n ) . Batas ini ketat asimptotik: pada kenyataannya, karena membaca input sudah memakan waktu Ω ( n ) , kita bisa lebih tepat dan mengatakan algoritma membutuhkan$A$$O(n^3)$$n$$A$$O(n)$$\Omega(n)$ waktu.$\Theta(n)$