Mathcenter Forum  

Go Back   Mathcenter Forum > คณิตศาสตร์ทั่วไป > ปัญหาคณิตศาสตร์ทั่วไป
สมัครสมาชิก คู่มือการใช้ รายชื่อสมาชิก ปฏิทิน ค้นหา ข้อความวันนี้ ทำเครื่องหมายอ่านทุกห้องแล้ว

ตั้งหัวข้อใหม่ Reply
 
เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
  #1  
Old 14 สิงหาคม 2002, 19:44
ToT's Avatar
ToT ToT ไม่อยู่ในระบบ
จอมยุทธ์หน้าหยก
 
วันที่สมัครสมาชิก: 13 สิงหาคม 2001
ข้อความ: 154
ToT is on a distinguished road
Post Big O Function

ใครพอจะอธิบายได้มั่ง รุ่นพี่อธิบายไม่ค่อยเข้าใจเลยอ่ะคับ
__________________
Mmmm ....
ตอบพร้อมอ้างอิงข้อความนี้
  #2  
Old 15 สิงหาคม 2002, 23:39
<DividedByZero>
 
ข้อความ: n/a
Post

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) ดูครับ
ตอบพร้อมอ้างอิงข้อความนี้
  #3  
Old 16 สิงหาคม 2002, 20:46
ToT's Avatar
ToT ToT ไม่อยู่ในระบบ
จอมยุทธ์หน้าหยก
 
วันที่สมัครสมาชิก: 13 สิงหาคม 2001
ข้อความ: 154
ToT is on a distinguished road
Post

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

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

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

คือตอนนี้ที่ผมเข้าใจก็คือว่า n2 จะมีค่ามากกว่า n2 + n แต่มันจะเป็นจริงเฉพาะตอนที่ c=1 และ n เป็นลบ ใช่หรือเปล่าครับ หรือผมเข้าใจอะไรผิด ?
__________________
Mmmm ....
ตอบพร้อมอ้างอิงข้อความนี้
  #4  
Old 17 สิงหาคม 2002, 01:46
<DividedByZero>
 
ข้อความ: n/a
Post

ใช่แล้วครับ 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 เป็นต้น
ตอบพร้อมอ้างอิงข้อความนี้
ตั้งหัวข้อใหม่ Reply


หัวข้อคล้ายคลึงกัน
หัวข้อ ผู้ตั้งหัวข้อ ห้อง คำตอบ ข้อความล่าสุด
Function problems Far ปัญหาคณิตศาสตร์ทั่วไป 4 23 กรกฎาคม 2009 05:09
ช่วยหาคำตอบFUNCTIONหน่อย บาคุระ จัง ปัญหาคณิตศาสตร์ ม.ปลาย 4 09 กุมภาพันธ์ 2006 17:29
คำถาม (function) Nay ปัญหาคณิตศาสตร์ ม.ปลาย 2 23 พฤษภาคม 2005 09:27
การ take function meteor ปัญหาคณิตศาสตร์ทั่วไป 4 16 กรกฎาคม 2004 19:59
FUNCTION GOD ปัญหาคณิตศาสตร์ทั่วไป 2 14 มีนาคม 2002 16:45

เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
ค้นหาในหัวข้อนี้:

ค้นหาขั้นสูง

กฎการส่งข้อความ
คุณ ไม่สามารถ ตั้งหัวข้อใหม่ได้
คุณ ไม่สามารถ ตอบหัวข้อได้
คุณ ไม่สามารถ แนบไฟล์และเอกสารได้
คุณ ไม่สามารถ แก้ไขข้อความของคุณเองได้

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
ทางลัดสู่ห้อง


เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 19:28


Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha