[การวิเคราะห์อัลกอริทึม] [ตารางไดนามิก] [ไบโนเมียลฮีพ] [เลซี่ไบโนเมียลฮีพ] [ฟิโบนักซี่ฮีพ] [สคริวฮีพ][รายการอ้างอิง]

การวิเคราะห์อัลกอริทึม

            การแก้ไขปัญหาหนึ่งๆ ส่วนใหญ่จะมีขั้นตอนวิธีหรือมีอัลกอริทึมที่สามารถแก้ปัญหานั้นได้หลายวิธี โดยในแต่ละวิธีจะใช้เวลาในการแก้ปัญหาแตกต่างกันไป ซึ่งในบางวิธีจะสามารถแก้ปัญหานั้นในบางกรณีได้ดี คืออาจจะมีวิธีหนึ่งที่สามารถแก้ปัญหากรณี (a) ได้ดีกว่าวิธีอื่นๆ แต่วิธีดังกล่าวนี้เมื่อนำไปแก้ปัญหาในกรณี (b) แล้วจะด้อยกว่าวิธีอื่น ดังนั้นในการวิเคราะห์ประสิทธิภาพนั้นจะต้องคำนวณหาเวลาดำเนินการของแต่ละวิธี เพื่อที่จะวิเคราะห์ได้ว่าควรใช้วิธีไหนในการแก้ปัญหานั้นๆ ในปัจจุบันการวิเคราะห์อัลกอริทึมมี 3 แบบด้วยกันคือ การวิเคราะห์กรณีร้ายแรงที่สุด การวิเคราะห์กรณีเฉลี่ย และการวิเคราะห์ถัวเฉลี่ย ในที่นี้จะขอใช้ปัญหาการนับเลขฐานสองเป็นตัวอย่าง ในการแสดงการวิเคราะห์

            พิจารณาการนับเลขฐานสอง 8 บิตที่เริ่มนับจาก 0, 1, 2, … , 15 โดยจะใช้แถวลำดับ (array) A [0 … 7] แทนบิตแต่ละบิต บิตต่ำสุดคือ A[0] และบิตสูงสุดคือ A[7] ดังรูปที่ 1.1 แสดงบิตที่ถูกเปลี่ยนค่าในการเพิ่มครั้งต่อไปด้วยตัวสีแดง ที่ซึ่งเวลาในการดำเนินงานเป็นสัดส่วนโดยตรงกับจำนวนการเปลี่ยนค่าของบิต จากบิต 1 เป็นบิต 0 หรือจากบิต 0 เป็นบิต 1

รูปที่ 1.1 การนับเลขฐานสอง

            การทำงานการเพิ่มค่าเลขฐานสองไปอีกหนึ่ง สามารถเขียนเป็นอัลกอริทึมได้ดังนี้

การวิเคราะห์กรณีร้ายแรงสุด
            สำหรับการวิเคราะห์นี้ เวลาที่ใช้ดำเนินงานในกรณีร้ายแรงสุดจะเป็นเวลาที่เป็นขอบเขตบนของการทำงาน กล่าวคือเวลาที่ใช้ในการดำเนินงานนั้น จะไม่มีการใช้เวลาเกินกว่าเวลาในกรณีร้ายแรงสุด แม้ว่าข้อมูลที่อินพุตมาจะมีลักษณะใดก็ตาม
            พิจารณาการนับเลขฐานสองในรูปที่ 1.1 ถ้า i > บิต A[i] จะไม่เปลี่ยนค่า ดังนั้นในกรณีร้ายแรงสุด สำหรับ i = 0, 1, … , บิต A[i] เปลี่ยนค่า n ครั้งเท่ากันหมด เวลาดำเนินงานกรณีร้ายแรงสุด (W (n)) จะเป็น

            ดังนั้นสำหรับการนับเลขฐานสอง เวลารวมที่ใช้ในกรณีร้ายแรงสุดจะเป็นจะมี O(nlog n) หรือเวลาที่ใช้ในกรณีร้ายแรงสุดจะเป็น O(log n)

