หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

ภาพ

โครงสร้างข้อมูลและอัลกอริทึมใน JavaScript

นี่คือการใช้งานการเขียนโค้ดของหนังสือ DSA.js และ repo สำหรับแพ็คเกจ NPM

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

โครงสร้างข้อมูลเชิงโต้ตอบ

สารบัญ

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

การติดตั้ง

คุณสามารถโคลน repo หรือติดตั้งโค้ดจาก NPM: 

npm install dsa.js

จากนั้นคุณสามารถนำเข้าลงในโปรแกรมหรือ CLI ของคุณได้ 

 const { LinkedList , Queue , Stack } = require ( 'dsa.js' ) ;

สำหรับรายการโครงสร้างข้อมูลและอัลกอริธึมที่มีอยู่ทั้งหมด โปรดดูที่ index.js

คุณสมบัติ

อัลกอริธึมถือเป็นกล่องเครื่องมือที่จำเป็นสำหรับโปรแกรมเมอร์ทุกคน

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

อัลกอริทึม + โครงสร้างข้อมูล = โปรแกรม

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

เนื้อหานี้จะสอนคุณเกี่ยวกับ:

  • - ใช้กลยุทธ์เพื่อจัดการกับคำถามอัลกอริทึม ไม่ต้องติดอีกต่อไป เอาชนะการสัมภาษณ์เหล่านั้น!
  • ️ สร้างอัลกอริธึมที่มีประสิทธิภาพ เรียนรู้วิธีแบ่งปัญหาออกเป็นส่วนๆ ที่สามารถจัดการได้
  • - พัฒนาทักษะการแก้ปัญหาของคุณและเป็นนักพัฒนาที่รอบรู้ด้วยการทำความเข้าใจแนวคิดพื้นฐานของวิทยาการคอมพิวเตอร์
  • - ครอบคลุมหัวข้อสำคัญ เช่น เวลา O ขนาดใหญ่ โครงสร้างข้อมูล และอัลกอริธึมที่ต้องรู้ ใช้โครงสร้างข้อมูลมากกว่า 10 โครงสร้างตั้งแต่เริ่มต้น

มีอะไรอยู่ข้างใน

รหัสและคำอธิบายทั้งหมดมีอยู่ใน repo นี้ คุณสามารถดูลิงก์และตัวอย่างโค้ดได้จาก (โฟลเดอร์ src) อย่างไรก็ตาม ตัวอย่างโค้ดอินไลน์จะไม่ขยาย (เนื่องจากข้อจำกัด asciidoc ของ Github) แต่คุณสามารถปฏิบัติตามเส้นทางและดูการใช้งานได้

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

หัวข้อแบ่งออกเป็นสี่ประเภทหลักดังที่คุณเห็นด้านล่าง:

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

นักเก็ตวิทยาการคอมพิวเตอร์ที่ไม่มีจัมโบ้ทั้งหมด (คลิกเพื่อขยาย)

นักเก็ตวิทยาการคอมพิวเตอร์ที่ไม่มีจัมโบ้ทั้งหมด

เรียนรู้วิธีการคำนวณรันไทม์จากตัวอย่างโค้ด

การแปลบรรทัดของโค้ดเป็นจำนวนการดำเนินการโดยประมาณ

เรียนรู้วิธีเปรียบเทียบอัลกอริทึมโดยใช้สัญลักษณ์ Big O (คลิกเพื่อขยาย)

เรียนรู้วิธีเปรียบเทียบอัลกอริทึมโดยใช้สัญลักษณ์ Big O

การเปรียบเทียบอัลกอริธึมโดยใช้สัญลักษณ์ Big O

สมมติว่าคุณต้องการค้นหารายการที่ซ้ำกันในอาร์เรย์ การใช้สัญลักษณ์ Big O ทำให้เราสามารถเปรียบเทียบวิธีแก้ปัญหาต่างๆ ที่แก้ปัญหาเดียวกันได้ แต่มีความแตกต่างอย่างมากในเรื่องระยะเวลาที่ใช้ในการแก้ปัญหา

  • ทางออกที่ดีที่สุดโดยใช้แผนที่
  • การค้นหารายการที่ซ้ำกันในอาร์เรย์ (วิธีการไร้เดียงสา)
