ลำโพงอยู่ด้านขวาทั้งหมดนี้เป็น CS50 นี่คือจุดสิ้นสุดของสัปดาห์ที่สามและถ้า คุณยังไม่ได้ใช้ประโยชน์แล้ว ทราบว่าจะมีอาหารกลางวัน วันศุกร์นี้ตามปกติท​​ี่ คุณสามารถเพลิดเพลินกับการสนทนาที่ดี และอาหารที่ไฟและน้ำแข็ง กับบางส่วนของ CS50 ของ พนักงานและเพื่อนร่วมชั้น มุ่งหน้าไปยัง URL ที่นี่ 

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

ผู้ชม: แมรี่เบ ธ ลำโพง: แมรี่เบ ธ มาขึ้น ให้ฉันได้รับไมโครโฟนที่นี่สำหรับคุณ มีความสุขที่ได้พบคุณ 

ผู้ชม: ยินดีที่ได้พบคุณ ลำโพง: สิทธิทั้งหมดเพื่อให้ฉันมี ที่นี่หนังสือสีฟ้าถึง Z และฉันจะแกล้งทำเป็นว่า ฉันมีหนึ่งของนักเรียน และพวกเขากำลังมาค่อนข้างสุ่ม ที่ส่วนท้ายของบล็อกสอบสามชั่วโมง ดังนั้นพวกเขาจึงกำลังสิ้นสุดขึ้นในบางส่วน เพื่อกึ่งสุ่มเช่นนี้ ตอนนี้งานของคุณในเวลาเพียงช่วงเวลาที่เกิด เพื่อ be-- นี้เป็นจริงว่าพวกเขาได้รับ หันในตอนท้ายของ ชั้นที่มีโอกาสมากที่สุด งานของคุณตอนนี้เป็นไปได้ค่อนข้าง เพียงแค่การจัดเรียงหนังสือสีฟ้าเหล่านี้สำหรับเรา จากถึง Z 

ผู้ชม: โอ้นี้เป็น จะใช้เวลาตลอด 

ลำโพง: และเราจะดู ในขณะที่คุณทำเช่นนี้ไม่มีความกดดัน ผู้ชม: ไม่มีแรงกดดันหรืออะไร 

ลำโพง: และเพื่อความสนุกสนาน ขอนำค่าตัวจับเวลา 

ผู้ชม: สนุกมากสนุกมาก 

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

ผู้ชม: ฉันสั่งให้พวกเขา เมื่อผมพบจดหมายสองฉบับ ที่ฉันรู้ว่ามีอยู่ด้วยกันในลำดับ ฉันทำให้พวกเขาร่วมกันเพื่อที่ฉันทำไม่ได้ ต้องกังวลเกี่ยวกับการรักษา ติดตามทั้งแถวของหนังสือ มันก็แค่โอเป็นครั้งแรก ฉันมีสแต็คที่นี่ ลำโพง: ดังนั้นเกือบจะเหมือน ชิ้นส่วนปริศนาที่ มีรูปร่างที่เหมาะสมที่จะ ตรงกับแต่ละอื่น ๆ ผู้ชม: สวยมากจ้ะ ลำโพง: ตกลงที่ดีเยี่ยม และตอนนี้แต่ละเหล่านี้ กองจะถูกจัดเรียงอย่างน่า? 

ผู้ชม: ใช่ 

ลำโพง: สิทธิทั้งหมดถึง Z ทั้งหมด ที่ถูกต้องขอแสดงความยินดีที่คุณทำมัน คุณมีทางเลือกของคุณ สีฟ้า? สิทธิทั้งหมดขอบคุณที่ ดังนั้นแมรี่เบ ธ ไม่เสนอ สิ่งที่วิธีการของเธอคือ แต่คือสิ่งที่อีกวิธีหนึ่งวิธีการที่คุณ อาจจะไปเกี่ยวกับการเรียงลำดับสิ่งเหล่านี้หรือไม่ สิ่งที่คุณจะได้ทำ? บันทึกที่จะชนะจะได้รับ หนึ่งนาทีและ 50 หรือดังนั้นวินาที บวกคนที่ฉันลืมที่จะนับ สิ่งที่คุณจะได้ทำ? ใช่? ผู้ชม: ใช้สแต็ค เริ่มต้นจากจุดเริ่มต้น ตรวจสอบเอกสารของคุณ และถ้าหนึ่งด้านบนที่สูง กว่าบางทีที่พวกเขาเป็น หนึ่งล่างคือ ที่สูงขึ้นแล้วสลับพวกเขา 

ลำโพง: OK เพื่อเริ่มต้น ที่ด้านบนและด้านล่าง แล้ววิธีการทำงานของคุณ ขาเข้าเช่นนั้นการแลกเปลี่ยนพวกเขา? OK เพื่อให้เล็ก ๆ น้อย ๆ ที่คล้ายกัน ในจิตวิญญาณในการเรียงลำดับฟอง แต่เลือกขั้ว ไม่ได้คู่ที่อยู่ติดกัน แต่ระยะสั้นของมันคือการที่มี แน่นอนพวงของวิธีการที่แตกต่างกัน เราสามารถทำเช่นนี้และ ตรงไปตรงมาผมคิดว่าคุณชนิดของ นำสองวิธีใช่มั้ย? คุณทำให้การจัดเรียงของสี่เรียงกองและ จากนั้นได้อย่างมีประสิทธิภาพรวมเข้าด้วยกัน และที่, daresay อีก เทคนิคทั้งหมด คุณไม่ได้รักษามันเป็นกองใหญ่หนึ่ง คุณแบ่งปัญหาออกเป็นสี่คณะสี่คน, ถ้าคุณจะแล้วอย่างใด รวมพวกเขาในท้ายที่สุด 

เพื่อให้พิจารณาในที่สุด วิธีอื่นที่เราอาจจะทำเช่นนี้ เรากรงเล็บความคิด ของฟองเรียงครั้งสุดท้าย และการเรียกคืนการจัดเรียงฟองเป็น อัลกอริทึมที่เรามองเห็น กับแปดของเพื่อนร่วมชั้นของคุณที่นี่ ดูเหมือนจะถูกจัดเรียงแบบสุ่มในตอนแรก และเราจึงตัดสินใจจับคู่ถ้า สององค์ประกอบที่จะออกคำสั่ง เพียงแค่สลับพวกเขา ดังนั้นสี่และทั้งสองมี เห็นได้ชัดว่าออกคำสั่ง ดังนั้นทั้งสองเพื่อนร่วมชั้น ตำแหน่งเปลี่ยน แล้วเราซ้ำกับสี่และหก จากนั้นหกและแปดในแต่ละซ้ำ, ย้ายไปทางขวา 

ให้ดังนั้นแปดคนกี่คู่ เปรียบเทียบผมทำในขณะที่เดินจาก จากซ้ายไปขวาในหนึ่งซ้ำเช่น? หลายวิธีการเปรียบเทียบ? เซเว่นใช่มั้ย? เพราะถ้ามีแปด คน แต่คุณมีคู่ พวกเขาและคุณให้ย้าย หนึ่งกระโดดไปทางขวา คุณไม่ได้จะมีแปด เปรียบเทียบเพราะคุณไม่สามารถเปรียบเทียบ องค์ประกอบกับตัวเองหรือมันจะ เพียงแค่จะไม่มีจุดหมายเพื่อให้คุณมีเจ็ด หรือมากกว่าโดยทั่วไปถ้า เรามี n คนเรา ทำ n ลบ 1 การเปรียบเทียบ ด้วยการจัดเรียงฟอง 

