เร็วกว่าเบราว์เซอร์!
9 ความสัมพันธ์: กองซ้อนการเรียกซ้ำวิทยาการคอมพิวเตอร์ขั้นตอนวิธีขั้นตอนวิธีการค้นหาขั้นตอนวิธีแบ่งแยกและเอาชนะคอมไพเลอร์ตารางแฮชแถวลำดับ
กองซ้อน
กองซ้อน หรือ สแต็ก หมายถึง แบบชนิดข้อมูลนามธรรมที่มีลักษณะการเรียงลำดับข้อมูล ในการเข้า-ออกในลักษณะเข้าก่อนออกทีหลัง FILO (First In Last Out) กล่าวคือข้อมูลที่เข้าใหม่ๆจะได้ออกก่อน คล้ายกองที่ทับถมซึ่งสิ่งที่เข้ามาใหม่จะอยู่ด้านบนๆ จึงเรียกว่า กองซ้อน (stack) กองซ้อนมีการดำเนินการพื้นฐานเพียง 3 อย่าง ได้แก่ push, pop และ top กองซ้อน โดยที่การ push คือการใส่ข้อมูลลงไปในกองซ้อน ซึ่งจะกระทำได้หากกองซ้อนยังว่างอยู่ หากไม่มีที่ว่างในกองซ้อนเหลืออยู่หรือกองซ้อนเต็ม กองซ้อนนั้นจะอยู่ในสภาวะล้นหรือมากเกินเก็บ (overflow) การ pop คือการนำข้อมูลออกจากส่วนบนสุดของกองซ้อน นอกจากนี้ การ pop จะเผยข้อมูลที่ถูกผิดอยู่ก่อนหน้า หรือทำให้กองซ้อนว่างได้ แต่ถ้ากองซ้อนนั้นว่างอยู่แล้ว การ pop จะทำให้อยู่ในสภาวะน้อยเกินเก็บ (underflow) (นั่นคือ ไม่มีข้อมูลให้นำออกแล้ว) การ top กองซ้อน จะดึงข้อมูลที่อยู่บนสุดและส่งค่านั้นให้ผู้ใช้โดยที่ไม่ได้ลบทิ้งไป การ top กองซ้อนอาจทำให้กองซ้อนอยู่ในสภาวะน้อยเกินเก็บได้เช่นกัน หากกองซ้อนว่างอยู่แล้ว กองซ้อนจึงเป็นวิธีการจัดการเข้า-ออกของข้อมูลอีกแบบหนึ่ง เป็นโครงสร้างข้อมูลที่นำมาใช้ในการทำงานของโปรแกรมคอมพิวเตอร์หลายประการ อาทิการสร้าง subroutine การเรียงลำดับนิพจน์ ฯลฯ.
ใหม่!!: การค้นหาแบบทวิภาคและกองซ้อน · ดูเพิ่มเติม »
การเรียกซ้ำ
การเรียกซ้ำ (recursion) หรือ การเวียนเกิด (recurrence) เป็นปรากฏการณ์ที่มีการกลับไปอ้างอิงถึงตนเอง (self-reference) หรือมีนิยามเช่นเดียวกันในลำดับต่ำลงไป ปรากฏการณ์นี้มีปรากฏในหลายด้านเช่น คณิตศาสตร์ วิทยาการคอมพิวเตอร์ ศิลปะ ดนตรี การสร้างปฏิทรรศน์ เป็นต้น.
ใหม่!!: การค้นหาแบบทวิภาคและการเรียกซ้ำ · ดูเพิ่มเติม »
วิทยาการคอมพิวเตอร์
วิทยาการคอมพิวเตอร์ หรือ วิทยาศาสตร์คอมพิวเตอร์ (Computer science) เป็นศาสตร์เกี่ยวกับการศึกษาค้นคว้าทฤษฎีการคำนวณสำหรับคอมพิวเตอร์ และทฤษฎีการประมวลผลสารสนเทศ ทั้งด้านซอฟต์แวร์ ฮาร์ดแวร์ และ เครือข่าย ซึ่งวิทยาการคอมพิวเตอร์นั้นประกอบด้วยหลายหัวข้อที่เกี่ยวข้องกับคอมพิวเตอร์ ตั้งแต่ระดับนามธรรม หรือความคิดเชิงทฤษฎี เช่น การวิเคราะห์และสังเคราะห์ขั้นตอนวิธี ไปจนถึงระดับรูปธรรม เช่น ทฤษฎีภาษาโปรแกรม ทฤษฎีการพัฒนาซอฟต์แวร์ ทฤษฎีฮาร์ดแวร์คอมพิวเตอร์ และ ทฤษฎีเครือข่าย ในแง่ของศาสตร์เกี่ยวกับคอมพิวเตอร์นั้น วิทยาการคอมพิวเตอร์เป็นหนึ่งในห้าสาขาวิชาคอมพิวเตอร์ ซึ่งประกอบด้วย สาขาวิทยาการคอมพิวเตอร์ หรือวิทยาศาสตรคอมพิวเตอร์ สาขาวิศวกรรมคอมพิวเตอร์ สาขาวิศวกรรมซอฟต์แวร์ สาขาเทคโนโลยีสารสนเทศ หรือเทคโนโลยีสารสนเทศและการสือสาร และ สาขาคอมพิวเตอร์ธุรกิจ หรือ ระบบสารสนเทศทางธุรก.
ใหม่!!: การค้นหาแบบทวิภาคและวิทยาการคอมพิวเตอร์ · ดูเพิ่มเติม »
ขั้นตอนวิธี
ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้.
ใหม่!!: การค้นหาแบบทวิภาคและขั้นตอนวิธี · ดูเพิ่มเติม »
ขั้นตอนวิธีการค้นหา
ขั้นตอนวิธีการสืบค้น (search algorithm) เป็นขั้นตอนวิธีสำหรับการค้นหารายการที่มีคุณสมบัติตามระบุจากรายการทั้งหมด รายการที่ต้องการอาจเก็บเป็นเอกเทศเช่น ระเบียน (records) ในฐานข้อมูล หรืออาจเป็นอิลีเมนต์ของพื้นที่การค้นหาที่นิยามโดยสูตรคณิตศาสตร์หรือกระบวนการ เช่นรากของสมการที่มีตัวแปรเป็นเลขจำนวนเต็ม หรือทั้งสองวิธีรวมกัน เช่น วงจรแฮมิโตเนียนของกราฟ เป็นต้น หมวดหมู่:ขั้นตอนวิธีการค้นหา.
ใหม่!!: การค้นหาแบบทวิภาคและขั้นตอนวิธีการค้นหา · ดูเพิ่มเติม »
ขั้นตอนวิธีแบ่งแยกและเอาชนะ
ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีแบ่งแยกและเอาชนะ (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).
ใหม่!!: การค้นหาแบบทวิภาคและขั้นตอนวิธีแบ่งแยกและเอาชนะ · ดูเพิ่มเติม »
คอมไพเลอร์
คอมไพเลอร์ (compiler) หรือ โปรแกรมแปลโปรแกรม, ตัวแปลโปรแกรม เป็น โปรแกรมคอมพิวเตอร์ที่ทำหน้าแปลงชุดคำสั่งภาษาคอมพิวเตอร์หนึ่ง ไปเป็นชุดคำสั่งที่มีความหมายเดียวกัน ในภาษาคอมพิวเตอร์อื่น คอมไพเลอร์ส่วนใหญ่ จะทำการแปล รหัสต้นฉบับ (source code) ที่เขียนในภาษาระดับสูง เป็น ภาษาระดับต่ำ หรือภาษาเครื่อง ซึ่งคอมพิวเตอร์สามารถที่จะทำงานได้โดยตรง อย่างไรก็ตาม การแปลจากภาษาระดับต่ำเป็นภาษาระดับสูง ก็เป็นไปได้ โดยใช้ตัวแปลโปรแกรมย้อนกลับ (decompiler) รูปแสดงขั้นตอนการทำงานของตัวแปลโปรแกรม ผลลัพธ์ของการแปลโปรแกรม (คอมไพล์) โดยทั่วไป ที่เรียกว่า ออบเจกต์โค้ด จะประกอบด้วยภาษาเครื่อง (Machine code) ที่เต็มไปด้วยข้อมูลเกี่ยวกับชื่อและสถานที่ของแต่ละจุด และการเรียกใช้วัตถุภายนอก (Link object) (สำหรับฟังก์ชันที่ไม่ได้อยู่ใน อ็อบเจกต์) สำหรับเครื่องมือที่เราใช้รวม อ็อบเจกต์เข้าด้วยกัน จะเรียกว่าโปรแกรมเชื่อมโยงเพื่อที่ผลลัพธ์ที่ออกมาในขั้นสุดท้าย เป็นไฟล์ที่ผู้ใช้งานทั่วไปสามารถใช้งานได้สะดวก คอมไพเลอร์ที่สมบูรณ์ตัวแรก คือ ภาษาฟอร์แทรน (FORTRAN) ของ ไอบีเอ็ม ในปี ค.ศ. 1957 และ ภาษาโคบอล (COBOL) ก็เป็นคอมไพเลอร์ตัวแรก ๆ ที่สามารถทำงานได้บนหลาย ๆ สถาปัตยกรรมทางคอมพิวเตอร์ การพัฒนาตัวแปลภาษารุดหน้าอย่างรวดเร็ว และเริ่มมีรูปแบบที่ชัดเจนยิ่งขึ้นต่อมา ในช่วงทศวรรษ 1960.
ใหม่!!: การค้นหาแบบทวิภาคและคอมไพเลอร์ · ดูเพิ่มเติม »
ตารางแฮช
ตารางแฮช เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแ.
ใหม่!!: การค้นหาแบบทวิภาคและตารางแฮช · ดูเพิ่มเติม »
แถวลำดับ
ในวิทยาการคอมพิวเตอร์ แถวลำดับ (array) คือโครงสร้างข้อมูลที่เป็นรายการอย่างหนึ่ง ข้อมูล (value) จะถูกเก็บบนหน่วยความจำคอมพิวเตอร์ แบบอยู่ติดกันไปเรื่อย ๆ การเข้าถึงข้อมูลสามารถกระทำได้ผ่านดัชนี (index) หรืออาจเรียกว่า คีย์ โดยดัชนีจะเป็นจำนวนเต็มซึ่งบอกถึงลำดับที่ของข้อมูลในแถวลำดับ นอกจากนี้ ค่าของดัชนียังไปจับคู่กับที่อยู่หน่วยความจำ ผ่านสูตรคณิตศาสตร์ ทำให้สามารถเข้าถึงข้อมูลได้ ตัวอย่างเช่นแถวลำดับที่มีข้อมูล 10 ตัว โดยมีดัชนีตั้งแต่ 0 ถึง 9 สมมุติให้ข้อมูลแต่ละตัวใช้หน่วยความจำ 4 ไบต์ และแถวลำดับนี้มีที่อยู่ในหน่วยความจำคือ 2000 จะได้ว่าที่อยู่หน่วยความจำของข้อมูลตัวที่ i คือ 2000 + 4i แถวลำดับยังสามารถขยายมิติไปเป็นสองมิติหรือมากกว่านั้นได้ เนื่องจากรูปแบบของแถวลำดับสองมิติมีรูปร่างเป็นตาราง คล้ายกับเมตริกซ์ บางทีจึงอาจเรียกแถวลำดับสองมิติว่าเมตริกซ์หรือตาราง (สำหรับตารางโดยส่วนมากแล้วจะหมายความถึงตาราง lookup) เช่นเดียวกับแถวลำดับมิติเดียวที่บางครั้งก็อาจเรียกว่าเวกเตอร์หรือทูเพิล แถวลำดับถือได้ว่าเป็นโครงสร้างข้อมูลที่ถือกำเนิดขึ้นพร้อม ๆ กับการเขียนโปรแกรม และสำคัญมากในการเขียนโปรแกรมเช่นเดียวกัน และแทบจะไม่มีโปรแกรมใดเลยที่ไม่ใช้แถวลำดับ โดยแถวลำดับนี้ยังนำไปอิมพลีเมนต์โครงสร้างข้อมูลอื่นอีกมากมายเช่นรายการหรือสายอักขระ แม้แต่หน่วยเก็บข้อมูลที่มีที่อยู่หน่วยความจำก็อาจจะมองหน่วยเก็บข้อมูลเป็นแถวลำดับขนาดยักษ์ก็ได้.
ใหม่!!: การค้นหาแบบทวิภาคและแถวลำดับ · ดูเพิ่มเติม »
