อัลกอริทึมการค้นหา
แนะนำใหม่| English | ความหมาย |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | การค้นหาเชิงเส้น |
| binary search/ˈbaɪnəri sɜːtʃ/ | การค้นหาแบบทวิภาค |
สองสิบบทสำหรับชื่อหนึ่งล้านชื่อ
- สมุดโทรศัพท์มีรายชื่อหนึ่งล้านชื่อ หากตรวจสอบทีละชื่อ คุณคาดว่าจะมีการเปรียบเทียบครึ่ง مليونก่อนจะพบชื่อที่ต้องการ
- เปิดตรงกลางแทน, ตัดสินใจว่าชื่ออยู่ในครึ่งไหน, แล้วทิ้งอีกครึ่งออก ทำซ้ำ你会 reaches 任何名字在二十次比较内。reach any name in twenty comparisons.
- ครึ่ง مليونเทียบกับยี่สิบไม่ใช่การประหยัดเล็กน้อย; แต่มันคือความแตกต่างระหว่างโปรแกรมที่ใช้งานได้กับโปรแกรมที่ไม่สามารถใช้งานได้อีกด้วย และมันต้องแลกมาด้วยสิ่งเดียว: รายการต้องถูกเรียงลำดับไว้ล่วงหน้า
- บทเรียนนี้เกี่ยวกับ การค้นหาเชิงเส้น (Linear search) และ การค้นหาแบบทวิภาค (Binary search), ประสิทธิภาพของแต่ละวิธี以及如何เลือก
การค้นหาเชิงเส้น
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- มันเริ่มจากจุดเริ่มต้น เปรียบเทียบแต่ละองค์ประกอบกับเป้าหมาย และหยุดเมื่อพบการจับคู่หรือถึง末尾
- มันใช้ได้กับ รายการใดก็ได้, ที่เรียงลำดับหรือไม่ และกับโครงสร้างใดๆ ที่สามารถ iterate ได้
- กรณี最差: เป้าหมายอยู่ที่末尾或缺失, ดังนั้น $n$ องค์ประกอบทั้งหมดจะถูกเปรียบเทียบ, ซึ่งเป็น $O(n)$. โดยเฉลี่ย, ประมาณครึ่งหนึ่ง
ทีละตัว, เริ่มตั้งแต่ต้น
Linear search:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การค้นหาแบบเชิงเส้นไม่ต้องการการเตรียมการและทำงานได้กับรายการใดๆ โดยในกรณีแย่ที่สุดคือ O(n)
การค้นหาแบบเชิงเส้นเป็นทางเลือกที่ดีกว่าเมื่อข้อมูลมีลักษณะ:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เมื่อไม่มีลำดับที่นำมาใช้ประโยชน์ (หรือเป็นรายการเล็ก) การค้นหาแบบเชิงเส้นจะหลีกเลี่ยงค่าใช้จ่ายในการจัดอันดับก่อนหน้า
การค้นหาแบบทวิภาค
low ← 1 ; high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN
RETURN mid
ENDIF
IF A[mid] < target THEN
low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
RETURN -1
- มันต้องการข้อมูลที่ถูก เรียงลำดับ. เปรียบเทียบองค์ประกอบตรงกลางกับเป้าหมาย: ถ้าตรงกัน, หยุด; ถ้าเป้าหมายใหญ่กว่า, ทิ้งครึ่งล่าง; ในกรณีอื่น, ทิ้งครึ่งบน
- ทุกการเปรียบเทียบ ลดครึ่ง ช่วงที่ยังต้องค้นหา, ดังนั้นจำนวนการเปรียบเทียบคือ $O(\log_2 n)$
- นี่คือเหตุผลที่ว่าข้อมูลหนึ่งล้านรายการต้องการประมาณยี่สิบการเปรียบเทียบ: $2^{20}$ เป็นมากกว่าหนึ่งล้านเล็กน้อย
อัลกอริทึมการค้นหา
แบบไบนารี减半ช่วง在每个步骤
Linear search ตรวจสอบทุกรายการ; แบบไบนารี减半已排序列表 — เปรียบเทียบน้อยกว่ามาก
ความซับซ้อนของเวลาในกรณีแย่ที่สุดของการค้นหาแบบทวิภาคีคือ:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การลดช่วงครึ่งหนึ่งในแต่ละขั้นตอนให้จำนวนการเปรียบเทียบเป็นลอการิทึม
การค้นหาแบบทวิภาคีต้องใช้การประมาณกี่ครั้งสำหรับรายการเรียงลำดับหนึ่งล้านรายการ?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\log_2(1\,000\,000) \approx 20$ — ประมาณ 20 ครั้ง
การค้นหาแบบทวิภาคีสามารถใช้ได้กับรายการใดๆ ทั้งเรียงลำดับหรือไม่เรียงลำดับ
Difficulty 1/5 · 100 coins + a small bonus on first completion today
มันตัดสินใจว่าจะตัดครึ่งใดออกโดยการเปรียบเทียบกับองค์ประกอบตรงกลาง ซึ่งมีความหมายก็ต่อเมื่อข้อมูลมีการเรียงลำดับเท่านั้น
การค้นหาแบบทวิภาคีเป็น O(log n) เพราะแต่ละการเปรียบเทียบ ____ ช่วงที่ยังต้องค้นหา
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การแบ่งครึ่ง 20 ครั้งจะลดจากหนึ่งล้านเหลือหนึ่ง นี่คือเหตุผลที่ 2^20 ซึ่งมีค่าเกินหนึ่งmillion เล็กน้อยเป็นตัวเลขที่ต้องจดจำ
ตัวอย่างทำ: วิเคราะห์การค้นหาแบบทวิภาค
- รายการที่เรียงลำดับคือ 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. วิเคราะห์การค้นหา 23
lowคือ 1,highคือ 10, ดังนั้นmidคือ 5, เก็บค่า 16. 16 น้อยกว่า 23, ดังนั้นทิ้งครึ่งล่าง:lowกลายเป็น 6low6,high10, ดังนั้นmidจึงเป็น 8, โดยเก็บ 56 ไว้ 56 มีค่าน้อยกว่า 23, ดังนั้นhighจึงกลายเป็น 7.lowคือ 6,highคือ 7, ดังนั้นmidคือ 6, เก็บค่า 23. พบแล้ว, ใช้สามการเปรียบเทียบ ในขณะที่การค้นหาเชิงเส้นจะใช้หก- แสดง
low,high,midและค่าในแต่ละขั้นตอน ส่วนใหญ่ของคะแนนอยู่ในส่วนวิเคราะห์, ไม่ใช่แค่คำตอบ
ในรายการเรียงลำดับ 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 การค้นหาแบบทวิภาคีต้องใช้การเปรียบเทียบกี่ครั้งเพื่อหาค่า 23?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
mid 5 มีค่า 16 (น้อยเกินไป), mid 8 มีค่า 56 (มากเกินไป), mid 6 มีค่า 23 การค้นหาแบบเชิงเส้นต้องใช้ถึงหกครั้ง
การเลือกระหว่างทั้งสอง
| linear | binary | |
|---|---|---|
| data must be sorted | no | yes |
| comparisons, worst case | $n$ | $\log_2 n$ |
| a million items | up to 1,000,000 | about 20 |
| เหมาะกับ | รายการที่ไม่ได้เรียงลำดับหรือรายการเล็ก, รายการลิงก์ | 数组ขนาดใหญ่ที่เรียงลำดับแล้ว, ค้นหาซ้ำๆ |
- การเรียงลำดับก่อน costing มากกว่า one linear search, ดังนั้น binary search มีประโยชน์ก็ต่อเมื่อรายการถูกเรียงลำดับอยู่แล้วหรือจะถูกค้นหาหลายครั้ง
- Binary search ยังต้องการ direct access ไปยังองค์ประกอบตรงกลาง, ซึ่ง array มีและ linked list ไม่มี
ตัวอย่างวิธีทำ: ให้เหตุผลในการเลือก
- โปรแกรมค้นหาในรายการ 50 บันทึกที่ไม่ได้เรียงลำดับเพียงครั้งเดียว การค้นหาเชิงเส้น: การเรียงลำดับรายการก่อนนั้นจะมีค่าใช้จ่ายสูงกว่า很多次เปรียบเทียบที่การค้นหาต้องการ 50 ครั้ง
- โปรแกรมค้นหาใน数组ที่เรียงลำดับของบันทึกหนึ่งล้านรายการ数千ครั้งต่อวินาที การค้นหาแบบทวิภาค: ข้อมูลเรียงลำดับอยู่แล้ว และการค้นหาแต่ละครั้งใช้ประมาณ 20 ครั้งเปรียบเทียบ แทนที่จะถึงหนึ่งล้านครั้ง
- โปรแกรมค้นหาในรายการลิงก์ การค้นหาเชิงเส้น: การค้นหาแบบทวิภาคต้องกระโดดไปที่องค์ประกอบตรงกลางโดยตรง แต่รายการลิงก์สามารถติดตามได้เฉพาะจากจุดเริ่มต้นเท่านั้น
- ชื่ออัลกอริทึม, จากนั้นคุณสมบัติของ data ที่ตัดสินใจมัน
จับคู่การค้นหาแต่ละประเภทเข้ากับข้อเท็จจริงหลัก
Difficulty 2/5 · 140 coins + a small bonus on first completion today
การค้นหาแบบทวิภาคีเร็วกว่ามาก (O(log n)) แต่ใช้ได้เฉพาะกับข้อมูลเรียงลำดับ; การค้นหาแบบเชิงเส้นทำได้ทุกที่ด้วย O(n)
เมื่อใดที่การค้นหาแบบเชิงเส้นจะเป็นทางเลือกที่ดีกว่า? เลือก ทั้งหมด ที่ถูกต้อง
Difficulty 2/5 · 140 coins + a small bonus on first completion today
กรณีสุดท้ายนี้คือจุดที่การค้นหาแบบทวิภาคีชนะ การจัดอันดับก่อนหน้ามีค่าใช้จ่ายมากกว่าการค้นหาแบบเชิงเส้นครั้งเดียว ดังนั้นจึงคุ้มค่าเมื่อมีการค้นหาหลายครั้ง
ค่าใช้จ่ายของการรักษาไฟล์ให้เรียงลำดับ
- Binary search ใช้ได้เฉพาะกับรายการที่ เรียงลำดับ, และการเรียงลำดับนั้นไม่ได้ฟรี. คำถามที่ให้คุณ justify การเลือกคือการให้คุณคิดราคา
- ถ้าข้อมูลถูกค้นหา บ่อยและแก้ไขน้อย, เรียงลำดับครั้งเดียวและทุกการค้นหาต่อไปจะเป็น $\log_2 n$. นั่นเป็นกรณีของ dictionary หรือ lookup table
- ถ้าข้อมูล เปลี่ยนแปลงตลอดเวลา, ทุกการ insert ต้องรักษาลำดับ, ซึ่ง costing การ shift ขององค์ประกอบถัดไป. การค้นหาเชิงเส้นเหนือข้อมูลที่ไม่เรียงลำดับอาจมีต้นทุนรวมที่ต่ำกว่า
- ตัวเลขทำให้ข้อโต้แย้งชัดเจน: ข้อมูลหนึ่งล้านรายการต้องการสูงสุดหนึ่งล้านการเปรียบเทียบแบบเชิงเส้น, แต่เพียง 20 แบบทวิภาค, เนื่องจาก $2^{20} > 10^6$
- ดังนั้นคำตอบที่ติดเครื่องหมายจะระบุ ทั้งสอง Half: ว่าถูกค้นหายากแค่ไหน และถูกแก้ไขบ่อยแค่ไหน
เรียงลำดับเหตุผลในการเลือกอัลกอริทึมการค้นหา
Difficulty 3/5 · 200 coins + a small bonus on first completion today
คำถาม justify ต้องการ seeing trade-off ไม่ใช่ผู้ชนะ การค้นหาแบบทวิภาคีบนรายการที่เปลี่ยนแปลงตลอดเวลาอาจมีค่าใช้จ่ายรวมมากกว่าการค้นหาแบบเชิงเส้น
คะแนนที่หลุดหายไป
- การค้นหาแบบทวิภาค ต้องใช้ข้อมูลที่เรียงลำดับแล้ว หากบอกว่าเป็น "เร็วกว่า" โดยไม่มีเงื่อนไขนี้จะไม่สามารถรับคะแนนได้
- ทุกขั้นตอนจะ ลดช่วงข้อมูลลงครึ่งหนึ่ง นี่คือที่มาของ $\log_2 n$ ให้ระบุเหตุผล ไม่ใช่แค่สัญลักษณ์ทางคณิตศาสตร์
- ทั้งสองวิธีการค้นหาต้องสามารถรายงานได้ว่า ไม่พบข้อมูล ซึ่งเป็นหน้าที่ของ
-1และเงื่อนไขการวนลูป - การค้นหาแบบทวิภาคต้องการ การเข้าถึงโดยตรง (direct access) ดังนั้นจึงใช้กับลิงก์คิสต์ไม่ได้แม้ว่ารายการนั้นจะเรียงลำดับแล้วก็ตาม
คุณเข้าใจแล้ว
- การค้นหาแบบเชิงเส้น เปรียบเทียบแต่ละองค์ประกอบตั้งแต่ต้น ใช้งานได้กับ รายการทุกชนิด และมีค่า $O(n)$
- การค้นหาแบบทวิภาค ต้องการ ข้อมูลเรียงลำดับ ที่มี การเข้าถึงโดยตรง, เปรียบเทียบองค์ประกอบตรงกลางและ แบ่งครึ่ง ช่วงเวลาในแต่ละครั้ง, ให้ $O(\log_2 n)$: ประมาณ 20 ครั้งเปรียบเทียบสำหรับ(item)หนึ่งล้านชิ้น
- ทำตามกระบวนการค้นหาแบบทวิภาคโดยแสดง
low,high,midและค่าในแต่ละขั้นตอน - เลือกจากข้อมูล: ข้อมูลที่ไม่เรียงลำดับ, ขนาดเล็ก หรือเป็นลิงก์คิสต์ หมายความว่าใช้แบบเชิงเส้น; ขนาดใหญ่, เรียงลำดับ และค้นหามักๆ หมายความว่าใช้แบบทวิภาค