บทความ IT เจ๋งๆ

6 Algorithms พื้นฐาน ที่ Developer ควรรู้จักไว้

18-มี.ค.-22

คัมภีร์เทพ IT

สำหรับคนที่เป็น Developer นอกจากจะมีความรู้ความเชี่ยวชาญในภาษา Programming, Frameworks หรือ Tools ต่าง ๆ ที่เกี่ยวข้องแล้ว Algorithms ก็มีความสำคัญไม่น้อยไปกว่ากัน และในบทความนี้จะกล่าวถึง 6 Algorithms พื้นฐาน ที่ Developer ควรรู้จักไว้

1. Sorting Algorithm

Sorting เป็น Algorithm ที่จัดลำดับของ Item ใน List

Sorting Algorithm มีดังนี้:

  • Bubble Sort: Bubble Sort เป็น Sorting Algorithm ที่เป็นขั้นพื้นฐานที่สุด และมันทำงานด้วยการสลับ Elements ที่อยู่ติดกัน ซ้ำ ๆ ไปเรื่อย ๆ ถ้าที่ Elements เหล่านั้นยังไม่อยู่ในตำแหน่งที่ถูกต้อง และการสลับจะหยุดลงเมื่อลำดับของทุก Elements ถูกเรียงอย่างถูกต้องแล้ว
  • Merge Sort: Merge sort เป็น Sorting Technique ที่ใช้ Divide and Conquer Strategy
  • Quicksort: Quicksort เป็น Sorting Algorithm ยอดนิยมที่ทำการเปรียบเทียบ n log n โดยเฉลี่ย เมื่อเรียงลำดับ Array ของ n elements มันเป็น Sorting Algorithm ที่มีประสิทธิภาพและรวดเร็ว
  • Heap Sort: Heap Sort เป็นการ Sorting ด้วยการมอง Array Elements เป็นรูปแบบ Binary Tree ที่เรียกว่า Heap

2. Searching Algorithm

Searching เป็น Algorithm ทีใช้ในการค้นหา Element ใน Data Set

Searching Algorithms มีดังนี้:

  • Binary Search: Binary Search จะใช้ Divide and Conquer Strategy กับ List ที่ถูกเรียงลำดับเรียบร้อยแล้ว ซึ่ง List นั้นจะถูกแบ่งออกเป็น 2 ส่วนและ Item จะถูกเปรียบเทียบกับ Element ตรงกลาง (Middle Element) ของ List หากพบค่าที่ต้องการแล้ว ตำแหน่งของ Middle Element จะถูก Return กลับมา
  • Breadth-First Search (BFS): Breadth-First Search เป็นการการค้นหาตามแนวกว้าง มันเป็น Graph Traversal Algorithm ที่เริ่มต้นที่ Root Node และจะทำการสำรวจ Node ที่อยู่ใกล้เคียงกันทั้งหมดไปเรื่อย ๆ
  • Depth-First Search (DFS): Depth-First Search (DFS) Algorithm เป็นการการค้นหาตามแนวลึก ที่เริ่มต้นด้วย First Node ของ Graph และจะดำเนินการค้นหาลงไปในทางที่ลึกลงเรื่อย ๆ จนกว่าเราจะพบ Goal Node หรือ Node ที่ไม่มี Child แล้ว

3. Dynamic Programming

Dynamic Programming (DP) เป็น Algorithmic Technique สำหรับการใช้วิธีแก้ปัญหาที่เหมาะสมที่สุด ด้วยการแยกปัญหาใหญ่ ๆ ออกเป็นปัญหาย่อย ๆ และใช้ประโยชน์จากข้อเท็จจริงที่ว่า วิธีแก้ปัญหาที่เหมาะสมที่สุดของปัญหาใหญ่นั้น ขึ้นอยู่กับ วิธีแก้ปัญหาที่เหมาะสมที่สุดของปัญหาย่อย

4. Recursion Algorithm

Recursion เป็นเทคนิคการแก้ปัญหา ซึ่งการแก้ปัญหาจะขึ้นอยู่กับวิธีแก้ปัญหาสำหรับ Instances ที่มีขนาดเล็กกว่าของปัญหาเดียวกัน การคำนวน Factorial เป็นตัวอย่างคลาสสิกของ Recursive Programming

Recursive Program จะทำตามขั้นตอนพื้นฐานที่เหมือนกัน ดังนี้:

  • ตั้ง Algorithm, Recursive Programs มักต้องการ Seed Value เพื่อเริ่มต้น ซึ่งทำได้โดยใช้ Parameter ส่งผ่านไปยัง Function หรือโดยการจัดเตรียม Non-Recursive Gateway Function ซึ่งตั้ง Seed Value สำหรับการคำนวณแบบ Recursive
  • ตรวจสอบเพื่อดูว่า Value ปัจจุบันที่กำลังประมวลผลที่สัมพันธ์กับ Base Case หรือไม่ หากสัมพันธ์กัน ก็ให้ประมวลผล Value แล้ว Return กลับไป
  • ทำการแก้ปัญหาแบบเดียวกันกับปัญหาย่อย หรือปัญหาย่อยที่เล็กกว่าหรือง่ายกว่า
  • ใช้ Algorithm กับปัญหาย่อย
  • เพื่อที่จะได้คำตอบ ให้รวมผลลัพธ์เข้าด้วยกัน
  • Return ผลลัพธ์

5. Divide and Conquer

Divide-and-Conquer Algorithm จะแบ่งปัญหาออกเป็น 2 ปัญหาย่อย(หรือมากกว่า) ที่เป็นประเภทเดียวกันหรือที่เกี่ยวข้องกัน และทำจนกว่าจะง่ายมากพอที่จะแก้ไขได้โดยตรง

Divide and Conquer Algorithm ประกอบด้วย 3 ขั้นตอนที่แสดงด้านล่างนี้:

  • แบ่งปัญหาใหญ่ ออกเป็นปัญหาย่อย ๆ
  • Conquer: แก้ปัญหาย่อยทีละปัญหา และทำซ้ำ ๆ ไปเรื่อย ๆ
  • Combine: นำ Solutions ของปัญหาย่อย ๆ มารวมกัน เพื่อให่ได้ Solution ของปัญหาใหญ่

6. Hashing

Hashing เป็น Technique หรือ Process ที่ใช้ Hash Function เพื่อทำการ Map Keys และ Values ลงใน Hash Table เราทำสิ่งนี้เพื่อให้เข้าถึง Elements ได้เร็วขึ้น ประสิทธิภาพของการ Map จะขึ้นอยู่กับประสิทธิภาพของ Hash Function

ที่มา:  https://medium.com/

 

 

รับตำแหน่งงานไอทีใหม่ๆ ด้วยบริการ IT Job Alert

 

อัพเดทบทความจากคนวงในสายไอทีทาง LINE ก่อนใคร
อย่าลืมแอดไลน์ @techstarth เป็นเพื่อนนะคะ

เพิ่มเพื่อน

 

บทความล่าสุด

ประเภทบทความ