big O
กำหนดให้ f, T : N → R+ เป็นฟังก์ชั่นจากจำนวนนับถึงจำนวนจริงบวก เราเขียน T(n) = O(f(n)) เมื่อมีจำนวนจริง c และจำนวนเต็ม n0 ซึ่งทำให้เงื่อนไข T(n) ≤ cf(n) เป็นจริง สำหรับทุก n > n0 [ข้อควรระวัง เครื่องหมาย "=" ประโยค T(n) = O(f(n)) ไม่ใช่เครื่องหมาย "เท่ากับ" แต่เป็นการนิยาม T(n) = O(f(n))]

เช่น T(n) = 6n3 + 2n2 + 20n + 45 พหุนามดีกรี 3 ดังนั้น T(n) = O(n3)

• เรานิยมใช้ big-O ในการวัดประสิทธิภาพของอัลกอลิทึม
• ประสิทธิภาพของอัลกอลิทึม (ที่ทำงานได้สำเร็จเท่า ๆ กัน) นิยมดูจาก เวลา และ หน่วยความจำ ที่ใช้ในการทำงานให้ประสบผลสำเร็จ ยิ่งใช้เวลาและหน่วยความจำน้อยเท่าไร ยิ่งเป็นอัลกอลิทึมที่ดี
• มี 2 วิธีในการเปรียบเทียบอัลกอลิทึม
     ก. benchmarking
     ข. analysis of algorithms (asymptotic analysis, big-O)

• big-O เรียงจากประสิทธิภาพสูงสุดไปต่ำสุดได้ดังนี้

O(1), O(log n), O(n), O(n log n), O(n2), O(nK), O(Kn), O(n!)

• วิธีหา big-O อย่างง่ายคือกระจายพหุนาม T(n) แล้วเลือกพจน์ใหญ่สุด
• จากกราฟ เมื่อ n มีค่ามาก เราควรเลือกอัลกอลิทึมที่ O(n) มีประสิทธิภาพสูง หรือ O(n) มีค่าต่ำ









Create Date : 04 ธันวาคม 2550
Last Update : 4 ธันวาคม 2550 20:34:17 น.
Counter : 1796 Pageviews.

0 comments
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

ศล
Location :
กรุงเทพ  Thailand

[ดู Profile ทั้งหมด]
 ผู้ติดตามบล็อก : 85 คน [?]

บทความทั้งหมด