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

การวิเคราะห์อัลกอริทึมช่วยให้เราทราบว่าอัลกอริทึมมีประโยชน์หรือไม่ โดยทั่วไปอัลกอริทึมจะถูกวิเคราะห์ตามเวลาดำเนินการ(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 และ n0 ดังนั้น f(n) ≤ c * g(n) เพื่อทุกสิ่ง n ที่ไหน n ≥ n0.

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

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

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

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

สัญลักษณ์ Theta

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

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

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

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

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

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

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

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

ค่าใช้จ่ายทั้งหมด

ต้นทุนรวมของอัลกอริทึมแบบขนานคือผลคูณของความซับซ้อนของเวลาและจำนวนตัวประมวลผลที่ใช้ในอัลกอริทึมนั้น ๆ

ต้นทุนรวม = ความซับซ้อนของเวลา×จำนวนโปรเซสเซอร์ที่ใช้

ดังนั้นไฟล์ efficiency ของอัลกอริทึมแบบขนานคือ -

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