การเปรียบเทียบอัลกอริทึมและ ADT ในวิชาอัลกอริทึม
แนะนำใหม่| English | ความหมาย |
|---|---|
| Big-O/bɪɡ əʊ/ | Big-O |
| time complexity/taɪm kəmˈpleksɪti/ | ความซับซ้อนของเวลา |
| space complexity/speɪs kəmˈpleksɪti/ | ความซับซ้อนของพื้นที่ |
| depth-first/depθ fɜːst/ | การค้นหาแบบลึก |
| breadth-first/bredθ fɜːst/ | การค้นหาลึกตามระดับ |
| binary tree/ˈbaɪnəri triː/ | ต้นไม้แบบสองทาง |
อัลกอริทึมที่จะอยู่รอดเกินอายุขัยของจักรวาล
- ผู้ขายของต้องเดินทางไปยัง 25 เมืองและกลับสู่บ้านด้วยเส้นทางที่สั้นที่สุด ลองจัดลำดับทุกแบบจะมีทั้งหมดประมาณ $10^{23}$ แบบ หากมีเครื่องคอมพิวเตอร์ตรวจสอบได้หนึ่งพันล้านครั้งต่อวินาที จะใช้เวลาสามล้านปี
- เพิ่มอีกหนึ่งเมืองงานจะคูณด้วย 25 นั่นไม่ใช่คอมพิวเตอร์ที่ต้องเร็วขึ้น; แต่มันเป็นแนวทางที่ไม่สามารถใช้งานได้เลย ไม่ว่าความเร็วหรือฮาร์ดแวร์ใด
- การรู้สิ่งนี้ ก่อนเขียนโปรแกรมคือสิ่งที่การวิเคราะห์ความซับซ้อนใช้ทำ มันคือความแตกต่างระหว่างการใช้เลือกอัลกอริทึมกับการค้นพบว่าอัลกอริทึมของคุณไม่สามารถขยายขนาดได้ในภายหลัง
- บทเรียนนี้คือ Big-OO สำหรับเวลาและพื้นที่,以及如何 ADTs的形状影响在其上构建的算法。
ความซับซ้อนของเวลา
- ความซับซ้อนของเวลาอธิบายว่า เวลาในการรันเพิ่มขึ้นตามขนาดข้อมูลเข้า $n$ เขียนใน Big-ONotation ซึ่งเก็บเฉพาะพจน์หลักและตัดค่าคงที่ออก
- $O(1)$ ค่าคงที่, เวลาไม่ขึ้นอยู่กับ $n$ เลย. $O(\log n)$ logaritmic, เช่น binary search. $O(n)$ linear, เช่น linear search. $O(n \log n)$, การจัดอันดับที่ดี. $O(n^2)$ quadratic, เช่น bubble และ insertion sort.
- เหตุผลที่ตัดค่าคงที่: มันถูกบดบัง. อัลกอริทึม $O(n^2)$ อาจชนะ $O(n \log n)$ สำหรับ $n = 10$, แต่ที่ $n = 10{,}000$ ไม่มีอะไรเกี่ยวกับค่าคงที่จะช่วยได้
เส้นโค้งตัดกันเพียงครั้งเดียว และหลังจากนั้นลำดับความซับซ้อนจะตัดสินทุกอย่าง
ความเร็วในการดำเนินการเพิ่มขึ้นตาม n อย่างไร
เลื่อนกราฟ n ขึ้นไปและเปรียบเทียบเส้นโค้ง: O(1) และ O(log n) จะราบเรียบเกือบคงที่, O(n) เพิ่มขึ้นอย่างต่อเนื่อง, O(n²) พุ่งสูงขึ้นอย่างรุนแรง นี่คือเหตุผลที่เราใช้ Big-O — ไม่ใช่ cronometer — ในการเปรียบเทียบอัลกอริทึมเมื่อมีอินพุตขนาดใหญ่
Big-O แบบใดอธิบาย binary search?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การลดช่วงลงครึ่งหนึ่งในแต่ละขั้นตอนคือ logarithmic — O(log n).
Big-O แบบใดอธิบาย worst case ของ bubble sort?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ลูปซ้อนสองชั้นบน n องค์ประกอบให้ O(n²).
จับคู่แต่ละอัลกอริทึมกับความซับซ้อนด้านเวลา
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Linear search คือ O(n), binary search คือ O(log n), bubble sort คือ O(n²).
ตัวอย่างฝึกหัด: ผลของการเพิ่มข้อมูลเข้าเป็นสองเท่า
- อัลกอริทึมใช้เวลา 4 วินาทีกับ 1,000 รายการ. ประมาณการเวลาสำหรับ 2,000 รายการถ้ามันคือ $O(n)$, จากนั้นถ้ามันคือ $O(n^2)$.
- $O(n)$: การเพิ่มข้อมูลเข้าเป็นสองเท่า $n$ จะทำให้เวลาเป็นสองเท่า, ดังนั้นประมาณ 8 วินาที.
- $O(n^2)$: การคูณ $n$ ด้วยสองจะทำให้เวลา เพิ่มขึ้นสี่เท่า ดังนั้นประมาณ 16 วินาที ที่ 10,000 รายการ จะใช้เวลา 100 เท่า ของเดิม ประมาณ 400 วินาที
- $O(\log n)$ จะเพิ่มเพียงขั้นตอนเดียว, และ $O(1)$ จะไม่เปลี่ยนแปลงเลย. สรุปจากลำดับความซับซ้อน ไม่ใช่จากสูตร
อัลกอริทึม O(n squared) ใช้เวลา 4 วินาทีกับ 1,000 รายการ โดยประมาณแล้วจะใช้เวลากี่วินาทีกับ 2,000 รายการ?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
การเพิ่ม n เป็นสองเท่าจะทำให้เวลาของ O(n squared) เพิ่มเป็นสี่เท่า การเพิ่ม n เป็นสองเท่าเดียวกันจะทำให้เวลาของ O(n) จาก 4 วินาทีเป็น 8 วินาที
ความซับซ้อนของพื้นที่
- ความซับซ้อนของพื้นที่คือหน่วยความจำ เพิ่มเติมที่อัลกอริทึมต้องการ นอกเหนือจากข้อมูลเข้าเอง
- Bubble และ insertion sort ใช้ $O(1)$ หน่วยความจำเพิ่มเติม: They work in place, ต้องการตัวแปรเพียงไม่กี่ตัว Merge sort ใช้ $O(n)$, เพราะสร้างอาร์เรย์เสริม
- การเรียกซ้ำใช้ stack memory สัดส่วนกับความ ลึก, เพราะทุก call ที่ยังไม่เสร็จคง frame ของมันไว้
- มักมี time and memory trade-off: การเก็บผลลัพธ์เพื่อหลีกเลี่ยงการคำนวณซ้ำ, เช่น memoisation, ซื้อความเร็วด้วยพื้นที่
สิ่งอื่นที่ตัดสินใจการเลือก
- Big-O เป็นเรื่องเกี่ยวกับ อัตราการเติบโต ไม่ใช่ความเร็วสัมบูรณ์ สำหรับ $n$ ขนาดเล็ก อัลกอริทึม $O(n^2)$ ที่เรียบง่ายอาจชนะอัลกอริทึม $O(n \log n)$ ที่ซับซ้อนกว่าได้ และเขียนได้ง่ายกว่าอย่างถูกต้อง
- ความเสถียร (Stability) มีความสำคัญเมื่อรายการมีลำดับเดิมจากอีกฟิลด์หนึ่ง ความเรียบง่าย (Simplicity) มีความสำคัญเพราะอัลกอริทึมที่มีโครงสร้างง่ายจะมีจุดที่ซ่อนบั๊กได้น้อยกว่า
- คำตอบที่ตรงไปตรงมาต่อคำถาม "เลือกอัลกอริทึมไหน" มักจะระบุทั้งอันดับและความเงื่อนไข: ตัวนี้ เพราะ $n$ มีขนาดใหญ่และข้อมูลเข้ามาโดยไม่มีการจัดลำดับ
การเรียงแบบ "in place":
Difficulty 1/5 · 100 coins + a small bonus on first completion today
อัลกอริทึม in-place (เช่น bubble และ insertion sort) จะเรียงภายใน array เดิม โดยใช้พื้นที่เสริมคงที่
ทำไม space complexity ของ bubble sort ถึงเป็น O(1) แม้ว่าจะเรียง array ที่มี n รายการ?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
มันเรียงใน-place Merge sort เป็น O(n) เพราะสร้าง array เพิ่มเติม และ recursion ต้องใช้หน่วยความจำสัดส่วนกับความลึก
ADTs inside algorithms
- Abstract data types จากหัวข้อ 10 คือเครื่องมือพื้นฐานที่อัลกอริทึมสร้างขึ้น และการเลือก ADT หนึ่งจะกำหนดลักษณะของอัลกอริทึมนั้น
- Stack ช่วยในการค้นหาแบบ depth-first: ดันเพื่อนบ้านเข้าไป แล้วดึงตัวล่าสุดออกมา ทำให้การค้นหาพุ่งลงไปในเส้นทางเดียวจนกว่าจะกลับหลัง Recursion ใช้ call stack เพื่อวัตถุประสงค์นี้โดยตรง
- Queue ช่วยในการค้นหาแบบ breadth-first: เควูเพื่อนบ้านเข้าไป แล้วดึงตัวเก่าสุดออกมา ทำให้การค้นหากระจายออกไปเป็นวงกลม ซึ่งนี่คือสิ่งที่ช่วยหาเส้นทางสั้นที่สุดในกราฟที่ไม่มีการให้น้ำหนัก
- Binary tree เก็บค่าตามลำดับ使得การค้นหาคัดออกครึ่งหนึ่งของโหนดที่เหลืออยู่ในแต่ละขั้นตอน ให้ binary search's $O(\log n)$ กับโครงสร้างที่สามารถเติบโตได้
ข้อใดเกี่ยวกับ Big-O ถูกต้อง? เลือก ทุก ข้อที่ใช้ได้
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Big-O ไม่พูดถึงวินาที; มันเกี่ยวกับการเติบโต นั่นคือเหตุผลว่าทำไมจุดตัดกับอัลกอริทึมที่ง่ายกว่าจึงเกิดขึ้นที่ขนาดเล็ก
Worked example: the same graph, two searches
- เขาวงกตจะถูกสำรวจจากทางเข้าทางหนึ่ง เปรียบเทียบการใช้ stack กับการใช้ queue
- ด้วย stack เส้นทางที่พบใหม่ล่าสุดจะถูกสำรวจถัดไป ทำให้การค้นหาพุ่งลึกไปตามเส้นทางหนึ่งจนเจอทางตัน แล้วค่อยถอยหลัง มันใช้หน่วยความจำสัดส่วนกับความลึกของเส้นทาง
- ด้วย queue เส้นทางที่พบเก่าสุดจะถูกสำรวจถัดไป ทำให้การค้นหาตรวจสอบทุกอย่างที่ห่างออกไป 1 ขั้นก่อน แล้วจึงตรวจสอบทุกอย่างที่ห่างออกไป 2 ขั้นตอน มันหาเส้นทางที่ สั้นที่สุด ได้ก่อน แต่ต้องเก็บทุกตำแหน่งในระยะปัจจุบันไว้ในหน่วยความจำ
- ระบุชื่อ ADT, ระบุชื่อลำดับการสำรวจที่เกิดขึ้น และระบุชื่อผลกระทบ
Stack (LIFO) นำไปสู่การ traversal แบบ depth-first โดยธรรมชาติ ในขณะที่ Queue (FIFO) นำไปสู่การ traverse แบบ breadth-first
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ADT ที่คุณเลือกจะกำหนดลำดับการค้นหา — stack ไปลึกก่อน, queue สำรวจระดับต่อระดับ
จับคู่แต่ละ ADT กับผลของการค้นหาที่เกิดขึ้นและผลกระทบ
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ใหม่สุดก่อน หรือเก่าสุดก่อน ตัวเลือกเดียวนี้决定了 whether การค้นหาจะลึกหรือกว้าง
คะแนนที่หลุดหายไป
- Big-O อธิบายถึง การเติบโตตามขนาดข้อมูล ไม่ใช่เวลาเป็นวินาที คำว่า "มันเร็ว" ไม่ถือเป็นคำตอบด้านความซับซ้อน
- การเพิ่มข้อมูลเป็นสองเท่าจะทำให้ $O(n)$ เพิ่มเป็นสองเท่าและ $O(n^2)$ จะเพิ่มเป็นสี่เท่า พิจารณาจากอันดับ
- ความซับซ้อนของพื้นที่ (Space complexity) คือ หน่วยความจำเพิ่มเติม ดังนั้นการเรียงลำดับแบบใน-place จึง $O(1)$ แม้ว่าจะมีขนาดอาร์เรย์เป็น $n$ ก็ตาม
- Stack ให้การค้นหาแบบลึกก่อน (depth-first), Queue ให้การค้นหาแบบกว้างก่อน (breadth-first). การจับคู่สองสิ่งนี้ให้ถูกต้องเป็นหัวใจสำคัญที่พบได้บ่อยในหลายข้อสอบ
คุณเข้าใจแล้ว
- ความซับซ้อนของเวลา (time complexity) ในรูปแบบ Big-O อธิบายถึงอัตราการเติบโตเมื่อ $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; ค่าคงที่จะถูกตัดทิ้งไปเพราะเมื่อสเกลใหญ่ขึ้น ลำดับความสำคัญ (order) จะกำหนดพฤติกรรมหลัก
- การคูณ $n$ ด้วยสองเท่า จะทำให้ $O(n)$ doubled และ $O(n^2)$ quadruples; จุดตัดกับอัลกอริทึมที่ "แย่" กว่านั้นจะมีอยู่เฉพาะสำหรับ $n$ ที่มีขนาดเล็กเท่านั้น
- ความซับซ้อนของพื้นที่ คือหน่วยความจำเพิ่มเติม: การเรียงลำดับแบบ in place เป็น $O(1)$, merge sort เป็น $O(n)$, และการเรียกซ้ำ (recursion) ต้องใช้ความลึกของ stack
- stack ให้การค้นหาแบบ ลึกก่อน (depth-first), queue ให้การค้นหาแบบ กว้างก่อน (breadth-first), และ binary tree จะลดจำนวนโหนดที่เหลืออยู่ลงครึ่งหนึ่งในแต่ละขั้นตอน