Page 46 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 46
2-36 โครงสร้างข้อมูลและขั้นตอนวิธี
= 2 n (i2 + i)
iΣ=1
n n
= 2 i2 + i
iΣ=1 iΣ=1
= 2 + 16 (2n3 + 3n2 + n) + n(n + 1)
2
= 32 n3 + n2 + 13 n + n2 + n
= 32 n3 + 2n2 + 34 n
เพราะฉ ะนนั้ T(n) = 23 n3 = 2n2 + 34 n = O(n3)
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
สว่ นของโปรแกรมน้ี เปน็ การท �ำ ลปู for ซอ้ นใน 3 ลปู
การป ระมวลผ ลส่วนในสุดข องล ูป for ซ้อนก ันคือ Sum := Sum + 1 ซงึ่ ม กี ารด ำ�เนนิ ก ารท ั้งหมด
2 อยา่ ง คือ การบ วกแ ละการใหค้ า่ คดิ เป็น 2 หน่วยเวลา
ดังนั้น จากลูป for ซ้อนใน จะได้การประมวลผลทั้งหมด คิดเป็น n n3 j หน่วยเวลา
จะไ ด้ว่า
iΣ=1 jΣ=1 kΣ=1
T(n) = n n3 j 2
iΣ=1 jΣ=1 kΣ=1
n n3 j
= 2 1
iΣ=1 jΣ=1 kΣ=1
n n3
= 2 j
iΣ=1 jΣ=1
= 2 n n3(n3 + 1)
2
iΣ=1
= 2 n3(n3 + 1) n 1
2
iΣ=1
= 2 n3(n3 + 1) n
2
= n7 + n4
เพราะฉะน้ัน T(n) = n7 + n4 = O(n7)