เพื่อให้พิจารณาตอนนี้วิธีที่ดีหรือ ฟองไม่ดีการจัดเรียงเป็นจริงและพยายาม เพื่อให้ตัวเองกับคำศัพท์ ซึ่งขั้นตอนวิธีการวิจารณ์เช่นนี้ และเร็ว ๆ นี้ของเราเอง เพื่อให้ผ่านครั้งแรกผ่าน การจัดเรียงฟองเป็นครั้งแรกที่ ผมเดินจากซ้ายไปทางขวาข้าม เวทีเอาฉัน n ลบ 1 การเปรียบเทียบ และนั่นจะเป็นของฉัน หน่วยของการวัดใช่มั้ย? ผมชนิดของการพูดคุยและเดินเล่น ค่อนข้างรวดเร็วค่อนข้างช้า เพื่อนับจำนวนของวินาที ไม่ได้โดยเฉพาะอย่างยิ่งบอก แต่นับจำนวนของ การดำเนินงานที่ผมทำในวันจันทร์ที่ เปรียบเทียบคนสองคนที่รู้สึก เช่นหน่วยที่ดีของวัด 

ดังนั้น n ลบ 1 ขั้นตอนที่เป็นครั้งแรกที่ แต่แล้วสิ่งที่เกิดขึ้นหลังจากที่? สิ่งหนึ่ง upside อีกหนึ่งผ่าน ผ่านรายการที่ไม่ได้เรียงลำดับอย่างอื่น? สิ่งที่คุณสามารถบอกฉันเกี่ยวกับองค์ประกอบ ซึ่งเป็นทางไปที่นั่นหรือไม่ ใช่? นั่นเป็นองค์ประกอบที่ใหญ่ที่สุดใช่มั้ย? หมายเลขแปดแม้ว่าเธอ เริ่มที่นี่ทุกครั้งที่ผม เมื่อเทียบกับของเธอกับ เพื่อนบ้านของเธอเก็บไว้ เดือดปุด ๆ ขึ้นไปทางขวา ด้านซ้ายมือของรายการ และแน่นอนว่าเป็นที่ อัลกอริทึมที่ได้รับชื่อของมัน 

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

ตอนนี้จุดจุด, จุดชนิดของคลื่นมัน มือที่บางส่วนของรายละเอียด juicier, แต่ขอเพียงไปข้างหน้าและลดความซับซ้อน ถ้าคุณจำจากที่สูง โรงเรียนตรงไปตรงมามากของคุณ มีหนังสือคณิตศาสตร์ที่มี แผ่นโกงเล็ก ๆ น้อย ๆ บนหน้าปกหรือ ปกหลังแสดงให้เห็นว่าคุณ summations สิ่งที่ชุดเช่น ท้ายที่สุดนี้ได้เพิ่มขึ้นถึง ในกรณีทั่วไปถ้าคุณมี เช่นตัวแปร n และแน่นอนคนนี้ ถ้าคุณมองไปที่ของคุณ หนังสือคณิตศาสตร์โรงเรียนเก่า คุณจะเห็นว่านี้จริง เพิ่มขึ้นจำนวนนี้ที่นี่ ครั้ง n n ลบ 1 ทั้งหมดหารด้วย 2 ดังนั้นสำหรับตอนนี้ให้ฉันเพียงกำหนด นี้เป็นจริงดังนั้นในการก้าวกระโดดของความเชื่อที่ นั่นคือสิ่งที่สรุปนี้ ขึ้นไปและที่เราจะทำได้ พิสูจน์ให้เห็นว่าในกรณีทั่วไปมากขึ้น แต่ตอนนี้ขอขยายออกไปนี้ ดังนั้นลองคูณนี้ออกมาเพื่อให้เป็น n กำลังสองลบ n แบ่งออกทุก 2 ที่จริง n ยกกำลัง หารด้วย 2 ลบ n กว่า 2 ดังนั้นนั่นคือทั้งหมดที่ดีและน่าสนใจ แต่สิ่งที่เกิดขึ้นถ้าเรา ตอนนี้ plug-in มูลค่า? สมมติว่าผมไม่ได้มีแปด คน แต่บอกว่าล้าน และล้านเพียงเพราะ มันเป็นจำนวนมากสวย ให้เสียบที่และดูสิ่งที่เกิดขึ้น ดังนั้นถ้าผมเสียบล้านเป็นสูตรที่ ฉันจะได้รับล้านยกกำลัง หารด้วย 2 ลบ ล้านบาทโดยแบ่งออกเป็น 2 ตอนนี้สิ่งที่ว่าจะเท่ากับ? ดังนั้น 500000000000 ลบ 500,000 และถ้าผมทำจริง คณิตศาสตร์ให้เห็นว่าวิธีการที่ ที่เรียงลำดับล้าน คนที่มีการจัดเรียงฟอง อาจจะใช้เวลาฉัน 499999500000 ขั้นตอนหรือการเปรียบเทียบในท้ายที่สุด เราเพียงแค่คะเน 

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

[วิดีโอเล่นภาพ] 

-Senator คุณอยู่ที่นี่ ที่ Google และผมชอบ ที่จะคิดของประธานาธิบดี เช่นการสัมภาษณ์งาน ตอนนี้มันเป็นเรื่องยากที่จะได้รับ งานเป็นประธาน และคุณกำลังจะผ่านความโหดร้ายนี้ นอกจากนี้ยังเป็นเรื่องยากที่จะได้รับงานที่ Google เรามีคำถามและเรา ขอให้ผู้สมัครคำถามของเรา และหนึ่งนี้จากลาร์รีชวิมเม What-- พวกคุณคิดว่าฉัน ล้อเล่นมันเป็นสิทธิที่นี่ สิ่งที่เป็นวิธีที่มีประสิทธิภาพที่สุดในการ ค้นหาล้านจำนวนเต็ม 32 บิต? 

-Well-- 

-I'm ขอโทษ maybe-- 

ไม่มีไม่มีไม่มี ผมคิดว่าการจัดเรียงฟอง จะเป็นวิธีที่ผิดไป 

-Come ที่ใครบอกเขานี้ ฉันไม่เห็นคอมพิวเตอร์ วิทยาศาสตร์ในพื้นหลังของคุณ 

-We've มีสายลับของเราในการมี 

-OK ให้ถามที่แตกต่างกัน คำถามสัมภาษณ์ 

[จบการเล่นวิดีโอ] 

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