8 ตัวอย่างเพื่ออธิบายด้วยโค้ดวิธีคำนวณความซับซ้อนของเวลา (คลิกเพื่อขยาย)

8 ตัวอย่างเพื่ออธิบายด้วยโค้ดวิธีคำนวณความซับซ้อนของเวลา

ความซับซ้อนของเวลาที่พบบ่อยที่สุด

ภาพ

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

ความซับซ้อนของเวลาที่พบบ่อยที่สุด

- โครงสร้างข้อมูลเชิงเส้น

ทำความเข้าใจรายละเอียดต่างๆ ของโครงสร้างข้อมูลที่พบบ่อยที่สุด (คลิกเพื่อขยาย)

ทำความเข้าใจรายละเอียดต่างๆ ของโครงสร้างข้อมูลที่พบบ่อยที่สุด

  • อาร์เรย์: มีมาให้ในภาษาส่วนใหญ่ ดังนั้นจึงไม่ได้นำมาใช้ที่นี่ ความซับซ้อนของเวลาอาร์เรย์

  • รายการที่เชื่อมโยง: แต่ละโหนดข้อมูลมีลิงก์ไปยังโหนดถัดไป (และก่อนหน้า) รหัส | ความซับซ้อนของเวลาที่เชื่อมโยงรายการ

  • คิว: ข้อมูลจะไหลในลักษณะ "เข้าก่อนออกก่อน" (FIFO) รหัส | ความซับซ้อนของเวลาคิว

  • Stack: ข้อมูลจะไหลในลักษณะ "เข้าหลังออกก่อน" (LIFO) รหัส | ความซับซ้อนของเวลาสแต็ก

เมื่อใดควรใช้อาร์เรย์หรือรายการที่เชื่อมโยง รู้ข้อดีข้อเสีย (คลิกเพื่อขยาย)

เมื่อใดควรใช้อาร์เรย์หรือรายการที่เชื่อมโยง รู้ข้อดีข้อเสีย

ใช้อาร์เรย์เมื่อ...

  • คุณต้องเข้าถึงข้อมูลแบบสุ่มอย่างรวดเร็ว (โดยใช้ดัชนี)
  • ข้อมูลของคุณมีหลายมิติ (เช่น เมทริกซ์ เทนเซอร์)

ใช้รายการที่เชื่อมโยงเมื่อ:

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

สร้างรายการ สแต็ก และคิวตั้งแต่เริ่มต้น

สร้างโครงสร้างข้อมูลเหล่านี้ตั้งแต่เริ่มต้น:

  • รายการที่เชื่อมโยง
  • สแต็ค
  • คิว

- โครงสร้างข้อมูลที่ไม่ใช่เชิงเส้น

ทำความเข้าใจหนึ่งในโครงสร้างข้อมูลที่หลากหลายที่สุด: Hash Maps (คลิกเพื่อขยาย)

แฮชแมปส์

เรียนรู้วิธีใช้งาน Maps ประเภทต่างๆ เช่น:

  • แฮชแมป
  • ทรีแมป

นอกจากนี้ โปรดเรียนรู้ความแตกต่างระหว่างการใช้งาน Maps แบบต่างๆ:

  • HashMap ประหยัดเวลามากขึ้น TreeMap ประหยัดพื้นที่มากขึ้น
  • ความซับซ้อนในการค้นหา TreeMap คือ O(log n) ในขณะที่ HashMap ที่ได้รับการปรับปรุงโดยเฉลี่ยคือ O(1)
  • คีย์ของ HashMap อยู่ในลำดับการแทรก (หรือสุ่มขึ้นอยู่กับการใช้งาน) คีย์ของ TreeMap จะถูกจัดเรียงอยู่เสมอ
  • TreeMap นำเสนอข้อมูลทางสถิติบางอย่างฟรี เช่น รับขั้นต่ำ รับสูงสุด ค่ามัธยฐาน ค้นหาช่วงของคีย์ HashMap ไม่ได้
  • TreeMap มีการรับประกัน O(log n) เสมอ ในขณะที่ HashMap มีเวลาตัดจำหน่ายเป็น O(1) แต่ในกรณีที่ไม่ค่อยพบบ่อยของการปรับปรุงใหม่ จะใช้เวลา O(n)
