โครงสร้างข้อมูลและอัลกอริทึม: ชุดสรุปเร่งรัด

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 6 ข้อ พร้อมเฉลยละเอียดไว้ท้ายเล่ม

โจทย์ใหม่กลับไปที่รายวิชา

ในหน้าต่างพิมพ์ ให้เลือก “บันทึกเป็น PDF” เพื่อเก็บสำเนาไว้ในอุปกรณ์ของคุณ

1สูตรและวิธีทำ

ทฤษฎีกราฟ

เล็มมาการจับมือ
Σ deg(v) = 2|E|
กราฟบริบูรณ์
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
กราฟปรกติ
|E| = n·k/2
ต้นไม้และป่า
|E| = n − 1, |E| = n − c
ใบของต้นไม้
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
ออยเลอร์
วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
วงจรแฮมิลตันใน Kn
(n − 1)!/2
การปรับค่าของไดก์สตรา
d(v) = min(d(v), d(u) + w(u, v))
วอล์กความยาว L
(Mᴸ)ij

วิธีการ

  1. เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
  2. สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
  3. สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
  4. สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
  5. สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)

2โจทย์ฝึก

1.อัลกอริทึมและความซับซ้อนปานกลาง

ความซับซ้อนเชิงเวลาของ for i = 1 to n: (j = 1; while j < n: j = j × 2) คือเท่าใด

  1. AO(n)
  2. BO(n²)
  3. CO(n log n)
  4. DO(log n)
2.อัลกอริทึมและความซับซ้อนยาก

ปัญหาหนึ่งเป็น NP-complete ถ้ามัน

  1. Aแก้ได้ในเวลาพหุนาม
  2. Bอยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม
  3. Cอยู่นอก NP แต่ยากกว่าทุกปัญหา NP เช่น ปัญหาการหยุด
  4. Dแก้ไม่ได้เลย
3.โครงสร้างข้อมูลปานกลาง

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

  1. Aการค้นหาด้วยคำนำหน้า เช่น autocomplete
  2. Bการเก็บเมทริกซ์
  3. Cการเรียงตัวเลข
  4. Dการหาเส้นทางสั้นที่สุด
4.โครงสร้างข้อมูลยาก

เหตุใดฐานข้อมูลจึงมักใช้ B+ tree แทน B-tree ธรรมดาสำหรับดัชนี

  1. AB+ tree เก็บข้อมูลที่รากเท่านั้น
  2. Bระเบียนทั้งหมดอยู่ในใบที่เชื่อมกัน ทำให้สแกนช่วงได้มีประสิทธิภาพ
  3. CB+ tree ไม่จำเป็นต้องสมดุล
  4. DB+ tree ใช้โหนดภายในแบบทวิภาค ซึ่งลดจำนวนการอ่านดิสก์
5.ทฤษฎีกราฟปานกลาง

ต้นไม้มี 3 จุดยอดดีกรี 3, 4 จุดยอดดีกรี 4, 4 จุดยอดดีกรี 5 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L

3 × deg 34 × deg 44 × deg 5
L =
6.ทฤษฎีกราฟยาก
749111616314ABCDEFG

จงหาน้ำหนักรวม W ของต้นไม้ทอดข้ามค่าน้อยที่สุดของกราฟถ่วงน้ำหนัก

|V| = 7|E| = 9
W =

3สารละลาย

1.อัลกอริทึมและความซับซ้อน

คำตอบ: C · O(n log n)

เหตุผลที่เป็นคำตอบนี้

ลูปชั้นในทำงานประมาณ log₂ n ครั้งสำหรับแต่ละรอบของลูปชั้นนอก n รอบ ได้ O(n log n)

คำตอบ

C · O(n log n)
2.อัลกอริทึมและความซับซ้อน

คำตอบ: B · อยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม

เหตุผลที่เป็นคำตอบนี้