ดังนั้นผมจึงได้เน้นสีเหลืองที่นี่ ผลของ n สองหารด้วย 2 ดังนั้นล้านกำลังสอง หารด้วย 2 แล้ว ผมได้เน้นสิ่งที่ ตอบที่ดีที่สุดคือ เมื่อเราหักออก n หารด้วย 2 และเรียกร้องที่ฉันจะทำตอนนี้คือ ที่ห่าใส่ใจถ้าคุณลบออก n อายุน้อยกว่า 2 ครั้งแรกเมื่อ ส่วนหนึ่งของสูตรนี้จึงใหญ่มาก? มันครอบงำอื่น ๆ ระยะ n สองหารด้วย 2 เป็นสิ่งที่ใหญ่กว่ามากอย่างเห็นได้ชัดเช่น n ได้รับขนาดใหญ่เช่นล้าน ที่มีจริงๆความแตกต่างใหญ่ที่ ตอนท้ายของวันระหว่าง 500,000,000,000 และ 499999500000? ไม่ได้จริงๆ และเพื่อให้สิ่งที่เรากำลังจะไป ทำตามที่นักวิทยาศาสตร์คอมพิวเตอร์ ไม่สนใจคำสั่งของผู้ที่ต่ำกว่าและ ใช้บางอย่างเช่นนี้จริงๆ เพียงแค่ลดความซับซ้อนของมันไป ระยะที่จะมีความสำคัญ ชุดข้อมูลขนาดใหญ่ของเราได้รับที่ใหญ่กว่า ฐานข้อมูลของเราได้รับที่หน้าเว็บ เรามีการค้นหามากขึ้น เพื่อนที่คุณมีใน Facebook 

เป็น n ได้รับใหญ่เราไม่ได้จริงๆ จะดูแลเกี่ยวกับการที่ใหญ่ที่สุด ระยะในการวิเคราะห์ดังกล่าว ประสิทธิภาพการทำงานของอัลกอริทึมของเรา และฉันจะบอกว่าคุณรู้ว่าสิ่งที่ การจัดเรียงฟองเป็นคำสั่งของโอใหญ่ โดยคำสั่งของ n กำลังสอง มันไม่ตรง n กำลังสองในขณะที่เราได้เห็น แต่ผู้ที่ใส่ใจจริงๆ เกี่ยวกับคำที่มีขนาดเล็กเหล่านั้น และตรงไปตรงมาที่จริงๆ ใส่ใจถ้าเราหารด้วย 2 หรือไม่? นั่นเป็นเพียงปัจจัยคง และเป็น 500,000,000,000 เมื่อเทียบกับ 250 พันล้านจริงๆที่ใหญ่ของการจัดการหรือไม่ ฉันจะรอหนึ่งปี ให้แล็ปท็อปของฉันอย่างแท้จริง ได้รับสองครั้งที่รวดเร็วในด้านฮาร์ดแวร์ และการเรียงลำดับของความแตกต่างที่ เพียงแค่ออกไปตามธรรมชาติเมื่อเวลาผ่านไป 

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

สิ่งที่เราไม่ได้ไป นับเป็นระยะเวลาที่ ที่ผ่านบนนาฬิกา บนผนังโดยทั่วไป สิ่งที่เราจะไม่ต้องกังวล เกี่ยวกับการเป็นหน่วยความจำเท่าใด ที่คุณใช้ในวันนี้ที่ น้อย แต่ที่ ทรัพยากรที่เราอาจจะวัดอื่น เราจะพยายามที่จะฐานการวิเคราะห์ของเรา เพียงการดำเนินงานพื้นฐานคนที่ ตรงไปตรงมาเห็นว่าคุณสามารถเห็นส่วนใหญ่ ดังนั้นกับสิ่งที่ต้องการ O ใหญ่ของ n กำลังสองผมอ้างว่า O ของ n กำลังสอง เป็นขอบเขตบนที่เรียกว่า ใช้เวลาของการจัดเรียงฟอง ในคำอื่น ๆ ถ้าคุณ ต้องการที่จะอ้างว่ามี ขีด จำกัด บนนี้ในหลายวิธี ขั้นตอนวิธีการอาจจะใช้เวลา มันจะอยู่ในโอใหญ่ของ n กำลังสองในกรณีนี้บนปก 

ถ้าฉันเปลี่ยนแทน เรื่องราวจะเป็นไม่เกี่ยวกับการจัดเรียงฟอง แต่เกี่ยวกับเรื่องนี้บนปก คุณสามารถคิดของอัลกอริทึม ที่เราได้มองที่แล้ว บนปกสูงสุดที่มี, วัดเวลาหรือการดำเนินงาน จะได้รับการบอกว่าจะกระโดด ด้วย n ฟังก์ชันเชิงเส้น ไม่หนึ่งกำลังสองที่โค้ง? คือสิ่งที่อัลกอริทึมที่ มักจะใช้เวลาไม่มาก กว่าเหมือนขั้นตอนที่ n หรือ ขั้นตอน 2n หรือขั้นตอน 3n? ใช่? 

ผู้ชม: หา จำนวนที่ใหญ่ที่สุดในรายการหรือไม่ 

ลำโพง: ที่สมบูรณ์แบบในการค้นหา หมายเลขที่ใหญ่ที่สุดในรายการ ถ้าฉันได้รับรายชื่อของ คนเช่น แต่ละที่มีการถือครองหมายเลข สิ่งที่เป็นจำนวนสูงสุด ในขั้นตอนที่มันควรจะใช้เวลาฉัน เป็นคนที่สมาร์ทพอสมควร ที่จะหาคนที่ใหญ่ที่สุดในรายการที่? n ขวา? เพราะในกรณีที่เลวร้ายที่สุดที่ ค่าที่ใหญ่ที่สุดอาจจะมี? ขวาตลอดทางที่สิ้นสุด ดังนั้นในกรณีที่เลวร้ายที่สุด บนผูกพันฉันอาจ ต้องไปตลอดทาง กว่าที่นี่และมีความเหมือน โอ้นี่เป็นจำนวนแปด หรืออะไรก็ตามที่ค่าที่ ตอนนี้ก็เพียงแค่จะโง่ ถ้าฉันยังคงต้องไปใช่มั้ย? มองหาองค์ประกอบมากขึ้นและมากขึ้น ถ้าสุดท้ายคือที่นั่น? ดังนั้นแน่นอน n คือบนผูกพัน ฉันไม่ต้องการที่จะใช้ ขั้นตอนที่มากไปกว่านั้น 

ดังนั้นสิ่งที่ถ้าแทนฉันเสนอว่า มีขั้นตอนวิธีการในโลกนี้ที่ มีเวลาในการทำงานที่ จำกัด โดย O ใหญ่ของล็อก n, log n? ที่เราได้เห็นนี้มาก่อนหรือไม่ ใช่? 

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

เพื่อให้เข้าสู่ระบบของ n หมายถึงแน่ใจว่า กับตัวอย่างสมุดโทรศัพท์ เพื่อค้นหา binary ในทางทฤษฎีเมื่อเรา มีประตูเสมือนบนกระดาน หรือเมื่อฌอนเป็น ค้นหาสิ่งที่ ถ้าเขาใช้ค้นหา binary, log n จะเป็นขอบเขตบนเท่าใด เวลาที่ใช้เวลา แต่อัลกอริทึมที่วิ่งเข้าไปในห้อง log N สันนิษฐานว่ารายละเอียดที่สำคัญ? ว่ารายการที่ถูกจัดเรียงใช่มั้ย? อัลกอริทึมของคุณเป็นสิ่งที่ผิดถ้า การป้อนข้อมูลของคุณไม่ได้เรียงลำดับ และยังคุณกำลังใช้ สิ่งที่ต้องการค้นหา binary เพราะคุณอาจจะกระโดด ที่เหมาะสมกว่าองค์ประกอบ โดยไม่ทราบว่ามันมีจริง 

