>> DOUG LLOYD: ดังนั้นใน CS50 เราได้เรียนรู้เกี่ยวกับ ความหลากหลายของการเรียงลำดับและการค้นหา
อัลกอริทึม
และบางครั้งก็อาจจะ เล็ก ๆ น้อย ๆ เพื่อให้ยุ่งยาก
ติดตามสิ่งที่ขั้นตอนวิธีการทำในสิ่งที่
เราได้จริงๆเท่านั้น พื้นผิวที่ไ​​ขมันต่ำเกินไป
มีการค้นหาอื่น ๆ อีกมากมาย ขั้นตอนวิธีการและการเรียงลำดับ
ดังนั้นในวิดีโอนี้ขอ เพียงแค่ใช้เวลาไม่กี่นาที
และพยายามสกัดแต่ละขั้นตอนวิธี ลงไปที่องค์ประกอบหลักของมัน
เพื่อให้คุณสามารถจำได้มากที่สุด ข้อมูลที่สำคัญเกี่ยวกับพวกเขา
และสามารถที่จะเป็นปล้อง ความแตกต่างในกรณีที่จำเป็น
>> ประการแรกคือการจัดเรียงการเลือก
ความคิดพื้นฐานหลังการเรียงลำดับการเลือก คือการหาองค์ประกอบที่ไม่ได้เรียงลำดับที่เล็กที่สุด
ในอาร์เรย์และสลับกับ ไม่ได้เรียงลำดับองค์ประกอบแรกของอาร์เรย์ที่
เราบอกว่าเลวร้ายที่สุดกรณี เวลาทำงานที่เป็นกำลังสอง n
และถ้าคุณต้องการที่จะจำว่าทำไมใช้เวลา ดูที่วิดีโอการเรียงลำดับการเลือก
เวลาทำงานกรณีที่ดีที่สุด นอกจากนี้ยังมี n ยกกำลังสอง
>> การจัดเรียงฟองคิดที่อยู่เบื้องหลังว่า หนึ่งคือการแลกเปลี่ยนคู่ที่อยู่ติดกัน
เพื่อให้เป็นกุญแจสำคัญที่จะช่วยให้คุณ จำได้ว่าแตกต่างกันที่นี่
เลือกการเรียงลำดับมีเพื่อให้ห่างไกล หาฟอง smallest--
การจัดเรียงเป็นคู่ที่อยู่ติดกันแลกเปลี่ยน
เราสลับคู่ที่อยู่ติดกัน ขององค์ประกอบถ้าพวกเขา
มีการออกคำสั่งที่มีประสิทธิภาพ องค์ประกอบฟองขนาดใหญ่ไปทางขวา
และในเวลาเดียวกันก็ยังเริ่มต้น ที่จะย้ายองค์ประกอบขนาดเล็กไปทางซ้าย
ในกรณีที่เลวร้ายที่สุดกรณีเวลาทำงาน ของการจัดเรียงฟองเป็นกำลังสอง n
เวลาทำงานกรณีที่ดีที่สุด ของการจัดเรียงฟองเป็น n
เพราะในสถานการณ์ที่ เราไม่ actually--
เราอาจจะไม่จำเป็นต้อง ทำให้การแลกเปลี่ยนใด ๆ
เราจะต้องทำอย่างใดอย่างหนึ่ง ผ่านทุกองค์ประกอบ n
>> ในการจัดเรียงแทรกที่ ความคิดพื้นฐานที่นี่จะขยับ
นั่นเป็นคำหลักสำหรับการจัดเรียงแทรก
เรากำลังจะก้าวผ่านครั้งเดียว อาร์เรย์จากซ้ายไปขวา
และในขณะที่เราทำเรา จะเปลี่ยนองค์ประกอบ
เราได้เห็นแล้วจะทำให้ห้อง คนเล็กที่ต้องการเพื่อให้พอดีกับที่ใดที่หนึ่ง
กลับมาอยู่ในส่วนที่เรียง
ดังนั้นเราจึงสร้างแถวเรียงหนึ่ง องค์ประกอบที่เวลาจากซ้ายไปขวา
และเราเปลี่ยนสิ่งที่จะทำให้ห้อง
เวลาทำงานที่เลวร้ายที่สุดกรณีของ จัดเรียงแทรกเป็นสี่เหลี่ยม n
ที่ดีที่สุดของกรณีที่เวลาทำงานเป็น n
>> ผสาน sort-- คำหลัก ที่นี่จะแยกและผสาน
เราแยกมากมายเต็มไม่ว่าจะเป็น มันหกองค์ประกอบแปดองค์ประกอบ
10,000 elements-- เราแยกมัน ลงครึ่งหนึ่งครึ่งหนึ่งครึ่งหนึ่ง
จนกว่าเราจะได้อยู่ภายใต้การอาร์เรย์ n หนึ่งขององค์ประกอบอาร์เรย์
ชุดของ n หนึ่งอาร์เรย์องค์ประกอบ
ดังนั้นเราจึงเริ่มต้นด้วยหนึ่ง อาร์เรย์ 1,000 องค์ประกอบ
และเราได้รับไปยังจุดที่พวกเรา มี 1,000 อาร์เรย์หนึ่งองค์ประกอบ
จากนั้นเราก็เริ่มที่จะผสานอาร์เรย์ย่อยเหล่านั้น กลับมารวมกันในลำดับที่ถูกต้อง
ดังนั้นเราจึงใช้เวลาสองอาร์เรย์หนึ่งองค์ประกอบ และสร้างอาร์เรย์สององค์ประกอบ
เราใช้เวลาสองอาร์เรย์สององค์ประกอบ และสร้างอาร์เรย์สี่องค์ประกอบ
และอื่น ๆ และอื่น ๆ จนเราได้ สร้างขึ้นมาใหม่อีกครั้งหนึ่งอาร์เรย์องค์ประกอบ n
>> เวลาทำงานที่เลวร้ายที่สุดกรณีของ ผสานการจัดเรียงเป็นครั้ง n log n
เรามีองค์ประกอบ n แต่ กระบวนการ recombining นี้
ใช้เวลา log n ขั้นตอนที่จะได้รับ กลับไปมากมายเต็ม
กรณีที่ดีที่สุดเวลาทำงานยังเป็นบันทึกของ n n เนื่องจากกระบวนการนี​​้ไม่ได้จริงๆ
สนใจว่าอาร์เรย์เป็น เรียงหรือไม่ที่จะเริ่มต้นด้วย
กระบวนการนี​​้เป็นกระบวนการเดียวกันที่มี วิธีการสิ่งที่ไม่มีไฟฟ้าลัดวงจร
ดังนั้น n log n ในกรณีที่เลวร้ายที่สุด n log n ในกรณีที่ดีที่สุด
>> เราได้พูดคุยเกี่ยวกับสอง ขั้นตอนวิธีการค้นหา
ดังนั้นการค้นหาเชิงเส้นเป็นเรื่องเกี่ยวกับ iterating
เราจะดำเนินการทั่วอาร์เรย์ ครั้งเดียวจากซ้ายไปขวา
พยายามที่จะหาจำนวน ที่เรากำลังมองหา
ที่เลวร้ายที่สุดกรณีที่เวลาทำงานมีขนาดใหญ่โอ n
มันอาจจะพาเราไปทำซ้ำ ทั่วทุกองค์ประกอบเดียว
เพื่อหาองค์ประกอบที่เรากำลังมอง สำหรับทั้งในตำแหน่งที่ผ่านมา
หรือไม่ได้เลย
แต่เราไม่สามารถยืนยันได้ว่าจน เราได้มองทุกอย่าง
มที่ดีที่สุดในกรณีที่เราจะพบทันที
เวลาการทำงานที่ดีที่สุดกรณีของ ค้นหาเชิงเส้นคือโอเมก้า 1
>> สุดท้ายมีการค้นหาแบบไบนารี, ซึ่งจะต้องมีอาร์เรย์สารพัน
โปรดจำไว้ว่าเป็นมาก การพิจารณาที่สำคัญ
เมื่อทำงานกับการค้นหาแบบไบนารี
มันเป็นสิ่งที่จำเป็นที่จะใช้ it-- อาร์เรย์ที่คุณกำลังมองผ่าน
จะต้องเรียง
มิฉะนั้นคำว่า คือแบ่งและพิชิต
แยกอาร์เรย์ลงในช่วงครึ่งปีและ ขจัดครึ่งหนึ่งขององค์ประกอบ
ทุกครั้งที่คุณดำเนินการผ่าน
เพราะการแบ่งนี้และพิชิต และสิ่งที่แยกในแนวทางครึ่ง
ที่เลวร้ายที่สุดกรณีที่เวลาทำงาน ของการค้นหาไบนารี
log n ซึ่งเป็นอย่างมาก ดีกว่า n เชิงเส้นของการค้นหา
เวลาทำงานกรณีที่ดีที่สุดยังคงเป็นหนึ่ง
>> เราอาจจะพบว่ามันทันที ครั้งแรกที่เราทำส่วนหนึ่ง แต่
อีกครั้งจำไว้ว่า แม้ว่าการค้นหาแบบไบนารีคือ
อย่างมีนัยสำคัญที่ดีกว่าการค้นหาเชิงเส้น โดยอาศัยอำนาจของการเข้าสู่ระบบเมื่อเทียบกับ n n,
คุณอาจจะต้องไปผ่านการทำงาน ของการเรียงลำดับอาร์เรย์ของคุณครั้งแรกที่
อาจจะทำให้มีประสิทธิภาพน้อยขึ้นอยู่กับ กับขนาดของ iterating เรียง
>> ฉันลอยด์ดั๊กนี้เป็น CS50