การวิเคราะห์กรณีเฉลี่ย
            สำหรับการวิเคราะห์นี้ เวลาที่ใช้ดำเนินงานจะเป็นค่าคาดหมายของการดำเนินงาน ซึ่งเป็นไปได้ที่จะคาดผิดไป กล่าวคือในการดำเนินงานนั้นจริงๆแล้ว อาจใช้เวลาไปมากกว่าหรือน้อยกว่า เวลาที่ได้คาดไว้ เพราะเวลาที่คาดหมายไว้ เป็นเพียงสมมติฐานของความน่าจะเป็นเท่านั้น
             พิจารณาการนับเลขฐานสอง ถ้า i > บิต A[i] จะไม่เปลี่ยนค่าเลย สำหรับ i = 0, 1, … , สมมติให้   p(I_i)    เป็น ความน่าจะเป็นที่จะเกิดการเปลี่ยนค่าของบิต A[i] และ     t(I_i)    เป็น เวลาดำเนินงานการเปลี่ยนค่าของบิต A[i]    แล้ว

            ดังนั้น เวลารวมที่ใช้ในกรณีเฉลี่ย สำหรับการนับเลขฐานสอง จะเป็น O(nlog n) หรือเวลาที่ใช้ในกรณีเฉลี่ย จะเป็น O(log n)