ตอนนี้สิ่งที่นี้อาจหมายถึงโอใหญ่ของหนึ่ง? นี้ไม่ได้หมายความว่าอัลกอริทึมของคุณ ใช้เวลาหนึ่งและมีเพียงขั้นตอนเดียว มันก็หมายความว่ามันจะใช้เวลา จำนวนคงที่ของขั้นตอน อาจจะเป็นที่ 1 อาจจะเป็น 10 อาจจะถึง 1,000 แต่มันก็เป็นอิสระจาก ขนาดของปัญหา ไม่ว่าใหญ่ n คือ อัลกอริทึมเวลาคงที่ มักจะใช้หมายเลขเดียวกันของขั้นตอน ดังนั้นสิ่งที่อาจจะมีอัลกอริทึม เราได้พูดคุยเกี่ยวกับหรือเพียงแค่ สังหรณ์ใจที่มาพร้อมกับคุณว่า มักจะทำงานในที่เรียกว่าเวลาคงที่? ใช่? 

ผู้ชม: เพ​​ิ่มตัวเลขสอง ลำโพง: เพิ่มสองตัวเลข 2 บวก 2 เท่ากับ 4 ทำ เพื่อที่จะทำงานอะไร? วิธีการเกี่ยวกับโลกแห่งความจริงมากขึ้นใช่? 

ผู้ชม: หา สิ่งแรกที่อยู่ในรายชื่อ ลำโพง: หาครั้งแรก องค์ประกอบในรายการนั่นเอง เราได้รับการพูดจริง เกี่ยวกับอาร์เรย์แล้ว คุณจะได้รับที่ องค์ประกอบแรกในอาร์เรย์ ไม่ว่านาน อาร์เรย์ที่อยู่ในรหัส C? คุณเพียงแค่ใช้เช่นวงเล็บ ศูนย์สัญกรณ์, แบม, คุณอยู่ที่นั่น และแน่นอนอาร์เรย์เช่นกัน สิ่งที่สนับสนุนรู้จักกันโดยทั่วไป การเข้าถึงแบบสุ่มเข้าถึงโดยสุ่ม หน่วยความจำเพราะคุณสามารถอย่างแท้จริง ข้ามไปที่ใดสถานที่หนึ่ง เราสามารถทำเช่นนี้ได้มากยิ่งขึ้นเพียงแค่ เราสามารถย้อนกลับไปเมื่อสัปดาห์ที่ศูนย์ เมื่อเราได้ Scratch เวลาเท่าไหร่มันใช้เวลาสำหรับ กล่าวว่าในบล็อก Scratch ที่จะดำเนินการ? เวลาคงที่เพียงแค่ใช่มั้ย? กล่าวว่าสิ่งที่พูด บางสิ่งบางอย่างมันไม่สำคัญ ว่าโลกรอยขีดข่วนขนาดใหญ่ก็มักจะ จะใช้จำนวนเงินเดียวกันของเวลา เพียงแค่พูดอะไรบางอย่าง 

เพื่อให้ถึงเวลาที่คงที่ แต่เป็นด้านพลิกอะไร ถ้าเป็นบน ขอบเขตสิ่งที่ถ้าเราต้องการ เพื่ออธิบายขอบเขตที่ต่ำกว่า อัลกอริทึมของเราทำงานเวลา? เกือบกรณีที่ดีที่สุด อาจถ้าคุณจะ แต่คำเหล่านี้สามารถนำไปใช้ที่ดีที่สุด กรณีที่เลวร้ายที่สุดกรณีกรณีเฉลี่ยมากกว่า ทั่วไป แต่ขอเพียงมุ่งเน้น ในขอบเขตที่ลดลงมากกว่าปกติ คือสิ่งที่อัลกอริทึมที่มี ขีด จำกัด ล่างของขั้นตอนที่ n, หรือขั้นตอน 2n หรือขั้นตอน 3n? ปัจจัยบางขั้นตอน n, นั่นคือขอบเขตที่ต่ำของ ใช่? 

ผู้ชม: จัดเรียงฟอง? 

ลำโพง: จัดเรียงฟองใช้เวลา ขั้นตอนน้อยที่สุด n, ทำไม? ทำไมจึงเป็นเช่นนั้น เริ่มต้นที่ควรทำไมมาให้คุณ สังหรณ์ใจแม้ว่าจะไม่ได้เพียงแค่ หรือยัง? ใช่? 

ผู้ชม: [ไม่ได้ยิน] ลำโพง: แน่นอน ในสถานการณ์ที่ดีที่สุดของ การจัดเรียงฟองและมากของขั้นตอนวิธีการ ถ้าผมมือคุณแปดคน ที่จะจัดเรียงแล้ว มันจะโง่ สำหรับคุณขั้นตอนวิธี ที่จะกลับไปมา มากกว่าหนึ่งครั้งใช่มั้ย? เพราะทันทีที่คุณ เดินผ่านรายการครั้งเดียว คุณควรตระหนักถึงโอ้ฉันทำไม่มี แลกเปลี่ยนรายการนี​​้จะถูกจัดเรียงออก แต่ที่จะพาคุณ n ขั้นตอน 

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

ดังนั้นตอนนี้เรามีวิธีการ อธิบายขอบเขตที่ต่ำกว่า และสิ่งที่เกี่ยวกับเวลาคงที่? คือสิ่งที่อัลกอริทึมที่มีลดลง ผูกพันกับเวลาทำงานของหนึ่ง? 1 ขั้นตอนที่ 2 ขั้นตอน 10 ขั้นตอน แต่ คงที่เป็นอิสระจาก n, ขนาดของการป้อนข้อมูลหรือไม่ ใช่ในด้านหลัง 

ผู้ชม: Printf? ลำโพง: มีอะไรที่? ผู้ชม: Printf? ลำโพง: Printf ตกลงนั่นเอง ดังนั้นก็จะใช้เวลาเป็นจำนวนคงที่ของขั้นตอน และฉันควร now-- ตอนนี้ที่ เรากำลังพูดถึงรหัส C และไม่ Scratch บางสิ่งบางอย่าง เหมือนพูดกับ printf, เราควรจะเริ่มต้นที่จะได้รับอย่างรอบคอบ เพราะ printf จะใช้เวลา ใส่มันเป็นสตริง และสตริงในทางเทคนิคจะมีความยาว ดังนั้นถ้าตอนนี้เราต้องการที่จะเลือก กับคุณถ้าคุณไม่ทราบ ในทางเทคนิคเราสามารถยืนยัน printf ที่ จะใช้ระยะเวลาในการป้อนข้อมูลตัวแปร และแน่นอนมันอาจจะใช้เวลามากขึ้น เวลาในการพิมพ์สายนี้ยาว ยาวกว่านี้ 

