บทนำสู่ความซับซ้อนของเวลาของอัลกอริทึม

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

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

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

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

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

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

ปัญหาคือการค้นหา เราต้องค้นหาองค์ประกอบในอาร์เรย์ (ในปัญหานี้เราจะถือว่าอาร์เรย์เรียงลำดับจากน้อยไปมาก) เพื่อแก้ปัญหานี้เรามีสองอัลกอริทึม:

1. การค้นหาเชิงเส้น

2. การค้นหาแบบไบนารี

สมมติว่าอาร์เรย์มีสิบองค์ประกอบและเราต้องหาตัวเลขสิบในอาร์เรย์

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

ค้นหาเชิงเส้นขั้นตอนวิธีการจะเปรียบเทียบองค์ประกอบของอาร์เรย์แต่ละกับsearch_digit เมื่อมันพบsearch_digitในอาร์เรย์ก็จะกลับจริง

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

โดยทั่วไปการค้นหาเชิงเส้นจะใช้จำนวนnของการดำเนินการในกรณีที่แย่ที่สุด (โดยที่nคือขนาดของอาร์เรย์)

ลองตรวจสอบอัลกอริทึมการค้นหาแบบไบนารีสำหรับกรณีนี้

ตัวอย่างนี้สามารถเข้าใจการค้นหาแบบไบนารีได้อย่างง่ายดาย:

ที่มา: Learneroo

ถ้าเราลองใช้ตรรกะนี้กับปัญหาของเราก่อนอื่นเราจะเปรียบเทียบsearch_digitกับองค์ประกอบกลางของอาร์เรย์นั่นคือ 5 ตอนนี้เนื่องจาก 5 น้อยกว่า 10 เราจะเริ่มค้นหาsearch_digitในองค์ประกอบอาร์เรย์ มากกว่า 5 ในทำนองเดียวกันจนกว่าเราจะได้องค์ประกอบที่ต้องการ 10

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

จำนวนการดำเนินการ = บันทึก (10) = 4 (โดยประมาณ)

สำหรับฐาน 2

เราสามารถสรุปผลลัพธ์นี้สำหรับการค้นหาแบบไบนารีเป็น:

สำหรับอาร์เรย์ขนาดnจำนวนการดำเนินการที่ดำเนินการโดย Binary Search คือlog (n)

สัญกรณ์ O ขนาดใหญ่

ในข้อความข้างต้นเราเห็นว่าสำหรับอาร์เรย์ขนาดn การค้นหาเชิงเส้นจะดำเนินการnเพื่อทำการค้นหาให้เสร็จสมบูรณ์ ในทางกลับกันการค้นหาแบบไบนารีดำเนินการlog (n)จำนวนการดำเนินการ (ทั้งสองกรณีที่เลวร้ายที่สุด) เราสามารถแทนค่านี้เป็นกราฟ ( แกน x : จำนวนองค์ประกอบแกน y : จำนวนการดำเนินการ)

ที่มา: Techtud

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

เมื่อเราวิเคราะห์อัลกอริทึมเราใช้สัญกรณ์เพื่อแสดงถึงความซับซ้อนของเวลาและสัญกรณ์นั้นคือสัญกรณ์ Big O

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

ความซับซ้อนของเวลาหรือสัญลักษณ์ Big O สำหรับอัลกอริทึมยอดนิยมบางรายการแสดงอยู่ด้านล่าง

  1. การค้นหาแบบไบนารี: O (log n)
  2. การค้นหาเชิงเส้น: O (n)
  3. จัดเรียงด่วน: O (n * log n)
  4. เรียงลำดับการเลือก: O (n * n)
  5. พนักงานขายที่เดินทาง: O (n!)

สรุป

ขอขอบคุณในความพยายามของคุณหากคุณยังคงอ่านบทความนี้ ตอนนี้คุณต้องคิด - ทำไมความซับซ้อนของเวลาจึงสำคัญที่ต้องเข้าใจ?

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

ตัวอย่างเช่นหากเรามี 4 พันล้านองค์ประกอบที่ต้องค้นหาในกรณีที่เลวร้ายที่สุดการค้นหาเชิงเส้นจะใช้เวลา 4 พันล้านการดำเนินการเพื่อให้งานสำเร็จ การค้นหาแบบไบนารีจะทำให้งานนี้เสร็จสมบูรณ์ใน 32 การดำเนินการ นั่นคือความแตกต่างที่ยิ่งใหญ่ ตอนนี้สมมติว่าถ้าการดำเนินการหนึ่งใช้เวลา 1 มิลลิวินาทีในการดำเนินการให้เสร็จสิ้นการค้นหาไบนารีจะใช้เวลาเพียง 32 มิลลิวินาทีในขณะที่การค้นหาเชิงเส้นจะใช้เวลา 4 พันล้านมิลลิวินาที (ประมาณ 46 วัน) นั่นคือความแตกต่างที่สำคัญ

นี่คือเหตุผลว่าทำไมการศึกษาความซับซ้อนของเวลาจึงมีความสำคัญเมื่อต้องใช้ข้อมูลจำนวนมากเช่นนี้

ทรัพยากร

Grokking Algorithms - โดย Aditya Y Bhargava

รู้เบื้องต้นเกี่ยวกับสัญกรณ์ Big O และความซับซ้อนของเวลา - โดย CS Dojo