Page 43 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 43
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-33
จะได้ว ่า n i
T(n) = iΣ=1 jΣ=1 2
= 2 n i 1
iΣ=1 jΣ=1
n
= 2 i
iΣ=1
= 2 n(n + 1)
2
เพราะฉะน้ัน = n2 + n
T(n) = n2 + n = O(n2)
จากตัวอย่างท่ี 2.19 2.20 และ 2.21 จะเห็นว่า การพิจารณา T(n) มีความยุ่งยาก แต่ถ้าใช้กฎการหาบ๊ิกโอ
ทั้ง 5 ข้อ ท่ีแนะน�ำไปแล้ว จะทราบได้ทันทีว่าบิ๊กโอของแต่ละตัวอย่างจะเป็นอะไร เช่นในตัวอย่างท่ี 2.21 น้ี จะเห็นว่า
เป็นลูป for ซ้อนใน 2 ลูป ลูปแรกจะมีขนาดการวนท�ำซ �้ำ n คร้ัง (เน่ืองจากวนรอบค่า i ต้ังแต่ 1 ถึง n) ลูปซ้อนที่ 2
มีขนาดการวนท�ำซ ้�ำ i ครั้ง (เน่ืองจากวนรอบค่า j ตั้งแต่ 1 ถึง i) แต่เน่ืองจาก i มีค่าสูงสุดได้ถึง n ดังน้ัน จะมีขนาด
การวนท�ำซ ้ําสูงสุด n ครั้ง จากกฎข้อที่ 4 ลูป for ซ้อนใน จะได้ว่าเวลาท่ีใช้ประมวลผลจะเป็นผลคูณข องขนาดข องลูป
for ซ้อนในท ้ังหมด น่ันค ือ n × n เป็น O(n2) นั่นเอง
กิจกรรม 2.2.1
1. จงห าฟงั ก์ชนั เวลา T(n) ทใ่ี ช้ในก ารป ระมวลผลส่วนข องโปรแกรมต่อไปน ้ี พรอ้ มทง้ั หาบก๊ิ โอ
1.1
FOR i := 1 to n DO
FOR j := 1 to i DO
FOR k := 1 to i + j DO
Sum := Sum + 1
1.2
FOR i := 1 to n DO
FOR j := 1 to n*n*n DO
FOR k := 1 to j DO
Sum := Sum + 1