ดังนั้นสิ่งที่ถ้าเราพิจารณาเพียง การเรียงลำดับและการค้นหาตัวอย่าง? สิ่งที่เกี่ยวกับไมค์สมิ ธ ในโทรศัพท์ หนังสือหรือค้นหา binary มากกว่าปกติ? ในกรณีที่ดีที่สุดสิ่งที่อาจเกิดขึ้นได้อย่างไร ฉันเปิดสมุดโทรศัพท์และแบม มีจำนวนไมค์สมิ ธ เป็น ฉันจะโทรไปหาเขาทันที 

เอาหนึ่งขั้นตอนที่อาจจะสองขั้นตอน แต่จำนวนคงที่ของขั้นตอน ถ้าฉันได้รับโชคดี และตรงไปตรงมาเราเห็นใน จันทร์เพื่อนร่วมชั้นของคุณ ได้รับโชคดีมากเป็นครั้งที่สองในแถว และที่เป็นจริงอย่างต่อเนื่อง เวลาอยู่ในขอบเขตที่ต่ำกว่า อัลกอริทึมในคำถามสำหรับการค้นหา จำนวน 50 หลังที่ปิด ประตู 

ตอนนี้เป็นกันถ้าคุณพบ ว่าทั้งสอง O ใหญ่บนปก และโอเมก้า, ที่ถูกผูกไว้ที่ต่ำกว่า เป็นหนึ่งในเดียวกันว่า เป็นสูตรเดียวกันใน วงเล็บคุณยังสามารถ พูดเพียงว่าเป็นแฟนซี บางสิ่งบางอย่างที่อยู่ในที ของ n หรือ theta ของบางค่าอื่น ที่เพียงแค่หมายความว่าเมื่อขนาดใหญ่ O และโอเมก้าเหมือนกัน ตอนนี้สิ่งที่เกี่ยวกับการจัดเรียงตัวเลือก? ลองใช้คำศัพท์ใหม่นี้ ในการเรียงลำดับตัวเลือกสิ่งที่เป็นเรา ทำอีกครั้งและอีกครั้งและอีกครั้งหรือไม่ ผมก็จะกลับมาผ่าน รายการที่กำลังมองหาใคร? จำนวนน้อยที่สุด 

ดังนั้นวิธีการหลายขั้นตอนวิธี การเปรียบเทียบจำนวนมากไม่ฉัน จะต้องทำเพื่อที่จะคิดออกที่ องค์ประกอบที่เล็กที่สุดในรายการคืออะไร n ลบ 1 ใช่มั้ย? เพราะถ้าฉันเพียงแค่เริ่มต้นด้วยหนึ่งฉัน ที่กำหนดและฉันเริ่มเปรียบเทียบเขาหรือเธอ จากนั้นเขาหรือเธอให้เขา หรือเธอเขาหรือเธอฉัน สามารถจับคู่องค์ประกอบ ร่วมกัน n ลบ 1 คูณ ดังนั้นตัวเลือกการจัดเรียงกันจะใช้เวลา n ลบ 1 ขั้นตอนที่เป็นครั้งแรกที่ 

มันไม่กี่ขั้นตอนพาฉันไปที่ พบว่าองค์ประกอบที่สองมีขนาดเล็กที่สุดหรือไม่ n ลบ 2 เพราะฉันเป็นใบ้ ถ้าฉันให้มองไปที่คนคนเดียวกัน อีกครั้งถ้าผมได้เลือกเขาแล้ว หรือเธอและนำพวกเขาในสถานที่ของพวกเขา และขั้นตอนที่สาม n ลบ 3 แล้ว n ลบ 4 เราได้เห็นรูปแบบนี้ ก่อนและแน่นอน ตัวเลือกการจัดเรียงกัน มีขีด จำกัด บน ของ n กำลังสองถ้าเราทำขึ้นบวกว่า ขีด จำกัด ล่างเรียงลำดับการเลือกคืออะไร น้อยที่สุดเท่าไหร่ต้องเลือกเวลา การจัดเรียงเวลาที่เรากำหนดไว้ว่าในวันจันทร์ที่? เสนอตัวเลือกที่สอง อาจจะเป็น n เป็นมาก่อน บางทีมันอาจจะเป็น n กำลังสองมัน คือตอนนี้เป็นขีด จำกัด บน 

ผู้ชม: n กำลังสอง ลำโพง: n กำลังสอง ทำไม? 

ผู้ชม: เพ​​ราะคุณมี เพื่อกำหนด [ไม่ได้ยิน] 

ลำโพง: แน่นอน อย่างน้อยที่สุดเท่าที่จะกำหนดตัวเลือกการจัดเรียง มันก็ไร้เดียงสาสวยเก็บไป พบว่าองค์ประกอบที่เล็กที่สุด ไปอีกครั้งพบว่าองค์ประกอบที่เล็กที่สุด ไปอีกครั้งพบว่าองค์ประกอบที่เล็กที่สุด มีการเรียงลำดับของไม่ได้ การเพิ่มประสิทธิภาพในการมีที่ อาจจะให้ฉันยกเลิกหลังจากที่ เพียง n หรือเพื่อให้ขั้นตอน ดังนั้นแน่นอนการเลือก เรียงลำดับของโอเมก้า n กำลังสอง 

สิ่งที่เกี่ยวกับการจัดเรียงแทรกที่ผมเอา ที่ผมได้รับแล้วผม plopped เขา หรือเธออยู่ในสถานที่ที่เหมาะสมหรือไม่ จากนั้นผมก็เดินไปที่คนที่สอง plopped เขาหรือเธอในสถานที่ที่เหมาะสม แล้วคนต่อไป plopped เขาหรือเธอในสถานที่ที่เหมาะสม ขอให้สังเกตว่านี้เป็นอย่างมาก เชิงเส้นจึงจะพูด ผมเป็นเส้นตรงผม จะไม่กลับมา ผมไม่เคยมองย้อนกลับไปจริงๆ แต่ สิ่งที่เกิดขึ้นเมื่อฉันใส่เขา หรือเธอเป็นจุดเริ่มต้นของ รายการที่เราได้ในวันจันทร์ที่? สิ่งที่เกิดขึ้น? ใช่? ผู้ชม: [ไม่ได้ยิน] ลำโพง: ใ​​ช่ว่า ก็จับได้ใช่มั้ย? คุณอาจจำจาก เพื่อนร่วมชั้นของคุณหากพวกเขา ได้ทำให้การเคลื่อนไหวใด ๆ เท้าของพวกเขาที่ได้รับการดำเนินการ ดังนั้นถ้ามีอยู่สามคนที่นี่และ คนใหม่เป็นวิธีการที่นั่น บนเวทีนานเช่นนี้นั่นเองเขา หรือเธอก็สามารถไปให้มาก แต่ถ้าเรากำลังคิดเกี่ยวกับ คอมพิวเตอร์และอาเรย์ของหน่วยความจำ, คนเหล่านี้จะไป ที่จะมีการสับเปลี่ยนกว่า ที่จะทำให้ห้องพักสำหรับคนที่ และเพื่อให้ n ลบ 1 shufflings, n ลบ 2 shufflings, n ลบ 3 shufflings เป็นเพียงชนิดของ สิ่งที่เกิดขึ้นข้างหลังผมไม่ได้อยู่ในด้านหน้าของฉัน เหมือนก่อนหน้านี้ในความรู้สึกบาง ตอนนี้เป็นกันและเป็น คุณอาจได้เห็นออนไลน์ หากคุณเริ่มต้น poking รอบเกี่ยวกับ ทุกประเภทมีคนที่แตกต่างกันมากมาย ออกมีบางส่วนของพวกเขา ดีกว่าคนอื่น อันที่จริง bogosort เป็นหนึ่ง นั่นคือความสนุกสนานของการที่จะมองขึ้น Bogosort ใช้ชุดของ ตัวเลขหรือพูดสำรับไพ่, สุ่ม shuffles พวกเขาและ ตรวจสอบว่าพวกเขากำลังถูกจัดเรียง และถ้าคุณไม่ได้ทำมันอีกครั้ง และถ้าคุณไม่ได้ทำมันอีกครั้ง ถ้าไม่ทำมันอีกครั้ง โง่อย่างไม่น่าเชื่อ 

