Decrease and Conquer Variations1. D

Decrease and Conquer Variations
1. Decrease by a constant: (usually by 1): instance is reduced by the same
constant on each iteration
– Insertion sort
– Graph traversal algorithms (DFS and BFS)
– Topological sorting
– Algorithms for generating permutations, subsets
2. Decrease by a constant factor (usually by half): instance is reduced by same
multiple on each iteration
– Binary search
– Bisection method
– Fake-coin problem
3. Variable size decrease: size reduction pattern varies from one iteration to the
next
– Euclid’s algorithm
– Interpolation search

ผลลัพธ์ (ไทย) 1:

ลด และพิชิตความแตกต่าง1. ลดลง โดยค่าคง: (ตามปกติแล้ว โดย 1): ตัวอย่างจะลดลง ด้วยเหมือนกันค่าคงที่ในแต่ละคำซ้ำ-เรียงลำดับแบบแทรก-กราฟอัลกอริทึมข้าม (DFS และ bfs แยก)– การเรียงลำดับ topological-อัลกอริทึมสำหรับการสร้างสับ ชุดย่อย2. ลดลง โดยปัจจัยคง (ปกติโดยครึ่ง): ตัวอย่างจะลดลง ด้วยเหมือนกันหลายในเนื่อง– ค้นหาไบนารี– วิธีการ bisection– ปัญหาเหรียญปลอม3. ตัวแปรขนาดลดลง: รูปแบบลดขนาดตั้งแต่หนึ่งเกิดซ้ำไปถัดไป-อัลกอริทึมยุคลิด-ค้นหาแทรกแทรง

ผลลัพธ์ (ไทย) 2:

ลดและพิชิตการเปลี่ยนแปลง
1 ลดลงอย่างต่อเนื่อง (โดยปกติ 1): ตัวอย่างเช่นจะลดลงเหมือนกัน
อย่างต่อเนื่องในแต่ละซ้ำ
- จัดเรียงแทรก
- กราฟขั้นตอนวิธีการสำรวจเส้นทาง (DFS และ BFS)
- การเรียงลำดับทอพอโลยี
- อัลกอริทึมสำหรับการสร้างพีชคณิต, ย่อย
2 ลดลงโดยปัจจัยคงที่ (มักจะลงครึ่งหนึ่ง) จะลดลงเช่นเดียวกันโดย
หลายคนในแต่ละซ้ำ
- ค้นหา Binary
- วิธีการแยกเป็นสองส่วน
- ปัญหาปลอมเหรียญ
3 ลดขนาดการศึกษา: รูปแบบการลดขนาดที่แตกต่างกันจากที่หนึ่งไปยังย้ำ
ต่อไป
- อัลกอริทึมของยุคลิด
- ค้นหาการแก้ไข

ผลลัพธ์ (ไทย) 3:

ลดลงและพิชิตการเปลี่ยนแปลง
1 ลดลงคงที่ : ( มักจะโดย 1 ) : อินสแตนซ์ลดลงเหมือนกัน

คงที่ในแต่ละ iteration ) การเรียงลำดับแบบแทรก
–กราฟหรืออัลกอริทึม ( DFS และ BFS )
-
- ขั้นตอนวิธีสำหรับการสร้างรูปแบบการเรียงลำดับส่วนย่อย
2 ลดลง โดยปัจจัยคงที่ ( มักจะโดยครึ่ง ) : อินสแตนซ์ลดลงหลายในแต่ละซ้ำเหมือนกัน


และการค้นหาแบบทวิภาค- วิธี bisection และปัญหาปลอมเหรียญ

3 . ลดขนาดของตัวแปร : รูปแบบการลดขนาดแตกต่างกันจากหนึ่งซ้ำไป


ต่อไป เพื่อการค้นหาสำหรับขั้นตอนวิธียูคลิด