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

การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-35

4. จงห​ า​บ๊กิ โ​อข​ อง​ข้ันต​ อนว​ ธิ ีต​ อ่ ​ไป​น้ี

Procedure Evaluation(A1, A2, …, An; n := 50) /* รับ​คะแนน​ของน​ ักเรียน​ท้งั หมด 50 คน */

11111114516723893204615 BEGIN
sum := 0
i := 1
WHILE i ≤ n DO /* วนลูป while ใน​ขณะท​ ี่ i ≤ n */
BEGIN /* หาผ​ ลร​ วม sum */
sum := sum + Ai /* เพิม่ ค​ า่ ด​ ชั นี i เพื่อ​อ้างอิงจ​ �ำนวน */
i := i + 1 /* หาร​ผล​รวมท​ ​ี่ได้ด​ ้วย n */
END /* มากกวา่ ห​ รือเ​ทา่ กบั 75 ถือวา่ ผา่ นม​ าตรฐาน */
avg := sum/n /* นอ้ ย​กวา่ 75 ถอื ว่า ไม​ผ่ ่านม​ าตรฐาน */
IF avg ≥ 75 THEN
DISPLAY "pass"
ELSE
DISPLAY "not pass"
END

แนว​ตอบ​กิจกรรม 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

ส่วน​ของโ​ปรแกรม​นี้ เปน็ ก​ าร​ทำ�ลูป for ซ้อน​ใน 3 ลปู
การป​ ระมวลผ​ ลส​ ่วนใ​น​สุดข​ องล​ ูป for ซ้อนก​ นั คือ Sum := Sum + 1 ซง่ึ ม​ ก​ี ารด​ ำ�เนินก​ ารท​ ั้งหมด
2 อย่าง คือ การบ​ วก​และ​การ​ให้​ค่า คดิ เ​ป็น 2 หน่วย​เวลา
n i i+j
ดัง​น้ัน จา​กลูป for ซ้อนใ​น จะ​ได้การป​ ระมวลผ​ ลท​ ้งั หมด คดิ ​เปน็ 2 หน่วย​เวลา
จะไ​ ด้​วา่ iΣ=1 jΣ=1 kΣ=1

T(n) = n i i+j 2

iΣ=1 jΣ=1 kΣ=1
n i i+j
= 2 1
iΣ=1 jΣ=1 kΣ=1
n i
= 2 (i + j)
iΣ=1 jΣ=1