และแน่นอนถ้าคุณอ่าน เช่นบทความวิกิพีเดีย ชื่อเล่นคือโง่จัดเรียง ในที่สุดมันก็จะทำงาน หวังว่าให้เวลาพอ แต่เวลาที่ อาจจะใช้เวลาค่อนข้างบางเวลา ดังนั้นถ้าผมจะให้สิ่งที่ความเร็ว เพิ่มขึ้นจากตัวอย่างที่แมรี่เบ ธ ที่ก่อนหน้านี้ โดยมีองค์ประกอบอื่น ๆ อีกไม่กี่ แต่ทั้งสองหน่วยประมวลผลมากขึ้น คนสองคนที่ถ้าคุณ จะไม่คิดร่วมงานกับผม วิธีการเกี่ยวกับ 1 กว่าที่นี่และ ขอ go-- หนึ่งไปที่นั่นหรือไม่ ไม่มีใครที่นั่น? ตกลง คุณมีสีดำ เสื้อใช่มาลง ขวาทุกสิ่งที่เป็นชื่อของคุณ? 

ผู้ชม: ปีเตอร์ 

ลำโพง: มีอะไรที่? 

ผู้ชม: ปีเตอร์ ลำโพง: ปีเตอร์เดวิดมีความสุขที่ได้พบคุณ สิทธิทั้งหมดที่เรามีปีเตอร์ที่นี่ถ้าคุณ ต้องการที่จะเข้ามาสู่โต๊ะกว่าที่นี่ และสิ่งที่ชื่อของคุณ? 

ผู้ชม: เอเลน่า ลำโพง: เอเลน่า ตกลงที่ดีที่จะได้พบคุณ Elena พบปีเตอร์ ปีเตอร์เอเลน่า และเราจะต้องแอนดรู ขึ้นที่นี่เช่นกันโปรด และความท้าทายของคุณเป็นไป ที่จะมีการเรียงลำดับของการ์ด และหากไม่คุ้นเคยดาดฟ้า ของบัตรควรในที่สุด จะแยกสิ่งเล็กน้อยเช่น นี้ที่เราจะทำสโมสรแล้ว เสียแล้วหัวใจและ เพชรจากเอซเป็นหนึ่ง ทั้งหมดทางขึ้นไปยังพระมหากษัตริย์ 

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

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

ผู้ชม: [ไม่ได้ยิน] ลำโพง: มีอะไรที่? ผู้ชม: โดยชุด ลำโพง: โดยชุด ดังนั้นครั้งแรกที่พวกเขาจะถูกจัดกลุ่ม ทั้งหมดของเพชรด้วยกัน ดูเหมือนว่าทั้งหมดของ หัวใจด้วยกันดูเหมือนว่า และอื่น ๆ โดยไม่ต้องเคารพ สำหรับตัวเลขบนบัตร และตอนนี้พวกเขาจะปรากฏตัวอย่างเช่น ที่จะให้พวกเขาโดยการเรียงลำดับจำนวน ที่ดีมาก 

ขวาทั้งหมดดังนั้นสิ่งที่จะ เป็นขั้นตอนสุดท้ายแล้วที่นี่? เมื่อเรามีสี่ชุดที่เรียงลำดับสิ่งที่ เราจะต้องทำเพื่อสี่กอง เพื่อให้บรรลุหนึ่ง แยกดาดฟ้าค่อนข้างง่าย? ดังนั้นเราจึงจำเป็นที่จะรวมพวกเขาอีกครั้ง 

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

[APPLAUSE] 

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

แต่ฉันชนิดของใช้สิ่งที่ฉันจะเรียก วิธีการซ้ำแล้วซ้ำอีกมากที่นี่ ในบรรทัดที่แจ้งให้ทราบล่วงหน้าโดยเฉพาะอย่างยิ่ง 8 และสาย 11 เหล่านี้คือหลักฐานของซ้ำ วิธีการวิธีการวนลูป, เพราะที่ว่า พฤติกรรมของพวกเขาก่อให้เกิด เส้นที่ทั้งสองพูดไป ชนิดสายสามและคุณสามารถของ คิดว่าของที่อยู่ในของคุณ ตาใจเป็นห่วง มันบอกให้คุณกลับไปถึงขั้นตอน สามและทำซ้ำอีกครั้งและอีกครั้ง และอีกครั้ง 

แต่ถ้าเราใช้ประโยชน์จากความคิดที่สำคัญ ที่นี่เราไม่ได้ครั้งสุดท้าย และลดความซับซ้อนและสาย 8 สาย 11 และเพื่อนบ้านของพวกเขา เป็นเพียงแค่นี้สีเหลือง มันไม่ได้เป็นพื้นฐานการตัดทอน pseudocode มาก แต่มันเปลี่ยนแปลงพื้นฐาน ธรรมชาติของอัลกอริทึมของฉัน ตอนนี้สิ่งที่ฉันพูด ในขั้นตอนที่ 7 ในขั้นตอนที่ 10, คือการค้นหาสำหรับไมค์ ในลักษณะเดียวกับที่แน่นอน แต่ในทางด้านซ้าย ครึ่งหนึ่งหรือครึ่งหนึ่งทางด้านขวา 

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

ดังนั้นแม้ว่านี้จะรู้สึก เช่นบิตของคำนิยามวงจร ที่คุณตอบคนเป็น คำถามโดยเพียงแค่การเรียงลำดับของการถาม คำถามเดียวกันอีกครั้ง เช่นทำไมทำไมทำไม? ความจริงก็คือเพราะเราเขียนยาก คู่ของสายพิเศษขั้นตอนที่ 4 ซึ่งเป็นกรณีที่และขั้นตอนที่ 12 ซึ่ง มีประสิทธิภาพสาขาอื่น เพราะเรามีผู้ที่มาตรการชั่วคราว, ขั้นตอนวิธีนี้จะยุติถ้าเรา หาไมค์หรือถ้าเราทำไม่ได้ แต่ในขั้นตอนที่ 7 และ 10 ตอนนี้เรามี สิ่งที่เราจะเรียกอัลกอริทึมแบบทั่วถึง และเรียกซ้ำตัวเองย่อมเป็นความคิดที่มีประสิทธิภาพ นั่นเป็นความคิดเล็ก ๆ น้อย ๆ การดัดในตอนแรก ว่าตอนนี้เราสามารถใช้ดังต่อไปนี้ 