การวิเคราะห์ถัวเฉลี่ย
            สำหรับการวิเคราะห์นี้ จะเป็นการเฉลี่ยเวลาที่เป็นไปได้มากที่สุดในแต่ละการดำเนินงาน ซึ่งในการวิเคราะห์แบบนี้ เปรียบการแทนเวลาที่ใช้ เป็นเงินต้นทุน และแทนการเฉลี่ยเวลาที่เป็นไปได้มากที่สุดเป็นต้นทุนถัวเฉลี่ย ถ้าเวลาในแต่ละการดำเนินงานส่วนใหญ่มีต้นทุนถูก การวิเคราะห์แบบนี้จะทำให้มีต้นทุนถัวเฉลี่ยแล้วถูก แม้ว่าบางการดำเนินงานจะมีต้นทุนสูงก็ตาม ซึ่งถ้าเทียบกับการวิเคราะห์กรณีร้ายแรงสุดแล้ว เมื่อมีบางการดำเนินงานมีต้นทุนสูง ต้นทุนโดยรวมก็ต้องสูง แม้ว่าการดำเนินงานส่วนใหญ่แล้วมีต้นทุนต่ำก็ตาม
            สำหรับเทคนิคที่ใช้ในการวิเคราะห์แบบนี้ มี 3 เทคนิควิธี คือ
            1. วิธีรวมกลุ่ม (Aggregate method) โดยจะแสดงให้เห็นว่า สำหรับการดำเนินงาน n ลำดับ ต้นทุนเฉลี่ยเป็น โดยที่ T(n) เป็นผลรวมต้นทุนทุกๆการดำเนินงาน ในการนับเลขฐานสอง เมื่อ n = 16 พบว่าบิต A[1] จะเปลี่ยนค่า 8 ครั้ง หรือ ครั้ง บิต A[2] จะเปลี่ยนค่า 4 ครั้ง หรือ ครั้ง และถ้า i > บิต A[i] จะไม่เปลี่ยนค่าเลย ดังนั้นในการดำเนินงานของการนับที่เริ่มจาก 0 ไปจนถึง n-1 สำหรับ i = 0, 1, … , บิต A[i] จะเปลี่ยนค่า ครั้ง ผลรวมจำนวนของการเปลี่ยนค่าเป็น
                                                                                           
            นั่นคือ ต้นทุนในการนับเลขฐานสองที่เริ่มนับจาก 0 ถึง n-1 เป็น 2n และต้นทุนถัวเฉลี่ย สำหรับแต่ละการดำเนินงานเป็น หรือเวลาที่ใช้ในกรณีถัวเฉลี่ยในวิธีรวมกลุ่มเป็น O(1)
            2. วิธีบัญชี (Accounting method) สำหรับวิธีนี้ จะต้องมีการกำหนดต้นทุนถัวเฉลี่ยในแต่ละการดำเนินงานก่อน โดยต้นทุนถัวเฉลี่ยอาจจะมากกว่าหรือน้อยกว่าต้นทุนจริงก็ได้ และถ้าการดำเนินงานใดมีต้นทุนถัวเฉลี่ยมากกว่าต้นทุนจริงแล้ว ความแตกต่างของต้นทุนถัวเฉลี่ยกับต้นทุนจริงจะถูกบันทึกในโครงสร้างข้อมูลที่เรียกว่า เครดิต ซึ่งเครดิตนี้จะลดลงได้ ถ้าการดำเนินงานใดๆมีต้นทุนถัวเฉลี่ยน้อยกว่าต้นทุนจริง ดังนั้นในวิธีนี้จะมองต้นทุนถัวเฉลี่ย แยกเป็น 2 ส่วน คือ (1.) ต้นทุนจริง (2.) เครดิต ซึ่งอาจมีเพิ่มขึ้นหรือลดลง ซึ่งจะต่างกับวิธีรวมกลุ่มที่ต้นทุนถัวเฉลี่ยจะไม่แยกเป็น 2 ส่วน ดังเช่นในวิธีนี้ อย่างไรก็ตาม ต้นทุนถัวเฉลี่ยรวมของลำดับการดำเนินงานจะต้องเป็นขอบเขตบนของต้นทุนจริงรวมของลำดับการดำเนินงาน ดังนั้นเครดิตเมื่อสุทธิแล้วต้องไม่ติดลบ เพราะเครดิตสุทธิจะแสดงถึงจำนวนของต้นทุนถัวเฉลี่ยรวมที่จะต้องมากกว่าต้นทุนจริงรวม พิจารณาการนับเลขฐานสอง กำหนดให้ต้นทุนจริงในการเปลี่ยนบิตเป็น 1 บาท และให้ต้นทุนถัวเฉลี่ยของการเซตบิตให้เป็น 1 เป็น 2 บาท โดยใช้ 1 บาทเพื่อจ่ายสำหรับการเซตบิตให้เป็น 1 และอีก 1 บาท ถูกจัดเก็บไว้เป็นเครดิตของบิตนั้นๆ นั่นคือที่บิต 1 ทุกๆบิต จะมีเครดิตอยู่ 1 บาท เพื่อใช้เป็นค่าใช้จ่ายในการเซตบิต 1 กลับเป็นบิต 0 ในอนาคต จากต้นทุนถัวเฉลี่ย 2 บาทที่ใช้ในการนับแต่ละครั้งที่กำหนดให้นั้น พบว่าไม่มีเครดิตที่บิตใดติดลบเสมอระหว่างนับ(นั่นคือ ต้นทุนถัวเฉลี่ยรวมไม่เคยน้อยกว่าต้นทุนจริงรวม) ดังนั้นต้นทุนถัวเฉลี่ยที่กำหนดไว้ 2 บาท ใช้ได้ จึงแสดงว่าเวลาการทำงานถัวเฉลี่ยของการนับแต่ละครั้งจึงเป็น 2 หรือเวลาที่ใช้ในกรณีถัวเฉลี่ยในวิธีบัญชีเป็น O(1)
            3. วิธีศักย์ (Potential method) สำหรับในวิธีนี้ จะมองในแง่ของการสะสมพลังงานศักย์ กล่าวคือ ถ้าการดำเนินงานใดมีต้นทุนถัวเฉลี่ยมากกว่าต้นทุนจริงแล้ว จะเป็นการสะสมพลังงานศักย์ โดยสะสมเป็นจำนวนเท่ากับผลต่างของต้นทุนถัวเฉลี่ยกับต้นทุนจริง ทำนองเดียวกัน ถ้าการดำเนินงานใดมีต้นทุนถัวเฉลี่ยน้อยกว่าต้นทุนจริงแล้ว จะเป็นการลดพลังงานศักย์เป็นจำนวนเท่ากับผลต่างของต้นทุนถัวเฉลี่ยกับต้นทุนจริง ซึ่งพลังงานศักย์ที่สะสมนี้ จะเป็นพลังงานที่สะสมของทั้งระบบ ต่างกับวิธีบัญชีที่เครดิตนั้น จะเป็นเงินที่กำกับอยู่กับข้อมูลต่างๆในระบบ

            สำหรับการดำเนินงาน n ลำดับ ที่ i = 1, 2, … , n
            ให้      C_i      เป็น ต้นทุนจริงของการดำเนินงานที่ i

                เป็น ฟังก์ชันศักย์ในการดำเนินงานที่ i

            เป็น ฟังก์ชันศักย์ก่อนการดำเนินงานที่ i

               เป็น ต้นทุนถัวเฉลี่ยของการดำเนินงานที่ i

            เพราะฉะนั้น     
            ต้นทุนจริงเป็นภาระการเปลี่ยนบิต และฟังก์ชันศักย์เป็นจำนวนบิต 1กำหนดให้ b_i คือ จำนวนบิตที่เป็น 1 หลังการดำเนินงานที่ i และ t_i คือ จำนวนของบิตที่ถูกเซตให้เป็น 0 ในการดำเนินงานที่ i ดังนั้น เนื่องจากต้นทุนจริงอย่างมากคือภาระการเปลี่ยนบิตจาก 1 เป็น 0 จำนวน t_i บิต และการเปลี่ยนบิต 0 เป็น 1 อีกอย่างมาก 1 บิต เพราะฉะนั้น 

           ดังนั้นต้นทุนถัวเฉลี่ย เป็น

การจินตทัศน์