การวิเคราะห์อัลกอริทึม(algorithm analysis)
•Download as PPT, PDF•
5 likes•14,027 views
วิชาโครงสร้างྺ้อมูล
การวิเคราะห์อัลกอริทึม(algorithm analysis)
- 2. • การวิเคราะห์อัลกอริทึม มีเป้าหมายเพื่อหา ประสิทธิภาพของอัลกอริทึม นั่นคือการประมาณ ค่าทรัพยากรที่จำาเป็นต้องใช้ในการทำางาน เช่น เวลา หรือ หน่วยความจำา อัลกอริทึมส่วนใหญ่ถูก ออกแบบมาเพื่อให้สามารถรองรับจำานวนอินพุท ได้ไม่จำากัด ปกติแล้วประสิทธิภาพ หรือความซับ ซ้อนของอัลกอริทึมจะวัดจากความสัมพันธ์ของ จำานวนอินพุทกับเวลาที่ใช้ในการทำางาน หรือ พื้นที่หน่วยความจำาที่ใช้ (ในระยะหลังเรื่องของ พื้นที่ไม่ถูกพิจารณามากนักเนื่องจากความ ก้าวหน้าในการพัฒนาหน่วยความจำา) • การออกแบบอัลกอริทึมเพื่อแก้ปัญหาใด ๆ
- 3. Asymptotic notationAsymptotic notation เครื่องหมายที่ใช้อธิบายการเติบโตของฟัง ก์ชั่น โดยในการวิเคราะห์อัลกอริทึมจะนำา เครื่องหมายนี้มาใช้ในการระบุ ประสิทธิภาพของอัลกอริทึม มีหลาย สัญลักษณ์ ดังนี้
- 4. Big-O NotationBig-O Notation • เครื่องหมาย บิ๊ก-โอ ใช้ในการระบุ ทรัพยากรที่ใช้ในการทำางานของอัลกอริ ทึมเมื่อขนาดของอินพุทเปลี่ยนไป • ปกติแล้วทรัพยากรดังกล่าวจะหมายถึง เวลา นั่นคือ ความสัมพันธ์ระหว่าง เวลา กับ ขนาดของอินพุท • อาจกล่าวง่าย ๆ ว่า หากอินพุทมีขนาดใด ขนาดหนึ่ง เวลาที่ใช้ในการทำางานมาก ที่สุด (upper bound) จะเป็นเท่าใด บิ๊ก- โอ เป็นฟังก์ชั่นที่นิยมใช้มากที่สุดในการ
- 5. • ตัวอย่าง • ความหมายของ O(n) คือ ฟังก์ชั่นนั้น ๆ ใช้ เวลาทำางานช้าที่สุด ≤ n • เช่น อัลกอริทึม a1 มีประสิทธิภาพเป็น O(n2 ) ถ้า n = 10 แล้ว a1 จะใช้เวลาทำางานช้าที่สุด 100 หน่วยเวลา (รับประกันว่าไม่ช้าไปกว่านี้ - แต่อาจจะเร็วกว่านี้ได้) • เขียนได้ว่า f(n) є O(g(n)) เพื่อบอกว่า f(n) เป็น ฟังก์ชันที่ไม่โตเร็วกว่า g(n) • Big-O NotationBig-O Notation
- 6. f(n) є O(g(n)) f(n) ≤(g(n)) Big-O NotationBig-O Notation
- 8. โอเมก้าใหญ่ (Big-Omega notation : Ω) • โอเมก้าใหญ่ จะใช้สำาหรับบอกถึงเวลาที่ใช้ น้อยที่สุด(lower bound) เมื่ออัลกอริทึมนั้น ๆ ทำางานกับอินพุทขนาดใดขนาดหนึ่ง • ตัวอย่าง • ความหมายของ Ω(n) คือ ฟังก์ชั่นนั้น ๆ ใช้ เวลาทำางานเร็วที่สุด ≥ n • เช่น อัลกอริทึม a1 มีประสิทธิภาพเป็น Ω(n) ถ้า n = 10 แล้ว a1 จะใช้เวลาทำางานเร็ว ที่สุด 10 หน่วยเวลา (รับประกันว่าไม่เร็วไป กว่านี้ - แต่อาจจะช้ากว่านี้ได้)
- 9. • เขียนได้ว่า f(n) є Ω(g(n)) เพื่อบอกว่า f(n) เป็นฟังก์ชันที่ไม่โตไม่ช้ากว่า g(n) • เราสามารถหาค่าคงตัวบวก C ที่ Cg(n) ≤ f(n) โอเมก้าใหญ่ (Big-Omega notation : Ω)
- 10. f(n) є Ω(g(n)) Cg(n) ≤ f(n) โอเมก้าใหญ่ (Big-Omega notation : Ω)
- 11. เตต้าใหญ่ (Big-Teta notation : Ө) • f(n) = Ө(g(n)) ก็ต่อเมื่อ f(n) = O(g(n)) และ f(n) = Ω(g(n)) • นั่นคือขอบบนและขอบล่างเป็นฟังก์ชั่นเดียวกัน
- 12. เตต้าใหญ่ (Big-Teta notation : Ө) f(n) є Ө(g(n)) C1g(n) ≤ f(n) ≤ C2g(n)
- 13. รูป 2.1 ความสัมพันธ์ระหว่างเวลาที่ใช้ กับจำานวน อินพุท ของฟังก์ชั่น 10n ฟังก์ชั่น 5n+4 และ 3n สังเกตว่า ขอบบน กับ ขอบล่าง เป็นฟังก์ชั่นเดียวกัน สัมประสิทธิ์ต่างกัน ความหมายของเตต้าคือ ใช้เวลา เตต้าใหญ่ (Big-Teta notation : Ө)
- 14. โอเล็ก (Little-o : o) •Little-o คือฟังก์ชั่นที่ไม่แตะขอบบน นั่น คือ ฟังก์ชั่นนี้ ทำางานช้าที่สุด < n •คือ o(g(n)) คือเซตของฟังก์ชันที่โต ช้ากว่า g(n) •เช่น หากเรามี t(n) = n0.98 + 0.05√n เราสามารถเขียนได้เป็น O(n) หรือ o(n) • แต่หากระบุเป็น Little-o จะเน้นให้เห็น ชัดว่าไม่ถึง n (เพราะค่ากำาลังของ n คือ
- 15. โอเมก้าเล็ก (Little-omega : ω) Little-omega คือฟังก์ชั่นที่ไม่แตะขอบ ล่าง นั่นคือ ฟังก์ชั่นนี้ทำางานเร็วที่สุด > n คือ ω(g(n)) คือเซตของฟังก์ชันที่โต เร็วกว่า g(n)
- 16. เปรียบเทียบ ลักษณะของฟังก์ชั่ นของแต่ละสัญลักษณ์ 2 สรุปเชิงเปรียบเทียบ ลักษณะของฟังก์ชั่นของแต่ละสัญล ≤ n <n ≥ n >n
- 17. การหาเทอมที่โตเร็วที่สุดในฟัง ก์ชั่น • คือ อัตราการเจริญเติบโตของ ฟังก์ชัน ที่แทนประสิทธิภาพของอัลกอริ ทึม • รูปแบบของฟังก์ชั่นที่มักพบบ่อยได้แก่ • exponential อยู่ในรูป an • polynomial อยู่ในรูป na (n ยก กำาลังค่าคงที่) เช่น n3 • Linear อยู่ในรูป n • logarithmic อยู่ในรูป logan • ทั้ง 4 รูปแบบ จะมีอัตราการเติบโตเรียง จากมากไปหาน้อย n a
- 18. อัตราการเจริญเติบโตของ ฟังก์ชัน 0 10 20 30 40 50 60 70 1 2 3 4 5 6 n 2^n n^2 log 2 n 2n n2 n log2n รูป 2.3 กราฟแสดงการเติบโตของฟังก์ชั่น
- 21. อัตราการติบโตྺองฟังก์ชัน • ตามประสิทธิภาพของอัลกอริธึมจากมากสุด(คือใช้ เวลาน้อยที่สุด) ไปหาน้อยสุด • C > logN > Log2 N > √N > N > N log N > N2 > N3 …Nk > 2n , cn > N!
- 22. อัตราการเจริญเติบโตของ ฟังก์ชัน •ตย1 •จงเรียงลำาดับฟังก์ชันต่อไปนี้ตาม อัตราการเจริญเติบโต •0.5n , 1 , log n , n , 10n •จะได้ว่า •0.5n < 1 < log n < n < 10n
- 23. •ตย 2 •จงเปรียบเทียบอัตราการเจริญ เติบโตของ n10 , 2n •จะได้ว่า •n10 < 2n อัตราการเจริญเติบโตของ ฟังก์ชัน
- 24. ตาราง 2.1 เปรียบเทียบเวลาการ ทำางานกับจำานวนอินพุท พิจารณาตารางจะพบว่า O(1) เป็นฟังก์ชั่นที่ให้ ประสิทธิภาพดีที่สุด นั่นคือ เวลาที่ใช้ในการทำางานไม่ขึ้น กับจำานวนอินพุท ในขณะที่ O(n) จะให้ประสิทธิภาพใน ระดับกลาง นั่นคือ อัตราการเติบโตของเวลาจะเป็นเส้น ตรง เมื่ออินพุทมากขึ้น ก็จะใช้เวลามากขึ้น ในสัดส่วนที่เท่า 2 ประสิทธิ ภาพสูง ตำ่า
- 25. การวิเคราะห์ประสิทธิภาพขอ งอัลกอริทึม • เราสามารถวิเคราะห์ประสิทธิภาพได้จาก ปริมาณคำาสั่งที่ถูกใช้งานในโปรแกรม อาศัย เครื่องหมายที่กล่าวมาข้างต้นเป็นตัวกำากับ โดย การนับคำาสั่งทั้งที่เป็นคำาสั่งมูลฐาน และคำาสั่ง มาตรเวลา ซึ่งจะทำาให้ได้ฟังก์ชั่นที่มีความ ละเอียดสูง จากนั้นจะค่อย ๆ ลดความซับซ้อนลง โดยดูจากเทอมที่ใหญ่ที่สุดของฟังก์ชั่น ในกรณีที่ต้องการกำากับด้วย บิ๊ก-โอ Ө(n2 ) Ө(n log n) เวลาในการทำางานทั้งหมดถูก กำาหนดโดยส่วนที่ 1 เพราะมัน โตเร็วกว่า
- 27. f(n) = O(n)f(n) = O(n) การวิเคราะห์ประสิทธิภาพขอ งอัลกอริทึม •ตย •อัลกอริทึม 1 Sum := 0; for I:=1 to n do Sum := Sum+I;
- 28. f(n) = O(1)f(n) = O(1) • ตย. • อัลกอริทึม 3 Sum := (1+n)*n/2; การวิเคราะห์ประสิทธิภาพขอ งอัลกอริทึม
- 30. n4 + n2 + n n4 O(f(n)) =O(f(n)) = การหาค่า Big-Oh • หาได้โดยนำา f(n) มากระทำาดังนี้ 1. ตัดสัมประสิทธิ์ของแต่ละเทอมทิ้ง 2. เลือกเทอมที่ใหญ่สุดเก็บไว้เป็นคำาตอบ • ตัวอย่างเช่น f(n) = 3n4 + 2n2 + n
- 31. เมื่อพิจารณาจาก f(n) จะพบว่า • อัลกอริทึม 1 f(n) = n • อัลกอริทึม 2 f(n) = n-1 • อัลกอริทึม 3 f(n) = 1 ประสิทธิภาพประสิทธิภาพตำ่าสุดตำ่าสุด ประสิทธิภาพประสิทธิภาพดีสุดดีสุด
- 32. การหาค่า Big-Oh •ตย จงหาค่า Big-o ของ n3 +2n3 +10 • 1. ตัดสัมประสิทธิ์ของแต่ละเทอมทิ้ง จะได้ n3 +n3 • 2. เลือกเทอมที่ใหญ่สุดเก็บไว้เป็นคำาตอบ O(f(n)) =O(f(n)) = OO((n3 ))
- 33. การหาค่า Big-Oh • ตย จงหาค่า Big-o ของ 100 •F(n) = 100 • O(f(n)) =O(f(n)) = O(O(1)1) • ตย จงหาค่า Big-o ของ 100N+1 •F(n) = 100N+1 • O(f(n)) =O(f(n)) = O(O(N)N)
- 34. การหาค่า Big-Oh • ตย จงหาค่า Big-o ของ 20nlogn+5n = O(nlogn) •F(n) = 20nlogn+5n •F(n) = nlogn+n • O(f(n)) =O(f(n)) = = O(nlogn)
- 35. • สมมติให้แต่ละโปรแกรมใช้เวลาในการทำางาน เป็นดังนี้ • prg1 = 3n2 +2n • prg2 = 2log2n+6n+n • prg3 = n+nlog2n+4n+9 • จงแสดง Big-O ของแต่ละโปรแกรมพร้อมทั้ง เรียงลำาดับประสิทธิภาพของโปรแกรมจากดีสุด ไปหาช้าสุด • 2Log2n < nlog2n < 3n2 • จะได้ 1. prg2 2. prg3 3.prg1 การวิเคราะห์ประสิทธิภาพขอ งอัลกอริทึม
- 36. แบบฝึกหัด 1. ให้ลำาดับอัตราการเติบโตของ ฟังก์ชันจากน้อยไปมาก •n log n, n3 , 2n , n, n!, log n, 100, n2 2.จงหาค่า Big-o ของ 12nlogn+0.05n2 3. จงหาค่า Big-o ของ n1/2 +3nlogn 4. ให้ลำาดับอัตราการติบโตྺองฟังก์ชัน
- 37. 5. จงวิเคราะห์ประสิทธิภาพของอัลกอริทึม ดังต่อไปนี้ for (j=1; j<n;j++){ sum = sum + j; print sum; } for (i=1; i<n;i++){ for (j=1; j<n;j++){ sum = sum + j; } print sum; }
- 38. 6. จงวิเคราะห์ประสิทธิภาพของอัลกอริทึม ดังต่อไปนี้ For i = 1 To n i = i + 1 Next i For j = 1 To n j = j + 1 Next j