ความซับซ้อนของเวลาและพื้นที่ในโครงสร้างข้อมูล

การวิเคราะห์อัลกอริทึม

การวิเคราะห์ประสิทธิภาพของอัลกอริธึมสามารถทำได้ในสองขั้นตอนที่แตกต่างกัน ก่อนนำไปใช้งานและหลังการใช้งาน ดังที่

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

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

การวิเคราะห์อัลกอริทึมจะจัดการกับการดำเนินการหรือเวลาดำเนินการของการดำเนินการต่างๆ ที่เกี่ยวข้อง เวลาดำเนินการของการดำเนินการสามารถกำหนดเป็นจำนวนคำสั่งคอมพิวเตอร์ที่ดำเนินการต่อหนึ่งการดำเนินการ

ความซับซ้อนของอัลกอริทึม

สมมติว่า X ได้รับการปฏิบัติเหมือนเป็นอัลกอริทึม และ N ถือเป็นขนาดของข้อมูลที่ป้อนเข้าไป เวลาและพื้นที่ที่ใช้โดยอัลกอริทึม X เป็นสองปัจจัยหลักที่กำหนดประสิทธิภาพของ X

ปัจจัยด้านเวลา - เวลาคำนวณหรือวัดโดยการนับจำนวนการดำเนินการหลัก เช่น การเปรียบเทียบในอัลกอริธึมการเรียงลำดับ

Space Factor - พื้นที่คำนวณหรือวัดโดยการนับพื้นที่หน่วยความจำสูงสุดที่อัลกอริทึมต้องการ

ความซับซ้อนของอัลกอริธึม f(N) ให้เวลาทำงานและ/หรือพื้นที่เก็บข้อมูลที่จำเป็นสำหรับอัลกอริทึม โดยคำนึงถึง N เป็นขนาดของข้อมูลอินพุต

ความซับซ้อนของอวกาศ

ความซับซ้อนของพื้นที่ของอัลกอริธึมแสดงถึงปริมาณพื้นที่หน่วยความจำที่อัลกอริทึมจำเป็นต้องใช้ในวงจรชีวิต

พื้นที่ที่อัลกอริทึมต้องการจะเท่ากับผลรวมของสององค์ประกอบต่อไปนี้

ส่วนที่คงที่ซึ่งเป็นพื้นที่ที่จำเป็นสำหรับจัดเก็บข้อมูลและตัวแปรบางอย่าง (เช่น ตัวแปรและค่าคงที่อย่างง่าย ขนาดโปรแกรม เป็นต้น) ที่ไม่ขึ้นอยู่กับขนาดของปัญหา

ส่วนตัวแปรคือช่องว่างที่ตัวแปรต้องการ ซึ่งขนาดจะขึ้นอยู่กับขนาดของปัญหาโดยสิ้นเชิง ตัวอย่างเช่น พื้นที่สแต็กแบบเรียกซ้ำ การจัดสรรหน่วยความจำแบบไดนามิก เป็นต้น

ความซับซ้อนของพื้นที่ S(p) ของอัลกอริธึม p ใด ๆ คือ S(p) =A + Sp(I) โดยที่ A ถือเป็นส่วนคงที่ และ S(I) จะถือเป็นส่วนแปรผันของอัลกอริทึมซึ่งขึ้นอยู่กับลักษณะอินสแตนซ์ I ต่อไปนี้คือตัวอย่างง่ายๆ ที่พยายามอธิบายแนวคิด

อัลกอริทึม

SUM(P, Q)
Step 1 - START
Step 2 - R ← P + Q + 10
Step 3 - Stop

ที่นี่เรามีตัวแปรสามตัว P, Q และ R และค่าคงที่หนึ่งค่า ดังนั้น S(p) =1+3 ตอนนี้พื้นที่ขึ้นอยู่กับประเภทข้อมูลของประเภทคงที่และตัวแปรที่กำหนด และจะถูกคูณตามนั้น

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

ความซับซ้อนของเวลาของอัลกอริทึมคือการแสดงระยะเวลาที่อัลกอริทึมต้องใช้ในการดำเนินการจนเสร็จสิ้น ความต้องการด้านเวลาสามารถแสดงหรือกำหนดเป็นฟังก์ชันตัวเลข t(N) โดยที่ t(N) สามารถวัดเป็นจำนวนขั้นตอนได้ โดยแต่ละขั้นตอนจะใช้เวลาคงที่

ตัวอย่างเช่น ในกรณีที่บวกจำนวนเต็ม n-bit สองตัว จะมีการดำเนินการ N ขั้นตอน ดังนั้น เวลาคำนวณทั้งหมดคือ t(N) =c*n โดยที่ c คือเวลาที่ใช้ในการบวกสองบิต ในที่นี้ เราสังเกตว่า t(N) เติบโตเป็นเส้นตรงเมื่อขนาดอินพุตเพิ่มขึ้น