รู้คุณสมบัติของกราฟและต้นไม้ (คลิกเพื่อขยาย)

รู้คุณสมบัติของกราฟและต้นไม้

กราฟ

รู้จักคุณสมบัติกราฟทั้งหมดด้วยรูปภาพและภาพประกอบมากมาย

ตัวอย่างกราฟสนามบินของสหรัฐอเมริกา

กราฟ : โหนด ข้อมูลที่สามารถมีการเชื่อมต่อหรือ ขอบ ถึงศูนย์หรือโหนดที่อยู่ติดกันมากขึ้น ต่างจากต้นไม้ตรงที่โหนดสามารถมีพาเรนต์หลายลูปได้ รหัส | ความซับซ้อนของเวลากราฟ

ต้นไม้

เรียนรู้ต้นไม้ชนิดต่างๆ และคุณสมบัติของต้นไม้

คุณสมบัติโครงสร้างข้อมูลต้นไม้

  • ต้นไม้ : โหนดข้อมูลมีโหนดที่อยู่ติดกันตั้งแต่ศูนย์ขึ้นไปหรือที่เรียกว่าโหนดลูก แต่ละโหนดสามารถมีโหนดพาเรนต์ได้เพียงโหนดเดียวเท่านั้น ไม่เช่นนั้นจะเป็นกราฟ ไม่ใช่แผนผัง รหัส | เอกสาร

    • Binary Trees : เหมือนกับต้นไม้ แต่มีลูกได้มากที่สุดเพียงสองคนเท่านั้น รหัส | เอกสาร

    • Binary Search Trees (BST): เหมือนกับต้นไม้ไบนารี่ แต่ค่าของโหนดจะคงลำดับนี้ไว้ left < parent < right รหัส | ความซับซ้อนของเวลา BST

    • AVL Trees : BST ที่สมดุลในตัวเองเพื่อเพิ่มเวลาในการค้นหาให้สูงสุด รหัส | เอกสาร AVL Tree | เอกสารการปรับสมดุลตนเองและการหมุนต้นไม้

    • ต้นไม้สีแดง-ดำ : BST ที่สมดุลในตัวเองจะหลวมกว่า AVL เพื่อเพิ่มความเร็วในการแทรกสูงสุด รหัส

ใช้แผนผังการค้นหาแบบไบนารีเพื่อการค้นหาที่รวดเร็ว

ใช้แผนผังการค้นหาแบบไบนารีเพื่อการค้นหาที่รวดเร็ว

  • เรียนรู้วิธีเพิ่ม/ลบ/อัปเดตค่าในแผนผัง: การแทรกโหนดในแผนผัง

  • จะทำให้ต้นไม้มีความสมดุลได้อย่างไร?

จาก BST ที่ไม่สมดุลไปจนถึง BST ที่สมดุล 

 1                           2
                         /   
   2        =>           1     3
    
     3

⚒ กล่องเครื่องมืออัลกอริทึม

ไม่ติดขัดในการแก้ปัญหาด้วย 7 ขั้นตอนง่ายๆ (คลิกเพื่อขยาย)

ไม่ติดขัดในการแก้ปัญหาด้วย 8 ขั้นตอนง่ายๆ

  1. เข้าใจปัญหา
  2. สร้างตัวอย่างง่ายๆ (ยังไม่มีเคส Edge)
  3. ระดมความคิดวิธีแก้ปัญหา (อัลกอริธึมโลภ, แบ่งแยกและพิชิต, การย้อนรอย, การใช้กำลังดุร้าย)
  4. ทดสอบคำตอบของคุณด้วยตัวอย่างง่ายๆ (ทางจิตใจ)
  5. เพิ่มประสิทธิภาพโซลูชัน
  6. เขียนโค้ด. ใช่ ตอนนี้คุณสามารถเขียนโค้ดได้แล้ว
  7. ทดสอบโค้ดที่คุณเขียน
  8. วิเคราะห์ความซับซ้อนทั้งพื้นที่และเวลา และตรวจสอบให้แน่ใจว่าได้เพิ่มประสิทธิภาพเพิ่มเติม