รวมการจัดเรียงจะเรียงลำดับสุดท้ายที่ เรามองไปที่อย่างน้อยในชั้นเรียนอย่างเป็นทางการ และมันก็แตกต่างกันลึกซึ้ง จากที่ผ่านมาสามและแน่นอน สี่ถ้าเรารวม bogosort ที่นี่ pseudocode สำหรับการจัดเรียงผสานเป็น เมื่อป้อนข้อมูลขององค์ประกอบ n ให้เพื่อให้ อาร์เรย์ของขนาด n ถ้า n น้อยกว่า 2, ผลตอบแทน ดังนั้นผมจึงมีเหตุผลที่ว่า สติตรวจสอบก่อน? อะไรคือความหมายถ้าฉันมือคุณ อาร์เรย์ที่มี n ระยะเวลาน้อยกว่า 2? มันถูกจัดเรียงอยู่แล้วเห็นได้ชัดว่าใช่มั้ย? เนื่องจากรายการทั้งสองมี องค์ประกอบหนึ่งซึ่งเป็นนิด ๆ ห่างเพราะมันเป็น สิ่งเดียวที่มี หรือมันเป็นเรื่องของขนาดเป็นศูนย์ซึ่งหมายถึง ไม่มีอะไรที่จะเรียงลำดับได้ดังนั้นโดยธรรมชาติ มันจะถูกจัดเรียง มีอะไรผิดปกติเพียงแค่มี เพื่อให้เป็นกรณีฐานของเราที่เรียกว่า 

ที่คล้ายในจิตวิญญาณ กับสิ่งที่เราทำกับไมค์ ถ้าไมค์ในสมุดโทรศัพท์ที่โทรไปหาเขา ถ้าเขาไม่ได้มีให้ขึ้น เป็นกรณีฐานที่เรียกว่าเพื่อให้แน่ใจว่า อัลกอริทึมในตอนท้ายของวันที่ จะหยุดในบางสถานการณ์ 

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

ดังนั้นรวมการจัดเรียงให้ทำเช่นนี้ถ้าคุณจะ ขบขันฉันด้วยการสาธิตเพิ่มเติม เพียงเพื่อให้เรามีบาง ตัวเลขที่จะทำงานกับ ฉันสามารถแลกเปลี่ยนแปดความเครียด ลูกแปดคน? ขวาทั้งหมดเกี่ยวกับวิธีการที่คุณสามสี่ ในส่วนนี้ห้าหกและขอ ไม่ 7, 8, มาขึ้น ตกลงใช่ตกลง ลบ 8 มีเราไปบวก 1 ที่ดีเยี่ยม สิ่งที่ถูกต้องมาขึ้นให้ ได้อย่างรวดเร็วให้คุณหมายเลข จำนวนสองจำนวนสามบ้านเลขที่สี่ จำนวนห้าหกเจ็ดและแปด ฉันไม่แปดอย่างถูกต้องในครั้งนี้ 

ตกลงเพื่อไปข้างหน้าถ้าคุณสามารถและ ให้เรียงคำสั่งเดิม ว่าเรามีเมื่อวานนี้ซึ่งมอง เช่นนี้ถ้าคุณจะไม่ทราบ และขอให้ทำมันในด้านหน้าของโต๊ะ ขวาทั้งหมดเพื่อรวมการจัดเรียง ซึ่งเป็นที่ที่มันจะ ที่จะได้รับชนิดของที่น่าสนใจ เพราะผมดูเหมือนจะให้ตัวเอง มากข้อมูลน้อยลงในวันนี้ 

ดังนั้นการผสานการเรียงลำดับแรกของทุกคน กับการป้อนข้อมูลขององค์ประกอบ n, และจะเห็นได้ชัดไม่น้อยกว่าสองก็ แปดดังนั้นฉันมีบางงานที่ต้องทำ ดังนั้นตอนนี้จิตใจเราเป็นชั้น ขณะนี้อยู่ในสาขาอื่นที่ ซึ่งหมายถึงขั้นตอนที่สาม ครั้งแรกผมต้องจัดเรียง ซีกซ้ายขององค์ประกอบ ดังนั้นฉันจะไปเกี่ยวกับการทำเช่นนี้? ดีฉันจะชนิดของ จิตใจแบ่งรายการที่นี่ คุณจะได้ไม่ต้อง ร่างกายย้ายและฉัน จะมุ่งเน้นเฉพาะใน ซีกซ้ายขององค์ประกอบที่นี่ ดังนั้นฉันจะไปเกี่ยวกับการเรียงลำดับ รายการตอนนี้ที่มีขนาดสี่ คืออะไร? ขั้นตอนวิธีของฉัน ครั้งแรกที่ผมตรวจสอบ n น้อยกว่าสองไม่มี ดังนั้นผมจึงดำเนินการต่อไปบล็อกอื่นอีกครั้ง ครึ่งเรียงซ้ายขององค์ประกอบ 

ดังนั้นตอนนี้อีกครั้งจิตใจ และนี่คือที่ คุณต้องได้รับจำนวนมาก ประวัติศาสตร์ทางจิตถ้าคุณจะ ตอนนี้ฉันกำลังเรียงลำดับด้านซ้าย ครึ่งหนึ่งของซีกซ้าย สิทธิทั้งหมดดังนั้นตอนนี้ที่ผมเรียกรวมกันของฉัน การเรียงลำดับขั้นตอนวิธีเป็น n น้อยกว่าสอง? ไม่เป็นสองดังนั้นฉันต้องจัดเรียง ครึ่งซ้ายและครึ่งขวา ดังนั้นที่นี่เราไปจัดเรียงซีกซ้าย ทำไมคุณไม่เพียงแค่ ใช้เวลาหนึ่งก้าวไปข้างหน้า คุณชื่ออะไร? 

ผู้ชม: คาร์เรน 

ลำโพง: แดน และได้ก้าวไปข้างหน้า 

ผู้ชม: คาร์เรน ลำโพง: คาร์เรนทำ คุณพูดว่าคาร์เรนแดนหรือ? 

ผู้ชม: คาร์เรน 

ลำโพง: คาร์เรน ตกลงคาร์เรนได้ก้าว ไปข้างหน้าและเขาจะเรียงตอนนี้ และนี่คือเกือบ เรียกร้องขาดความผิดใช่มั้ย? ฉันไม่ได้จริงๆดูเหมือนจะประสบความสำเร็จ อะไร แต่ให้ดำเนินการต่อไป ตอนนี้ให้ฉันค้นหาที่พักที่เหมาะสม ครึ่งหนึ่งขององค์ประกอบ คุณชื่ออะไร? 

ผู้ชม: ลุค 

