ขั้นตอนวิธีและขั้นตอนวิธีแบ่งแยกและเอาชนะ

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง ขั้นตอนวิธีและขั้นตอนวิธีแบ่งแยกและเอาชนะ

ขั้นตอนวิธี vs. ขั้นตอนวิธีแบ่งแยกและเอาชนะ

ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้. ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีแบ่งแยกและเอาชนะ (divide and conquer; D&C) เป็นวิธีการออกแบบขั้นตอนวิธีโดยมีพื้นฐานมาจากการเรียกซ้ำ ขั้นตอนวิธีแบ่งแยกและเอาชนะทำงานโดยแบ่งปัญหาออกเป็นปัญหาย่อย 2 ส่วนหรือมากกว่านั้นแบบเวียนเกิด ปัญหาถูกแบ่งไปเรื่อย ๆ จนเล็กและง่ายพอที่จะแก้อย่างง่ายดาย หลังจากแก้ปัญหาย่อยเล็ก ๆ เหล่านั้นแล้วก็จะนำคำตอบมารวมกันขึ้นไปเรื่อย ๆ จนสุดท้ายได้คำตอบของปัญหาดั้งเดิม กลวิธีนี้เป็นพื้นฐานของขั้นตอนวิธีที่มีประสิทธิภาพจำนวนมากมาย เช่น การเรียงลำดับ (การเรียงลำดับแบบเร็ว การเรียงลำดับแบบผสาน) การคูณเลขขนาดใหญ่ (ขั้นตอนวิธีของคาราซูบา) การคำนวณการแปลงฟูรีเยไม่ต่อเนื่อง ในอีกด้าน การที่จะเข้าใจและสามารถออกแบบขั้นตอนวิธีแบ่งแยกและเอาชนะได้นั้นต้องใช้ทักษะในระดับหนึ่ง เพราะในการที่จะทำให้ขั้นตอนวิธีมีการเรียกซ้ำต่อไปได้เรื่อย ๆ ในเวลาที่ต้องการ บางครั้งอาจจะต้องหาวิธีสร้างปัญหาย่อยซึ่งซับซ้อนและยากมาก นอกจากนี้ การสร้างขั้นตอนวิธีแบ่งแยกและเอาชนะนั้นไม่มีขั้นตอนอย่างเป็นระบบ ตัวอย่างความซับซ้อนจากการวิเคราะห์หรือออกแบบขั้นตอนวิธีแบ่งแยกและเอาชนะ เช่น การคำนวณหาจำนวนฟีโบนัชชีในเวลา O(\log n) โดยใช้รูปเมทริกซ์ร่วมกับการยกกำลังโดยการยกกำลังสอง ขั้นตอนวิธีแบ่งแยกและเอาชนะ ยังรวมไปถึงขั้นตอนวิธีที่แต่ละปัญหาแบ่งออกเป็นปัญหาย่อยหลายส่วน แต่กลับใช้คำตอบหรือคำนวณคำตอบจากเพียงแค่ปัญหาย่อยเดียวเท่านั้น เช่น การค้นหาแบบทวิภาคบนแถวลำดับที่เรียงแล้ว (หรือขั้นตอนวิธีแบ่งครึ่ง สำหรับการหาคำตอบของรากในการวิเคราะห์เชิงจำนวน)Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).

การเรียกซ้ำ

การเรียกซ้ำ (recursion) หรือ การเวียนเกิด (recurrence) เป็นปรากฏการณ์ที่มีการกลับไปอ้างอิงถึงตนเอง (self-reference) หรือมีนิยามเช่นเดียวกันในลำดับต่ำลงไป ปรากฏการณ์นี้มีปรากฏในหลายด้านเช่น คณิตศาสตร์ วิทยาการคอมพิวเตอร์ ศิลปะ ดนตรี การสร้างปฏิทรรศน์ เป็นต้น.

การเรียกซ้ำและขั้นตอนวิธี · การเรียกซ้ำและขั้นตอนวิธีแบ่งแยกและเอาชนะ · ดูเพิ่มเติม »

วิทยาการคอมพิวเตอร์

วิทยาการคอมพิวเตอร์ หรือ วิทยาศาสตร์คอมพิวเตอร์ (Computer science) เป็นศาสตร์เกี่ยวกับการศึกษาค้นคว้าทฤษฎีการคำนวณสำหรับคอมพิวเตอร์ และทฤษฎีการประมวลผลสารสนเทศ ทั้งด้านซอฟต์แวร์ ฮาร์ดแวร์ และ เครือข่าย ซึ่งวิทยาการคอมพิวเตอร์นั้นประกอบด้วยหลายหัวข้อที่เกี่ยวข้องกับคอมพิวเตอร์ ตั้งแต่ระดับนามธรรม หรือความคิดเชิงทฤษฎี เช่น การวิเคราะห์และสังเคราะห์ขั้นตอนวิธี ไปจนถึงระดับรูปธรรม เช่น ทฤษฎีภาษาโปรแกรม ทฤษฎีการพัฒนาซอฟต์แวร์ ทฤษฎีฮาร์ดแวร์คอมพิวเตอร์ และ ทฤษฎีเครือข่าย ในแง่ของศาสตร์เกี่ยวกับคอมพิวเตอร์นั้น วิทยาการคอมพิวเตอร์เป็นหนึ่งในห้าสาขาวิชาคอมพิวเตอร์ ซึ่งประกอบด้วย สาขาวิทยาการคอมพิวเตอร์ หรือวิทยาศาสตรคอมพิวเตอร์ สาขาวิศวกรรมคอมพิวเตอร์ สาขาวิศวกรรมซอฟต์แวร์ สาขาเทคโนโลยีสารสนเทศ หรือเทคโนโลยีสารสนเทศและการสือสาร และ สาขาคอมพิวเตอร์ธุรกิจ หรือ ระบบสารสนเทศทางธุรก.

ขั้นตอนวิธีและวิทยาการคอมพิวเตอร์ · ขั้นตอนวิธีแบ่งแยกและเอาชนะและวิทยาการคอมพิวเตอร์ · ดูเพิ่มเติม »

ขั้นตอนวิธีการเรียงลำดับ

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการเรียงลำดับ (sorting algorithm) คือ ขั้นตอนวิธีที่จัดเรียงสมาชิกของรายการ (list) ให้เป็นไปตามรูปแบบของอันดับที่กำหนด ส่วนใหญ่อันดับที่ใช้กันคือ อันดับตัวเลข และอันดับตัวอักษร การเรียงลำดับที่มีประสิทธิภาพมีความสำคัญต่อขั้นตอนวิธีอื่นๆ (เช่น ขั้นตอนวิธีการค้นหา และ การผสาน) ซึ่งขั้นตอนวิธีเหล่านี้ต้องใช้รายการที่เรียงอย่างถูกต้อง.

ขั้นตอนวิธีและขั้นตอนวิธีการเรียงลำดับ · ขั้นตอนวิธีการเรียงลำดับและขั้นตอนวิธีแบ่งแยกและเอาชนะ · ดูเพิ่มเติม »