Page 40 - โครงสร้างข้อมูลและขั้นตอนวิธี

P. 40

2-30 โครงสร้างข้อมูลและขั้นตอนวิธี

กฎข ้อท ่ี 3 การวเิ คราะห์ค �ำส ่ังการท �ำงานแ บบต อ่ เน่ือง
ค�ำส ั่งการท�ำงานแ บบต่อเนื่อง (consecutive statement) คือ การรวมโปรแกรมย ่อยส่วนต่างๆ ต่อเน่ืองกัน
เวลาท่ีใช้ประมวลผลของโปรแกรมรวมทั้งหมดจะเท่ากับเวลาที่ใช้ประมวลผลในส่วนของโปรแกรมท่ีใช้เวลาประมวล
ผลน านท ่ีสุด ซ่ึงส อดคล้องแ ละเป็นไปต ามท ฤษฎีบท 2.5
เช่น ส่วนของโปรแกรมดังในข้ันตอนวิธีต่อไปน้ี เร่ิมด้วยโปรแกรมย่อยท่ีใช้เวลาประมวลผลในระดับ O(n)
และต ามด้วยโปรแกรมย ่อยท ี่ใช้เวลาในการประมวลผ ลร ะดับ O(n2) ดังน ั้น ในท ี่สุด โปรแกรมร วมท้ังหมดน ี้จะใช้เวลา
ประมวลผ ลในระดับ O(n2)

FOR i := 1 to n DO
BEGIN
ENDAi := 0
FOR i := 1 to n DO
BEGIN
FOR j := 1 to n DO
BEGIN
E NDAi = Ai + Aj + i + j
END

กฎข อ้ ท่ี 4 การว เิ คราะหเ์ ง่ือนไข IF-ELSE
ส�ำหรับส ่วนใดส่วนหนึ่งข องโปรแกรมท ่ีใช้ IF-ELSE ซึ่งม ีรูปแ บบต ามน ้ี

IF (เง่ือนไข) DO
ชุดค �ำส ั่ง S1

ELSE
ชุดค �ำส ั่ง S2

เวลาที่ใช้ประมวลผลค�ำสั่ง IF-ELSE นี้ ใช้เวลาน้อยกว่าหรือเท่ากับผลรวมของเวลาท่ีใช้ในการตรวจสอบ
เง่ือนไขกับเวลาท ี่ใช้ประมวลผลของช ุดค�ำส ั่งท่ีใช้เวลาม ากกว่า

จะเห็นว่า จากกฎข้อนี้ อาจประเมินเวลาที่ใช้เกินไปได้บ้างในบางกรณี แต่เวลาที่ประมาณได้จะไม่มีทาง
ต่ํากว่าเวลาที่ควรจะเป็น ซ่ึงสอดคล้องกับพื้นฐานการวิเคราะห์ข้ันตอนวิธีที่นิยมหาขอบเขตบนของเวลาท่ีใช้
การป ระมวลผ ลในรูปข อง บิ๊กโอ

กฎข ้อท่ี 5 การว ิเคราะห์การเวียนเกิด
การเวียนเกิด (recursion) คือ ขั้นตอนวิธีท่ีมีการเรียกใช้ตัวเองซ้ําเพ่ือประมวลผลการท�ำงาน การวิเคราะห์
ข้ันตอนว ิธีน ี้จ ึงพ ิจารณาได้ในห ลายล ักษณะข ึ้นอยู่ก ับรูปแ บบการเรียกใช้ ดังน้ี

35 36 37 38 39 40 41 42 43 44 45