ลำโพง: ลุค Come on, ก้าวไปข้างหน้า ทำผมได้แยกลุค ซีกซ้ายจะเรียงตอนนี้และ ครึ่งขวาจะถูกจัดเรียงในขณะนี้ อีกครั้ง แต่มีขั้นตอนที่สำคัญที่นี่ ฉันจะทำอะไรต่อไปจะต้องทำอย่างไร รวมครึ่งแยก ตอนนี้เรากำลังจะมีเพียง ทุกคนกลับมาในทางนี้ เพราะผมชนิดของจำเ​​ป็น พื้นที่รอยขีดข่วนบาง มันเกือบจะเหมือนเหล่านี้ พวกที่อยู่บนโต๊ะ และฉันต้องการห้องพักบางส่วน ที่จะย้ายพวกเขาไปรอบ ๆ ดังนั้นฉันจะรวม พวกคุณโดยการมอง ที่ครึ่งซ้ายและครึ่งขวา และผู้ที่เห็นได้ชัดมาก่อน ครึ่งซ้ายหรือครึ่งหนึ่งใช่มั้ย? ดังนั้นครึ่งหนึ่งที่เหมาะสมจึงขอย้ายไปลุค ที่นี่ไปยังตำแหน่งเดิมของคาร์เรน และตอนนี้ที่จะรวมครึ่งซ้ายของพวกเขาใน คาร์เรนจะย้ายไปทางขวามี 

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

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

ผู้ชม: Adriano 

ลำโพง: Adriano Adriano จะเรียงตอนนี้ และสิ่งที่ชื่อของคุณ? 

ผู้ชม: อเล็กซ์ 

ลำโพง: อเล็กซ์จะเรียงตอนนี้ ครึ่งซ้ายครึ่งขวา สิ่งที่อยู่ในขั้นตอนสุดท้าย? การผสาน สวยน่ารำคาญดังนั้นฉัน จะไปรวมอยู่ในที่หก, ใช้ขั้นตอนกลับ แปดใช้ขั้นตอนกลับ และตอนนี้แจ้งให้ทราบนี้เป็น Takeaway มีประโยชน์อะไร ขณะนี้เป็นจริงประมาณครึ่งหนึ่งทางด้านซ้ายของ รายการโดยไม่คำนึงถึงวิธีการที่เราเริ่ม? มันจะถูกจัดเรียง 

ตอนนี้มันไม่ได้เรียงลำดับใน โครงการขนาดใหญ่ของสิ่งที่ แต่มันจะถูกจัดเรียงอย่างเป็นอิสระ ของอีกครึ่งหนึ่ง ตอนนี้สิ่งที่ขั้นตอนที่ฉันอยู่กับว่าฉันเก็บ rewinding ว่าเรื่องเริ่ม? ตอนนี้ฉันต้องจัดเรียงครึ่งขวา ดังนั้นตอนนี้เรากำลังย้อนกลับไปที่ จุดเริ่มต้นของเรื่อง และขอให้ทำเช่นนี้มากขึ้นอย่างรวดเร็ว ดังนั้นฉันจะต้องเรียงลำดับ ครึ่งขวาของรายชื่อทั้งหมด สิ่งที่ขั้นตอนต่อไปหรือไม่ เรียงครึ่งที่เหลือของครึ่งขวา เรียงครึ่งทางด้านซ้ายของ ครึ่งซ้ายครึ่งขวา และสิ่งที่ชื่อของคุณ? 

ผู้ชม: โอมาร์ 

ลำโพง: โอมาร์ก้าวไปข้างหน้าทำ ซีกซ้ายจะเรียง และสิ่งที่ชื่อของคุณ? 

ผู้ชม: คริส 

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

ผู้ชม: มารีน่า 

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

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

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

ดังนั้นตอนนี้ให้เสร็จสิ้นนี้ขึ้นอย่างรวดเร็ว ดังนั้นสามมาต่อไป แล้วสี่มาต่อไป และตอนนี้ห้ามาต่อไปแล้วหก เจ็ดและแปดแล้วในที่สุด รู้สึกเหมือนอัลกอริทึมที่ช้าที่สุด แต่ถ้าเราไม่ได้จริง เรียกใช้ในการจัดเรียงเดียวกัน ความเร็วนาฬิกาดังนั้นเพื่อ พูดแบบเดียวกับ ฟ้องนาฬิกาเหมือนก่อน ทำไม? ดีลองมา มองไปที่ผลสุดท้าย 

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

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

ผู้ชม: เข้าสู่ระบบ n 

ลำโพง: เข้าสู่ระบบ n แต่ก็มีขั้นตอนหนึ่งที่สำคัญอื่น ๆ อัลกอริทึมนี้ไม่ได้เข้าสู่ระบบขั้นตอน n ถ้ามันเป็นเพียง log n ขั้นตอน เราจะอยู่ในปัญหาเดียวกัน เหมือนก่อนหน้านี้ที่เราไม่สามารถ แน่ใจว่าทุกอย่างของการจัดเรียง คุณต้องมองไปที่น้อยที่สุดองค์ประกอบ n เพื่อให้แน่ใจว่า n องค์ประกอบเรียงลำดับ มิฉะนั้นมันเป็นก้าวกระโดดของความศรัทธา 

ดังนั้นจึงเป็นบันทึกน้อยที่สุด n ขั้นตอน แต่ สิ่งที่เกี่ยวกับขั้นตอนการผสมคีย์นี้ ที่ผมรวมครึ่งซ้ายและขวา ครึ่งและเดินข้ามเวที? วิธีการหลายขั้นตอนที่จะรวมคืออะไร? มันเป็น n แต่ฉันไม่ได้เพียงแค่ รวมครั้งสุดท้าย ในแต่ละสายซ้อนเหล่านั้นในแต่ละ ของผสานซ้อนกันนั้นผมก็ยังห่าง ฉันรวมทั้งสองคนแล้วสองคนนี้ คนจากนั้นทั้งสองคนและอื่น ๆ 

ดังนั้นผมจึงไม่รวมอีกครั้งและอีกครั้ง กี่ครั้ง? ดังนั้นทุกครั้งที่ผมแบ่ง รายการในช่วงครึ่งปีที่ฉันได้ผสาน แบ่งรายการในช่วงครึ่งปีทำผสาน ดังนั้นหากการแบ่งรายการ สามารถทำได้ล็อก n ครั้ง และการรวมกันในท้ายที่สุดจะใช้เวลา n ขั้นตอนสิ่งที่อาจจะตอนบน ผูกพันในการทำงาน เวลาของขั้นตอนวิธีของเราหรือไม่ n log n 

และแน่นอนว่าเป็นสิ่งที่ เราได้ประสบความสำเร็จที่นี่ ดังนั้นความรู้สึกที่คุณเห็นสายตาเมื่อ ทั้งสามสิ่งที่ทำงานเคียงข้าง เป็นกำลังสองกับ n n กำลังสองกับ n บันทึก n ซึ่งพื้นฐานที่เราจะเห็น วันนี้ไม่เพียง แต่ในอนาคต เป็นมากได้เร็วขึ้นมาก รอบของเสียงปรบมือสำหรับผู้ชายเหล่านี้ ผมจะตอบแทนพวกเขากับลูกความเครียด ขอเลื่อนการที่นี่ในวันนี้และ เราจะเห็นคุณในวันจันทร์ที่