Big O Function

[ToT]

ใครพอจะอธิบายได้มั่ง รุ่นพี่อธิบายไม่ค่อยเข้าใจเลยอ่ะคับ

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) ดูครับ

[ToT]

ขอบคุณมากครับ

อืม ... ผมลองใช้เครื่องคิดเลข plot กราฟออกมาหยาบๆนะครับ รู้สึกว่า n/log n มันจะตกวูบไปเลยในช่วงแรก แล้วเพิ่มค่าขึ้นเร็วมากจนแซงหน้า sqrt(n) ไปตอนประมาณ x = 1 หลังจากนั้นก็ไม่มีค่าน้อยกว่า sqrt(x) อีก หมายความว่า sqrt(n) = O(n/log n) เมื่อ n มีค่ามากกว่า 1 หรือเท่ากับ 1 ประมาณนี้ใช่ป่าวครับ ???

อ่า .. ถามนิดนึงครับ คือ n² + n = O(n²) เนี่ย มันจะหมายถึง
n² + n ฃ c.n² เมื่อ n ณ ค่าคงที่ค่านึง

คือตอนนี้ที่ผมเข้าใจก็คือว่า n² จะมีค่ามากกว่า n² + n แต่มันจะเป็นจริงเฉพาะตอนที่ c=1 และ n เป็นลบ ใช่หรือเปล่าครับ หรือผมเข้าใจอะไรผิด ?

ใช่แล้วครับ sqrt(n) = O(n/log n) ครับ
ลองใช้ limit ดูจะพบความจริงที่น่าสนใจหลาย ๆ ปรการ เช่น
n^a = O(n/log n) เมื่อ a < 1 ครับ (ในทางกลับกัน n/log n = O(n^a) เมื่อ a >= 1 ครับ)

ผมอาจจะพูดไม่ครบน่ะครับ ไอ้ c กับ n ที่ผมบอกไปตอนต้น หมายถึงว่า ถ้าเราหา c และ n ที่สอดคล้องกับเงื่อนไขได้ เราก็จะได้ความสัมพันธ์ทันที (for some c,n)
เช่น
n^2 + n <= 2*n^2 เมื่อ n >= 1 เพราะฉะนั้นจะได้ว่า n^2 + n = O(n^2)
ในที่นี้ c = 2 เป็นต้น