Big O คือ , อะไรคือ Big O , Big O หมายถึง , ความหมายของ Big O

เขียนมั่วไปส่งเถอะครับ ไม่ได้อ่านหรอก บ่นเหมือนกันทุกรุ่น
อยากได้คำตอยจริงๆลองถามอาจารย์ดู
big-O คืออะไรในความหมายของปรัชญา

มาดูกันครับ
หลังจากไม่ได้ Up blog มานาน(ด้วยความขี้เกียจเป็นเหตุนั่นเอง 555)
วันนี้ขอมาแนะนำเรื่องของ Big O และการคำนวณเวลาการรันโปรแกรมด้วยฟังก์ชัน
Big O (อ่าน ว่า บิ๊กโอ)ชัว ไม่ผิดแน่ละ.. 
แต่อย่าเข้าใจผิดว่า Big O เป็นญาติหรือเครือเดียวกับ Big C ละ เดียวจะสอบตกโดยไม่รู้ตัว

Big-O Notation

- เครื่องหมาย บิ๊ก-โอ ใช้ในการระบุทรัพยากรที่ใช้ในการทำงานของอัลกอริทึมเมื่อขนาดของอินพุทเปลี่ยนไป
- ปกติแล้วทรัพยากรดังกล่าวจะหมายถึงเวลา นั่นคือ ความสัมพันธ์ระหว่าง เวลา กับ ขนาดของ อินพุท
- อาจกล่าวง่าย ๆ ว่า หากอินพุทมีขนาดใดขนาดหนึ่ง เวลาที่ใช้ในการทำงานมากที่สุด (upper bound) จะเป็นเท่าใด บิ๊ก-โอ เป็นฟังก์ชั่นที่นิยมใช้มากที่สุดในการระบุประสิทธิภาพของอัลกอริทึม 


Big-O Notation

ตัวอย่าง
- ความหมายของ O(n) คือ ฟังก์ชั่นนั้น ๆ ใช้เวลาทำงานช้าที่สุด ≤ n
- เช่น อัลกอริทึม a1 มีประสิทธิภาพเป็น O(n2)    ถ้า n = 10 แล้ว a1 จะใช้เวลาทำงานช้าที่สุด 100 หน่วยเวลา (รับประกันว่าไม่ช้าไปกว่านี้ - แต่อาจจะเร็วกว่านี้ได้)
- เขียนได้ว่า f(n) є O(g(n)) เพื่อบอกว่า f(n) เป็นฟังก์ชันที่ไม่โตเร็วกว่า g(n)
-  เราสามารถหาค่าคงตัวบวก C ที่ f(n) ≤ Cg(n) 


หากบางท่านเคยได้ไปอ่านเว็บ Reference  ต่างๆเกี่ยวกับ ภาษาซี แล้วเห็นเค้าเขียนว่า O(n) หรือ O(n^2) หรือ O(n log n) เคยสงสัยมั้ยว่ามันคืออะไร...

สำหรับนักเขียนโปรแกรมทั้งหลาย โดยเฉพาะในการแข่งขัน (โอลิมปิกหรือ Online Contest ต่างๆ) สิ่งที่สำคัญมากคือเราจำเป็นต้องรู้เวลาในการรัน

โปรแกรมของเรา เพราะการแข่งขันโดยมากจะมีการระบุว่า โปรแกรมของคุณจะต้องรันเสร็จในเวลากี่วินาทีต่อ 1 ชุดข้อมูลทดสอบ แล้วถามว่า เราจะรู้

ได้ยังไงนะ ว่าโปรแกรมของเราจะใช้เวลารันมากกกกแค่ไหน

สิ่ง ที่จะช่วยได้ก็คือการคำนวณฟังก์ชัน Big O นั่นเองครับ บิ๊กโอไม่ได้เป็นฟังก์ชันที่ไว้ให้เรียกใช้ในการเขียนโปรแกรมนะครับ แต่เป็นฟังก์ชันสมมติ
ทางคณิตศาสตร์อย่างหนึ่งที่เราเอาไว้ใช้คำนวณเวลาของ อัลกอริทึม 

ในการคำนวณเวลาการรัน เราจะให้ความสำคัญกับ "ลูป" ครับ เพราะโดยมากแล้วจะเป็นส่วนที่กินเวลาการทำงานมากที่สุด(อันนี้หมายถึงการ เขียน

โปรแกรมในการแข่งขันแก้โจทย์นะครับ ส่วนอื่นๆผมไม่ทราบ) โปรแกรมจะรันทันหรือไม่ทันก็ดูที่การทำซ้ำหรือลูปนี่ละครับ

การคำนวณ ฟังก์ชัน Big O จึงจะใช้การดูจาก "จำนวนรอบ" ครับ การเขียนฟังก์ชันบิ๊กโอจะเขียนกันในรูป

O(จำนวนรอบ)

โดย O(จำนวนรอบ) = เวลาการรันในแต่ละรอบ * จำนวนรอบ;

...

อ่าว งงๆ เชิญงงกันให้หนำใจครับ งงเสร็จเมื่อไหร่ก็อ่านต่อได้เลย

อธิบาย ง่ายๆ(เหรอ..) ก็คือ สมมติว่าเราวนลูป 50 รอบ แต่ละรอบใช้เวลา 0.00001 วินาที ก็จะได้ว่าโปรแกรมของเราทำงานด้วยเวลา 0.00001*50 =

0.00050 วินาทีนั่นเอง

ตัวอย่างเช่นสมมติเรามีข้อมูลขนาด n ตัว แล้วเราวนลูป สมมติวนลูป print ค่าในอาเรย์ทั้งหมดออกมา เขียนโค้ดเป็นภาษาซีได้แบบนี้

