อัลกอริทึมแบบคู่ขนาน - การวิเคราะห์

การวิเคราะห์อัลกอริทึมช่วยให้เราทราบว่าอัลกอริทึมมีประโยชน์หรือไม่ โดยทั่วไปอัลกอริทึมจะถูกวิเคราะห์ตามเวลาดำเนินการ(Time Complexity) และจำนวนพื้นที่ (Space Complexity) มันต้องการ.

เนื่องจากเรามีอุปกรณ์หน่วยความจำที่ซับซ้อนในราคาที่สมเหตุสมผลพื้นที่จัดเก็บข้อมูลจึงไม่ใช่ปัญหาอีกต่อไป ดังนั้นความซับซ้อนของพื้นที่จึงไม่ได้รับความสำคัญมากนัก

อัลกอริทึมแบบขนานได้รับการออกแบบมาเพื่อปรับปรุงความเร็วในการคำนวณของคอมพิวเตอร์ สำหรับการวิเคราะห์อัลกอริทึมคู่ขนานโดยปกติเราจะพิจารณาพารามิเตอร์ต่อไปนี้ -

ความซับซ้อนของเวลา (เวลาดำเนินการ)
จำนวนโปรเซสเซอร์ทั้งหมดที่ใช้และ
ค่าใช้จ่ายทั้งหมด.

ความซับซ้อนของเวลา

เหตุผลหลักที่อยู่เบื้องหลังการพัฒนาอัลกอริทึมแบบขนานคือการลดเวลาในการคำนวณของอัลกอริทึม ดังนั้นการประเมินเวลาดำเนินการของอัลกอริทึมจึงมีความสำคัญอย่างยิ่งในการวิเคราะห์ประสิทธิภาพ

เวลาดำเนินการวัดตามเวลาที่อัลกอริทึมใช้ในการแก้ปัญหา เวลาในการดำเนินการทั้งหมดจะคำนวณจากช่วงเวลาที่อัลกอริทึมเริ่มดำเนินการจนถึงช่วงเวลาที่หยุดทำงาน หากโปรเซสเซอร์ทั้งหมดไม่เริ่มต้นหรือสิ้นสุดการดำเนินการพร้อมกันเวลาดำเนินการทั้งหมดของอัลกอริทึมคือช่วงเวลาที่โปรเซสเซอร์ตัวแรกเริ่มต้นการทำงานจนถึงช่วงเวลาที่โปรเซสเซอร์ตัวสุดท้ายหยุดการทำงาน

ความซับซ้อนของเวลาของอัลกอริทึมสามารถแบ่งออกเป็นสามประเภท

Worst-case complexity - เมื่อระยะเวลาที่อัลกอริทึมต้องการสำหรับอินพุตที่กำหนดคือ maximum.
Average-case complexity - เมื่อระยะเวลาที่อัลกอริทึมต้องการสำหรับอินพุตที่กำหนดคือ average.
Best-case complexity - เมื่อระยะเวลาที่อัลกอริทึมต้องการสำหรับอินพุตที่กำหนดคือ minimum.

การวิเคราะห์ Asymptotic

ความซับซ้อนหรือประสิทธิภาพของอัลกอริทึมคือจำนวนขั้นตอนที่ดำเนินการโดยอัลกอริทึมเพื่อให้ได้ผลลัพธ์ที่ต้องการ การวิเคราะห์ Asymptotic ทำขึ้นเพื่อคำนวณความซับซ้อนของอัลกอริทึมในการวิเคราะห์เชิงทฤษฎี ในการวิเคราะห์แบบไม่แสดงอาการจะใช้อินพุตขนาดใหญ่เพื่อคำนวณฟังก์ชันความซับซ้อนของอัลกอริทึม

Note - Asymptoticคือเงื่อนไขที่เส้นมีแนวโน้มที่จะพบกับเส้นโค้ง แต่ไม่ตัดกัน ที่นี่เส้นและเส้นโค้งเป็นแบบไม่แสดงอาการซึ่งกันและกัน

สัญกรณ์ Asymptotic เป็นวิธีที่ง่ายที่สุดในการอธิบายเวลาดำเนินการที่เร็วและช้าที่สุดสำหรับอัลกอริทึมที่ใช้ขอบเขตสูงและขอบเขตความเร็วต่ำ สำหรับสิ่งนี้เราใช้สัญกรณ์ต่อไปนี้ -

สัญกรณ์ Big O
สัญกรณ์โอเมก้า
สัญกรณ์ Theta

สัญกรณ์ Big O

ในทางคณิตศาสตร์สัญกรณ์ Big O ใช้เพื่อแสดงถึงลักษณะที่ไม่แสดงอาการของฟังก์ชัน แสดงถึงพฤติกรรมของฟังก์ชันสำหรับอินพุตขนาดใหญ่ในวิธีการที่ง่ายและถูกต้อง เป็นวิธีการแสดงขอบเขตบนของเวลาดำเนินการของอัลกอริทึม แสดงถึงระยะเวลาที่ยาวนานที่สุดที่อัลกอริทึมสามารถใช้เพื่อดำเนินการให้เสร็จสมบูรณ์ ฟังก์ชั่น -

f (n) = O (g (n))

iff มีค่าคงที่เป็นบวก c และ n₀ ดังนั้น f(n) ≤ c * g(n) เพื่อทุกสิ่ง n ที่ไหน n ≥ n₀.

สัญกรณ์โอเมก้า

สัญกรณ์ Omega เป็นวิธีการแสดงขอบเขตล่างของเวลาดำเนินการของอัลกอริทึม ฟังก์ชั่น -

ฉ (n) = Ω (g (n))

iff มีค่าคงที่เป็นบวก c และ n₀ ดังนั้น f(n) ≥ c * g(n) เพื่อทุกสิ่ง n ที่ไหน n ≥ n₀.

สัญลักษณ์ Theta

สัญกรณ์ Theta เป็นวิธีการแสดงทั้งขอบเขตล่างและขอบเขตบนของเวลาดำเนินการของอัลกอริทึม ฟังก์ชั่น -

ฉ (n) = θ (g (n))

iff มีค่าคงที่เป็นบวก c₁, c₂, และ n₀ ดังนั้น c1 * g (n) ≤ f (n) ≤ c2 * g (n) สำหรับทุกคน n ที่ไหน n ≥ n₀.

การเร่งความเร็วของอัลกอริทึม

ประสิทธิภาพของอัลกอริทึมแบบขนานถูกกำหนดโดยการคำนวณ speedup. Speedup ถูกกำหนดให้เป็นอัตราส่วนของเวลาดำเนินการกรณีที่เลวร้ายที่สุดของอัลกอริธึมแบบลำดับที่รู้จักกันเร็วที่สุดสำหรับปัญหาเฉพาะกับเวลาดำเนินการกรณีที่เลวร้ายที่สุดของอัลกอริทึมแบบขนาน

speedup =

เวลาดำเนินการเคสที่แย่ที่สุดของลำดับที่ทราบเร็วที่สุดสำหรับปัญหาเฉพาะ / เวลาดำเนินการเคสที่แย่ที่สุดของอัลกอริทึมแบบขนาน

จำนวนโปรเซสเซอร์ที่ใช้

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