ปัญหา NP-complete เป็นปัญหาที่ยากที่สุดใน NP ถ้ามีอัลกอริทึมพหุนามสำหรับปัญหาหนึ่ง ก็จะมีสำหรับทั้ง NP

คำตอบ

B · อยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม
3.โครงสร้างข้อมูล

คำตอบ: A · การค้นหาด้วยคำนำหน้า เช่น autocomplete

เหตุผลที่เป็นคำตอบนี้

Trie เก็บสตริงด้วยอักขระตามเส้นทาง การค้นหาและคำถามคำนำหน้าจึงใช้เวลาแปรผันตามความยาวคีย์

คำตอบ

A · การค้นหาด้วยคำนำหน้า เช่น autocomplete
4.โครงสร้างข้อมูล

คำตอบ: B · ระเบียนทั้งหมดอยู่ในใบที่เชื่อมกัน ทำให้สแกนช่วงได้มีประสิทธิภาพ

เหตุผลที่เป็นคำตอบนี้

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

คำตอบ

B · ระเบียนทั้งหมดอยู่ในใบที่เชื่อมกัน ทำให้สแกนช่วงได้มีประสิทธิภาพ
5.ทฤษฎีกราฟ

คำตอบ: L = 25

ออยเลอร์ แฮมิลตัน และต้นไม้: กราฟเชื่อมโยงมีวงจรออยเลอร์ (ผ่านทุกเส้นเชื่อมครั้งเดียวและกลับจุดเริ่มต้น) เมื่อทุกจุดยอดมีดีกรีคู่ และมีทางเดินออยเลอร์ที่ไม่ใช่วงจรเมื่อมีจุดยอดดีกรีคี่พอดีสองจุด ทางเดินนั้นไปจากจุดยอดคี่จุดหนึ่งถึงอีกจุดหนึ่ง วงจรแฮมิลตันผ่านทุกจุดยอดครั้งเดียว Kn มีวงจรแบบนี้ (n − 1)!/2 วงจร ต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม และกราฟเชื่อมโยงที่มี m เส้นเชื่อมจะเหลือต้นไม้ทอดข้ามหลังเอาเส้นเชื่อมออก m − n + 1 เส้น

เล็มมาการจับมือสำหรับต้นไม้

L + 45 = 2(L + 11) − 2
L = 25

คำตอบ

L = 25

ทางลัด: L = 2 + Σ (d − 2) ของจุดยอดที่มีดีกรี d ≥ 3

6.ทฤษฎีกราฟ

คำตอบ: W = 32

เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้าม: ขั้นตอนวิธีของไดก์สตรายืนยันหนึ่งจุดยอดต่อรอบ: จุดยอดที่ยังไม่ยืนยันซึ่งมีระยะทางชั่วคราวน้อยที่สุด ระยะทางของมันเป็นค่าสุดท้ายแล้ว และเพื่อนบ้าน v ทุกจุดได้ d(v) = min(d(v), d(u) + w(u, v)) ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเลือกเส้นเชื่อมจากเบาไปหนักและข้ามเส้นที่ทำให้เกิดวัฏจักร ขั้นตอนวิธีของพริมขยายต้นไม้หนึ่งต้นจากจุดยอดเริ่มต้นโดยเพิ่มเส้นเชื่อมที่เบาที่สุดที่ออกจากต้นไม้เสมอ ต้นไม้ทอดข้ามที่มี n จุดยอดมี n − 1 เส้นเชื่อม

ขั้นตอนวิธีของครัสคัล

CE (1): เลือก
GD (3): เลือก
AC (4): เลือก
EF (6): เลือก
AB (7): เลือก
BC (9): ข้าม ทำให้เกิดวัฏจักร
BD (11): เลือก

น้ำหนักรวม

W = 1 + 3 + 4 + 6 + 7 + 11 = 32

คำตอบ

W = 32

ExamProblems · examproblems.com/courses/data-structures-and-algorithms