f(x) = O(g(x)) ก็ต่อเมื่อ
lim x -> inf ; f(x)/g(x) = c
หรือมองอีกมุมหนึ่ง f(x) <= c*g(x) เมื่อ x >= n
โดย c, n เป็นค่าคงที่หนึ่ง ๆ
อืมมม โดยปกติแล้วเรามองว่า function ที่นำมาคิด Big O relation กันเนี่ย เราจะมองกันว่าเป็น function ที่ให้ค่าบวกเท่านั้นนะครับ
โดยส่วนตัวผมจะเข้าใจว่า มันเป็นการเปรียบเทียบกันแบบว่ามากกว่าแบบจะ ๆ เช่น
n = O(n^2)
n^2 + n = O(n^2)
ลองถามเพื่อความเข้าใจครับ ลองเปรียบเทียบ n/log n กับ sqrt(n) ดูครับ
|