for( i=0 ; i

ลูป ของเราก็จะวิ่งวนๆๆๆๆ  ตั้งแต่รอบที่ 0 1 2 ... ไปถึงรอบที่ n-1 ได้ว่า เราทำการวิ่งไปทั้งหมด n รอบ ก็จะได้ว่า โปรแกรมของเราใช้เวลารันเท่ากับ

O(n) (อ่านว่า "โอเอ็น") นั่นเอง

อ่าว แล้ว O(n) ของเฮียมันกี่วิล่ะ อธิบายมาให้เคลียร์!!!

คำตอบก็ง่ายแสน ง่าย ใช้ปัญญาสักนิดก็จะได้คำตอบว่า...ไม่รู้ครับ :)  (: 

อ่าว...กวน ตี_

ก็ไม่รู้จริงๆนิ่ครับ เพราะเราไม่รู้ว่า printf แต่ละครั้งมันกินเวลาเท่าไหร่ สิ่งที่พอจะทำได้ก็คือการ "ประมาณ" ครับ ส่วนนี้อาจจะต้องใช้ประสบการณ์กัน

พอสมควร แต่สรุปกันแบบง่ายๆซะงั้นก็คืออัลกอริทึมที่ทำงานด้วยเวลา O(n) จะรันทันใน 1 วินาทีก็ต่อเมื่อ n มีค่าไม่เกิน 1 ร้อยล้านครับ อันนี้คือ

ประมาณกันแบบสุดๆเลยนะครับ บางตำราก็บอกสิบล้าน มันก็ขึ้นอยู่กับว่า...

1. ในลูปคุณมีอะไรอยู่ หากในลูปคุณมีโค้ดยาวเฟื้อย เวลาในการรันแต่ละรอบก็จะมาก โปรแกรมของคุณก็จะยิ่งกินเวลามาก อาจจะรันได้ไม่ถึง 1

ร้อยล้านรอบใน 1 วินาที
2. ความเร็ว CPU หากเครื่องของคุณใช้ซุปเปอร์ซีพียูความเร็วซัก 100GHz คุณจะรันซักพันล้านรอบผมว่ามันก็ทันครับ แต่ถ้าใช้ซีพียูยุคพฤษภาทมิฬ

หรือ 6 ตุลา 19 หนึ่งร้อยล้านรอบก็อาจจะใช้เวลากันเป็น 10วิ.หรือเป็นนาทีเลยทีเดียว แต่สำหรับซีพียูที่ใช้ในเครื่องตรวจโดยเฉลี่ย ก็เร็วพอที่จะให้รัน

100 ล้านรอบน 1 วิได้ครับ
3. ภาษาที่ใช้ อันนี้ก็สำคัญครับ ภาษาบางภาษาใช้เวลารันค่อนข้างมาก ในขณะที่บางภาษาก็รันค่อนข้างเร็ว(ภาษาซีเป็นต้น) การประมาณของผมดูที่

ภาษาซีเป็นหลักครับ
4. อื่นๆ  คิดไม่ออก

แนะนำว่าอย่า พยามให้รันถึงร้อยล้านเลยครับ ไม่ปลอดภัยสำหรับการแข่งขันที่ลิมิตเวลา 1 วินาที เพราะจะรันได้ร้อยล้าน ลูปต้องตัวเล็กพอสมควร (

ตัวเล็กหมายถึงข้างในมีโค้ดไม่เยอะ ศัพท์ใครไม่รู้ ยืมมา ^ ^)

ถาม ว่าทำไมต้อง O( n ) ใช้ Y( n ) หรือ Hello ( n )   ไม่ได้หรอ....  ก็ได้ครับ อย่างที่ผมบอก มันไม่ใช่ฟังก์ชันที่เราจะเขียนลงไปในโค้ด มันก็แค่

ฟังก์ชันที่เรานึกอยู่ในหัว แต่โดยสากลแล้วจะใช้ตัวโอใหญ่ครับ

เอ แล้วถ้าลูป 2 ชั้นล่ะ...

โลกนี้ไม่ได้มีเพียงแค่ O(n) ครับท่านผู้ชม บางครั้งเราอาจจำใจต้องเขียนลูป 2 ชั้น เช่น กำหนดให้มีตารางรูปสี่เหลี่ยมจตุรัสขนาด n*n ช่อง แล้วให้

แสดงค่าในตารางออกมา เราก็จะก้มหน้าก้มตาเขียนลูปกันออกมาประมาณนี้

for( i=0 ; i

for( j=0 ; j

printf("%c ",table[i][j]);

printf("\n");

}

สัง เกตุว่า ลูปนอกวิ่ง n รอบ ข้างในมีลูปวิ่งอีก n รอบ...เราก็จะได้ว่าโปรแกรมของเรา ทำงานด้วยเวลา O(n^2) นั่นเอง!!!! (อ่าน "โอเอ็นกำลังสอง")

อ่าว แล้ว 3 ชั้นล่ะท่าน...

ก็ O(n^3) ไง...

นี่ก็คือฟังก์ชัน O () คร่าวๆครับ เดี๋ยวผมจะมาต่ออีกหน่อยเรื่องทฤษฎีเล็กๆน้อยๆในบทหน้าครับ

ข้อมูลเกี่ยวกับ Big O ตามนี้เลย เข้าไปดูเองขี้เกรียจพิมพ์

1 .Big O  www.srwdan.com/databigo.htm
2.Big O http://cs.payap.ac.th/pumin/221_2_50/221_2.pdf 
3.Big O http://www.science.cmru.ac.th/admin/blog/file/51108122320.ppt
By : Scheguc ราชพฤษ
By : Mistertun