รายละเอียดทั้งหมดที่นี่

ฝึกฝนอัลกอริธึมการเรียงลำดับที่ได้รับความนิยมสูงสุด (การเรียงลำดับแบบผสาน การเรียงลำดับแบบรวดเร็ว ฯลฯ) (คลิกเพื่อขยาย)

เชี่ยวชาญอัลกอริธึมการเรียงลำดับที่ได้รับความนิยมสูงสุด

เราจะสำรวจอัลกอริธึมการเรียงลำดับที่จำเป็นสามประการ O(n^2) ซึ่งมีค่าใช้จ่ายต่ำ:

  • การเรียงลำดับฟอง รหัส | เอกสาร

  • การเรียงลำดับการแทรก รหัส | เอกสาร

  • เรียงลำดับการเลือก รหัส | เอกสาร

จากนั้นอภิปรายการอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพ O(n log n) เช่น:

  • ผสานการเรียงลำดับ รหัส | เอกสาร

  • เรียงลำดับด่วน รหัส | เอกสาร

เรียนรู้วิธีการต่างๆ ในการแก้ปัญหา เช่น การแบ่งแยกและการพิชิต การเขียนโปรแกรมแบบไดนามิก อัลกอริธึมที่โลภ และการย้อนรอย (คลิกเพื่อขยาย)

เรียนรู้แนวทางต่างๆ ในการแก้ปัญหาอัลกอริทึม

เราจะหารือเกี่ยวกับเทคนิคต่อไปนี้สำหรับการแก้ปัญหาอัลกอริทึม:

  • Greedy Algorithms: ตัดสินใจอย่างละโมบโดยใช้การวิเคราะห์พฤติกรรมเพื่อค้นหาทางออกที่ดีที่สุดโดยไม่ต้องหันกลับมามอง
  • Dynamic Programming: เทคนิคสำหรับการเร่งความเร็วอัลกอริธึมแบบเรียกซ้ำเมื่อมี ปัญหาย่อยที่ทับซ้อนกัน มากมาย ใช้ การท่องจำ เพื่อหลีกเลี่ยงการทำงานซ้ำซ้อน
  • แบ่งและพิชิต: แบ่ง ปัญหาออกเป็นชิ้นเล็กๆ พิชิต แต่ละปัญหาย่อย แล้ว รวม ผลลัพธ์เข้าด้วยกัน
  • การย้อนรอย: ค้นหาเส้นทางที่เป็นไปได้ ทั้งหมด (หรือบางส่วน) อย่างไรก็ตาม จะหยุดและ ย้อนกลับ ทันทีที่สังเกตเห็นว่าโซลูชันปัจจุบันไม่ทำงาน
  • Brute Force : สร้างวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมดและพยายามทั้งหมด (ใช้เป็นทางเลือกสุดท้ายหรือเป็นจุดเริ่มต้น)

คำถามที่พบบ่อย

ฉันจะนำสิ่งเหล่านี้ไปใช้กับงานประจำวันของฉันได้อย่างไร? (คลิกเพื่อขยาย)

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

เหตุใดคุณจึงสร้าง repo/หนังสือเล่มนี้

หนังสือเกี่ยวกับอัลกอริทึมใน JavaScript มีไม่มากนัก วัสดุนี้เติมเต็มช่องว่าง นอกจากนี้ยังเป็นการฝึกฝนที่ดี :)

มีใครที่ฉันสามารถติดต่อได้หากฉันมีคำถามเกี่ยวกับบางสิ่งเป็นพิเศษหรือไม่?

ใช่ เปิดปัญหาหรือถามคำถามใน [slack channel](https://dsajs-slackin.herokuapp.com)

หนังสือ

โครงการนี้มีอยู่ในหนังสือด้วย คุณจะได้รับ PDF ที่จัดรูปแบบอย่างสวยงามความยาว 180+ หน้า + เวอร์ชัน ePub และ Mobi

สนับสนุน

ติดต่อฉันได้ที่สถานที่ใดที่หนึ่งต่อไปนี้!

  • ทวิตเตอร์ที่ @iAmAdrianMejia
  • แชทบน dsajs.slack.com

ใบอนุญาต

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