อธิบายอัลกอริทึม Brute Force

อัลกอริทึม Brute Force เป็นวิธีการที่ตรงไปตรงมาในการแก้ปัญหาที่อาศัยพลังการประมวลผลที่แท้จริงและพยายามทุกวิถีทางแทนที่จะใช้เทคนิคขั้นสูงเพื่อปรับปรุงประสิทธิภาพ

ตัวอย่างเช่นสมมติว่าคุณมีแม่กุญแจเล็ก ๆ ที่มีตัวเลข 4 หลักแต่ละตัวมีค่า 0-9 คุณลืมชุดค่าผสมของคุณ แต่คุณไม่ต้องการซื้อแม่กุญแจอื่น เนื่องจากคุณจำตัวเลขใด ๆ ไม่ได้คุณจึงต้องใช้วิธี brute force เพื่อเปิดล็อค

ดังนั้นคุณจึงตั้งค่าตัวเลขทั้งหมดกลับเป็น 0 และลองทีละตัว: 0001, 0002, 0003 ไปเรื่อย ๆ จนกว่าจะเปิดขึ้น ในกรณีที่เลวร้ายที่สุดจะใช้เวลา 104 หรือ 10,000 ครั้งในการค้นหาชุดค่าผสมของคุณ

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

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

ความซับซ้อนของเวลาของแรงเดรัจฉานคือO (m n )ซึ่งบางครั้งเขียนเป็นO (n * m). ดังนั้นหากเราค้นหาสตริงของอักขระ "n" ในสตริงของอักขระ "m" โดยใช้กำลังดุร้ายเราจะต้องใช้เวลา n * m

ข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม

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

นี่คือวิธีที่ Wikipedia กำหนด:

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

มีข้อกำหนดบางประการที่อัลกอริทึมต้องปฏิบัติตาม:

  1. ความชัดเจน: แต่ละขั้นตอนในกระบวนการมีการระบุไว้อย่างแม่นยำ
  2. ความสามารถในการคำนวณที่มีประสิทธิภาพ: แต่ละขั้นตอนในกระบวนการสามารถดำเนินการได้โดยคอมพิวเตอร์
  3. ความวิจิตร: ในที่สุดโปรแกรมจะยุติลงได้สำเร็จ

อัลกอริทึมทั่วไปบางประเภท ได้แก่ :

  • อัลกอริทึมการเรียงลำดับ
  • อัลกอริทึมการค้นหา
  • อัลกอริธึมการบีบอัด

คลาสของอัลกอริทึม ได้แก่

  • กราฟ
  • การเขียนโปรแกรมแบบไดนามิก
  • การเรียงลำดับ
  • กำลังค้นหา
  • สตริง
  • คณิตศาสตร์
  • เรขาคณิตเชิงคำนวณ
  • การเพิ่มประสิทธิภาพ
  • เบ็ดเตล็ด.

แม้ว่าในทางเทคนิคจะไม่ใช่คลาสของอัลกอริทึม แต่โครงสร้างข้อมูลมักจะถูกจัดกลุ่มไว้ด้วยกัน

ประสิทธิภาพ

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

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

การเรียงลำดับอัลกอริทึม

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

Quicksort

ไม่มีการจัดเรียงการอภิปรายที่สามารถจบได้โดยไม่ต้องเรียงลำดับอย่างรวดเร็ว นี่คือแนวคิดพื้นฐาน: Quick Sort

ผสาน

อัลกอริทึมการเรียงลำดับซึ่งอาศัยแนวคิดในการจัดเรียงอาร์เรย์จะรวมเข้าด้วยกันเพื่อให้อาร์เรย์ที่เรียงลำดับหนึ่งอาร์เรย์ อ่านเพิ่มเติมได้ที่นี่: Mergesort

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

หนังสือเกี่ยวกับอัลกอริทึมใน JavaScript:

โครงสร้างข้อมูลใน JavaScript

  • หนังสือฟรีที่ครอบคลุมโครงสร้างข้อมูลใน JavaScript
  • GitBook

การเรียนรู้โครงสร้างข้อมูล JavaScript และอัลกอริทึม - Second Edition

  • ครอบคลุมการเขียนโปรแกรมเชิงออบเจ็กต์การสืบทอดต้นแบบการเรียงลำดับและการค้นหาอัลกอริทึมการคัดแยกการผสานโครงสร้างการค้นหาแบบไบนารีและแนวคิดอัลกอริทึมขั้นสูง
  • Amazon
  • ISBN-13: 978-1785285493

โครงสร้างข้อมูลและอัลกอริทึมด้วย JavaScript: การนำแนวทางการคำนวณแบบคลาสสิกมาสู่เว็บ

  • ครอบคลุมอัลกอริทึมการเรียกซ้ำการเรียงลำดับและการค้นหารายการที่เชื่อมโยงและโครงสร้างการค้นหาแบบไบนารี
  • Amazon
  • ISBN-13: 978-1449364939