Page 56 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 56
2-46 โครงสร้างข้อมูลและขั้นตอนวิธี
กิจกรรม 2.2.2
1. จงพิจารณาขนั้ ตอนว ิธกี ารสบื ค้น 2 ขัน้ ต อนวธิ ีตอ่ ไปน ี้ ส�ำ หรบั ข้อมลู ทีเ่ รยี งลำ�ดบั ม าแ ลว้ ว่า ขน้ั ต อน
วธิ ไี หนมีประสทิ ธิภาพม ากกวา่ ก นั แ ละจงประม าณบ ิก๊ โอของแต่ละวิธี
Procedure SequentialSearch(A1, A2, …, An, X) Procedure BinarySearch(A1, A2, …, An, X)
BEGIN BEGIN
i := 1 i:=1
WHILE i ≤ n AND X ≠ Ai DO j:=n
i := i + 1 WHILE i < j DO
IF i ≤ n THEN BEGIN
location := i m := [(i + j) / 2]
ELSE IF x > Ami :T=HmE+N1
location := 0
END ELSE
RETURN location j := m
END END
IF x =locAaitiToHn E:=Ni
ELSE
location := 0
RETURN location
END
2. ขน้ั ตอนวธิ ีหนง่ึ ใช้เวลา 12 วนิ าทีในการประมวลผ ลข้อมลู ท ้งั หมด 100 ขอ้ มลู จงห าว ่าข ั้นต อนวธิ ีน ้ี
จะใชเ้ วลากีว่ นิ าทีในก ารป ระมวลผ ลขอ้ มูลขนาด 5,000 ขอ้ มลู ถา้ ฟ งั กช์ ันเวลา T(n) ทขี่ นึ้ อ ย่กู ับขนาดของข้อมูล
n ของขน้ั ต อนวิธีน้ีมอี ตั ราก ารเติบโตดงั ต ่อไปน้ี
2.1 มีอ ัตราการเตบิ โตเป็นฟ ังกช์ นั ค่าค งตวั
2.2 มอี ัตราการเติบโตเป็นฟังกช์ นั เชิงเสน้
2.3 มีอัตราก ารเตบิ โตเป็น O(log n)
2.4 มอี ตั ราการเตบิ โตเป็น O(n3)
แนวตอบกจิ กรรม 2.2.2
1. SequentialSearch() ใชเ้วลาเป็น O(n) ในข ณะท่ี BinarySearch() ใช้เวลาเป็น O(log n) ดังน ั้น การ
ทำ�งานแบบ BinarySearch() มปี ระสทิ ธิภาพและรวดเรว็ ก ว่าสำ�หรับขอ้ มูลข นาดเดียวกัน
2. ข้นั ตอนว ธิ หี นึง่ ใชเ้วลา 12 วนิ าทใี นก ารป ระมวลผ ลข อ้ มูลท ั้งหมด 100 ข้อมูล
2.1 ถา้ ฟงั กช์ นั เวลา T(n) ของข น้ั ตอนวธิ นี ้ี มอี ตั ราก ารเตบิ โตเปน็ ฟ งั กช์ นั ค า่ คงตวั แสดงว า่ ฟงั กช์ นั
เวลา T(n) ไม่ข้ึนอยู่กับขนาดของข้อมูล ไม่ว่าจะประมวลผลข้อมูลขนาดเท่าใด จะใช้เวลาเท่ากัน เพราะฉะนั้น
ขน้ั ต อนวธิ นี จ้ี ะใช้เวลา 12 วนิ าที ในก ารประมวลผ ลขอ้ มูลทั้งหมด 5,000 ข้อมูล
2.2 ถา้ ฟ งั กช์ นั เวลา T(n) ของข นั้ ต อนว ธิ นี ี้ มอี ตั ราก ารเตบิ โตเปน็ ฟ งั กช์ นั เชงิ เสน้ แสดงว า่ ขน้ั ต อน
วิธนี ้ี ประมวลผลข้อมลู 100 ขอ้ มูล ใชเ้ วลา 12 วินาที
