การเข้าถึงโดยสุ่มและสัญกรณ์โอใหญ่

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

ความแตกต่างระหว่าง การเข้าถึงโดยสุ่มและสัญกรณ์โอใหญ่

การเข้าถึงโดยสุ่ม vs. สัญกรณ์โอใหญ่

การเข้าถึงโดยสุ่ม เปรียบเทียบกับการเข้าถึงเชิงเส้น ในวิทยาการคอมพิวเตอร์ การเข้าถึงโดยสุ่ม (random access) หรือ การเข้าถึงโดยตรง (direct access) คือความสามารถในการเข้าถึงข้อมูลในลำดับภายในเวลาที่เท่าๆกันสำหรับข้อมูลตัวใด ๆ ก็ตาม เวลาในการเข้าถึงข้อมูลนี้ไม่ขึ้นกับกับขนาดของลำดับด้วย ตัวอย่างของการเข้าถึงโดยสุ่มคือการอ่านข้อมูลจากแผ่นซีดี ซึ่งสามารถอ่านข้อมูลตำแหน่งใดๆได้ทันที การเข้าถึงข้อมูลที่ตรงกันข้ามกับการเข้าถึงโดยสุ่มคือการเข้าถึงเชิงเส้น ซึ่งข้อมูลที่อยู่ไกลกว่าจะเสียเวลาในการเข้าถึงข้อมูลมากกว่า ตัวอย่างเช่นการอ่านข้อมูลจากตลับเทป ซึ่งต้องมีกรอเทปไปยังตำแหน่งที่ต้องการอ่านข้อมูล สำหรับโครงสร้างข้อมูล ความสามารถในการเข้าถึงโดยสุ่มคือความสามารถในการเข้าถึงรายการได้ภายในเวลาคงที่ หรือ O(1) ซึ่งโครงสร้างข้อมูลที่เรียบง่ายที่สุดที่มีความสามารถนี้ก็คือแถวลำดับ โครงสร้างข้อมูลที่เหลือที่มีความสามารถนี้ โดยมากแล้วก็จะมาจากการดัดแปลงแถวลำดับ เช่น แถวลำดับพลวัต อย่างไรก็ตาม การมีความสามารถในการเข้าถึงโดยสุ่มก็ความหมายอีกนัยหนึ่งว่าที่อยู่ของหน่วยความจำต้องเรียงกันแบบมีแบบแผน ดังนั้นจึงทำให้โครงสร้างข้อมูลทั้งหลายที่มีความสามารถนี้ไม่สามารถเพิ่มข้อมูลกลางรายการได้อย่างมีประสิทธิภาพ บางโครงสร้างข้อมูลเช่นรายการโยงแลกความสามารถในการเข้าถึงแบบสุ่มด้วยความสามารถในการเพิ่มและลบข้อมูลกลางรายการแทน ความสามารถในการเข้าถึงโดยสุ่มมีความสำคัญมาก มีขั้นตอนวิธีมากมายที่ใช้ประโยชน์จากโครงสร้างข้อมูลที่มีการเข้าถึงข้อมูลโดยสุ่ม เช่น การค้นหาแบบทวิภาค ขั้นตอนวิธีการเรียงลำดับ ตะแกรงเอราทอสเทนีส เป็นต้น. ตัวอย่างของสัญกรณ์โอใหญ่ โดย ''f''(''x'') ∈ O(''g''(''x'')) ซึ่งหมายความว่ามี ''c'' > 0 (เช่น ''c''.

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

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

การเข้าถึงโดยสุ่มและวิทยาการคอมพิวเตอร์ · วิทยาการคอมพิวเตอร์และสัญกรณ์โอใหญ่ · ดูเพิ่มเติม »

สัญกรณ์โอใหญ่

ตัวอย่างของสัญกรณ์โอใหญ่ โดย ''f''(''x'') ∈ O(''g''(''x'')) ซึ่งหมายความว่ามี ''c'' > 0 (เช่น ''c''.

การเข้าถึงโดยสุ่มและสัญกรณ์โอใหญ่ · สัญกรณ์โอใหญ่และสัญกรณ์โอใหญ่ · ดูเพิ่มเติม »

ขั้นตอนวิธี

ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้.

การเข้าถึงโดยสุ่มและขั้นตอนวิธี · ขั้นตอนวิธีและสัญกรณ์โอใหญ่ · ดูเพิ่มเติม »

โครงสร้างข้อมูล

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

การเข้าถึงโดยสุ่มและโครงสร้างข้อมูล · สัญกรณ์โอใหญ่และโครงสร้างข้อมูล · ดูเพิ่มเติม »