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

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

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

ดังนั้น n squared และสิ่งที่เป็น n? 

ผู้ชม: จำนวนขององค์ประกอบ 

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

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

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

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

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

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

ตอนนี้วุฒิสมาชิกคุณที่นี่ที่ Google, และผมชอบที่จะคิดว่าการเป็นประธานาธิบดี ในขณะที่การสัมภาษณ์งาน 

[เสียงหัวเราะ] 

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

[เสียงหัวเราะ] -พวกคุณคิดว่าฉันล้อเล่น? มันถูกต้องที่นี่ วิธีที่มีประสิทธิภาพมากที่สุดที่จะคืออะไร จัดเรียงล้านจำนวนเต็มสองบิต? 

[เสียงหัวเราะ] 

ดี, UH - 

I'm-เสียใจ บางทีเราควร - 

ไม่มีไม่ไม่ไม่ไม่ 

ที่ไม่ได้ - ตกลง 

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

[เสียงหัวเราะ] 

[โห่ร้องปรบมือ] 

-Come เมื่อใครบอกเขานี้ ตกลง 

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

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

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

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

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

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

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

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

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

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

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

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

ดี O ใหญ่ของบันทึกของ n เราไม่ได้พูดคุยในรายละเอียดที่ดีเกี่ยวกับ นี้ แต่เราเคยเห็นแบบนี้มาก่อน ทำงานในสิ่งที่เรียกว่าลอการิทึมอะไร เวลาในกรณีที่เลวร้ายที่สุด? 

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

Big O 1 ดังนั้นเราจึง O ใหญ่ 2, O ใหญ่จาก 3 เวลาที่คุณต้องการเพียงจำนวนคงที่ เราเพียงแค่การจัดเรียงของเพียงแค่ลดความซับซ้อน ที่เป็นใหญ่ O 1 ถึงแม้ว่าถ้าแนบเนียนก็จะใช้เวลา 2 หรือ 100 ขั้นตอนถ้ามัน จำนวนคงที่ของขั้นตอน เราเพียงแค่พูดว่า O ใหญ่จากทั้งหมด 1 อัลกอริทึมที่อะไร ใน O ใหญ่ 1? 

ผู้ชม: การหาระยะเวลา ของตัวแปร 

DAVID ลัน: การหา ความยาวของตัวแปร? 

ผู้ชม: ไม่มีระยะเวลา ถ้ามันเรียงแล้ว 

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

ตรงกันข้ามกลับคิดว่าที่จะเกา คิดกลับไปในสัปดาห์แรกของ C, เพียงโทร printf และการพิมพ์ บางสิ่งบางอย่างบนหน้าจอเป็น arguably เวลาคงเพราะมันใช้เวลาเพียง บางส่วนของจำนวนรอบการทำงานที่จะแสดง ข้อความบนหน้าจอว่า หรือรอ - ไม่ได้หรือไม่ วิธีการอื่นที่เราอาจจะสร้างแบบจำลอง ประสิทธิภาพการทำงานของ printf? ใครบางคนต้องการที่จะไม่เห็นด้วยที่ บางทีมันอาจจะไม่ได้ตลอดเวลาจริงๆ สิ่งที่รู้สึกอาจ printf ทำงาน เวลาพิมพ์จริงสตริง หน้าจอเป็นสิ่งที่ อื่นที่ไม่ใช่ค่าคงที่ 

ผู้ชม: [ได้ยิน] 

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

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

ดังนั้นสิ่งที่เกี่ยวกับโอเมก้าของ n squared? สิ่งที่อัลกอริทึมคือการที่ดีที่สุดใน กรณีที่ยังคงเอา n squared ขั้นตอน? อ้าง? 

ผู้ชม: [ได้ยิน] 

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

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

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

หนึ่งในที่สุดของโอเมก้า n log n ดังนั้น n log n, ที่เราทำไม่ได้จริงๆ พูดคุยเกี่ยวกับ แต่ - 

ผู้ชม: ผสานเรียงลำดับ? 

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

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

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

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

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

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

ดังนั้นลองมาดูที่สิ่งที่ผสาน จัดเรียงเป็นจริงทั้งหมดเกี่ยวกับการ เป็นสิ่งดีๆที่ผสานการ จัดเรียงเป็นเพียงนี้ นี่คืออีกสิ่งที่เราเรียกว่า pseudocode เป็น pseudocode ไวยากรณ์ภาษาอังกฤษอย่าง และความเรียบง่ายคือ การจัดเรียงของที่น่าสนใจ 

ดังนั้นกับการป้อนข้อมูลขององค์ประกอบ n - เพื่อให้ เพียงแค่หมายความว่านี่คืออาร์เรย์ มันมีสิ่งที่ n ในนั้น นั่นคือทั้งหมดที่เรากำลังจะบอกว่ามี 

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

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

ผู้ชม: [ได้ยิน] 

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

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

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

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

[เสียงหัวเราะ] 

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

[เสียงหัวเราะ] 

DAVID ลัน: ฉันจริง ไม่แน่ใจว่ามันคืออะไร มันเป็นลูกความเครียด โคมไฟโต๊ะ? วัสดุ? อินเทอร์เน็ตหรือไม่ 

ตกลง เพื่อมาขึ้น ที่ต้องการ - ให้มา ลองมาดูกัน และสิ่งนี้ทำให้คุณอยู่ในสถานที่ - คุณอยู่ในสถานที่หนึ่ง UH-โอ้รอสักครู่ 1, 2, 3, 4, 5, 6, 7 - โอ้ดี สิทธิทั้งหมดที่เราไม่ดี ทั้งหมดถูกต้องทุกคนเพื่อให้มีที่นั่ง, แต่ไม่ได้อยู่บน Google แก้ว ผมขอคิวขึ้นเหล่านี้ คุณชื่ออะไร? 

MICHELLE: มิเชลล์ 

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

ขวาทั้งหมดเพื่อให้เรามีที่นี่ array ของ องค์ประกอบและอาร์เรย์ที่เป็นต่อ ชิ้นส่วนของกระดาษในคนเหล่านี้ ' มือไม่ได้เรียงปัจจุบัน 

MICHELLE: โอ้ที่แปลก 

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

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

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

ดังนั้นถ้าพวกคุณก็อาจถือได้ของคุณ ตัวเลขดังนั้นเราจะเห็นว่าคุณ แน่นอนการจับคู่ 4, 2, 6, 1, 3, 7, 8 ยอดเยี่ยม ดังนั้นฉันจะพยายามที่จะ orchestrate สิ่งที่ถ้าพวกคุณก็สามารถ ทำตามนำของฉันที่นี่ 

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

ผู้ชม: เรียงซีกซ้าย 

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

ผู้ชม: เรียงซีกซ้าย 

DAVID ลัน: เรียงซีกซ้าย ดังนั้นตอนนี้เหล่านี้นั่งที่นี่, เป็นรายการของขนาด 1 และสิ่งที่ชื่อของคุณอีกครั้ง? 

PRINCESS DAISY: เจ้าหญิงเดซี่ 

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

เรียงครึ่งขวาซึ่งเป็น - คุณชื่ออะไร? 

LINDA: ลินดา 

DAVID ลัน: ลินดา และเพื่อให้เราทำในสิ่งที่ทำตอนนี้ว่า เรามีรายชื่อของขนาด 1? 

ผู้ชม: ย้อนกลับ 

DAVID ลัน: ระวัง เรากลับมาเป็นครั้งแรกและตอนที่สาม ขั้นตอน - ชนิดและถ้าฉันเห็นภาพของมันด้วย กอดสองที่นั่งในขณะนี้ตอนนี้ฉัน มีการผสานทั้งสององค์ประกอบ ดังนั้นตอนนี้น่าเสียดายที่องค์ประกอบ มีการออกคำสั่ง แต่ที่ที่กระบวนการควบรวมกิจการ เริ่มที่จะได้รับที่น่าสนใจ 

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

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

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

ผู้ชม: ครึ่งขวา 

DAVID ลัน: เรียงครึ่งขวา ดังนั้นพวกคุณต้องทำเช่นนี้เช่นกัน ดังนั้นหากคุณสามารถลุกขึ้นยืน รอสักครู่? และสิ่งที่ your name? 

JESS: Jess 

DAVID ลัน: Jess OK เพื่อให้ Jess คือตอนนี้ทางด้านซ้าย ครึ่งหนึ่งของครึ่งขวา และเพื่อให้เธอเป็นรายการขนาด 1 เธอจัดเรียงอย่างเห็นได้ชัด และชื่อของคุณอีกครั้ง? 

MICHELLE: มิเชลล์ 

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

ย้อนกลับไปในเรื่อง สิ่งที่เป็นขั้นตอนต่อไปหรือไม่ 

ผู้ชม: ผสาน 

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

[เสียงหัวเราะ] 

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

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

1 SPEAKER: ทั้งหมดขวาดังนั้นตั้งแต่ ผมครึ่งซ้ายของ ครึ่งซ้ายฉันกลับ ใช่ไหม? 

DAVID ลัน: ดี 

ลำโพง 1: และจากนั้น - 

DAVID ลัน: ใคร ไมค์ไปที่ต่อไปหรือไม่ 

1 SPEAKER: หมายเลขถัดไป 

ลำโพง 2: ดังนั้นฉันครึ่งขวา ในช่วงครึ่งซ้ายของ ครึ่งซ้ายและเราจะกลับมา 

DAVID ลัน: ดี คุณจะกลับไป ดังนั้นตอนนี้ขึ้นต่อไปสำหรับคุณสองคืออะไร 

2 SPEAKER: เราต้องการดูว่ามีใครที่มีขนาดเล็ก 

DAVID ลัน: ว่า เราต้องการที่จะผสาน พื้นที่ที่เราจะใช้ในการผสาน คุณเข้าสู่แม้ว่าพวกเขากำลัง จัดเรียงอย่างเห็นได้ชัดแล้วเราจะ ที่จะทำตามขั้นตอนวิธีการเดียวกัน ดังนั้นไปในครั้งแรกที่? ดังนั้น 3 แล้ว 7 และตอนนี้ไมค์ไป เพื่อคนเหล่านี้, OK? 

3 SPEAKER: ดังนั้นฉันครึ่งทางด้านขวาของ ครึ่งซ้ายและ n ของฉันมีค่าน้อยกว่า 1 ดังนั้นฉันเพียงแค่จะผ่านไป - 

DAVID ลัน: ดี 

4 SPEAKER: ฉันครึ่งทางด้านขวาของ ครึ่งขวาของครึ่งขวาและฉัน นอกจากนี้ยังมีคนคนหนึ่งดังนั้นฉัน ไปกลับ ดังนั้นตอนนี้เรารวม 

3 ลำโพงดังนั้นเราจึงกลับไป 

DAVID ลัน: คุณกลับไปเป็น ดังนั้น 5 ไปก่อนแล้ว 8 และผู้ชมในขณะนี้ซึ่งเป็น ขั้นตอนที่เราต้องย้อนกลับในขณะนี้ กลับไปยังอยู่ในใจของเราหรือไม่ 

ผู้ชม: ผสาน 

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

3 ไปคร​​ั้งแรก แล้ว 5 อย่างเห็นได้ชัด แล้ว 7 และตอนนี้ 8 ตกลงตอนนี้เรามีอะไรบ้าง 

ผู้ชม: ไม่ได้ทำ 

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

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

ดังนั้นเราจึงวางมิเชลล์ที่นี่ และมี 2 จำนวนผู้ที่? 2 จำนวนมาที่ด้านหลังเช่นกัน 3 จำนวน? ยอดเยี่ยม 4 จำนวนจำนวน 5 หมายเลข 6, หมายเลข 7, 8 และจำนวน 

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

1 ลำโพงจะ log n จะ ทำลายเราขึ้นเป็นสอง - หารด้วยสองหลัก 

DAVID ลัน: ว่า เวลาที่เราเห็นในอัลกอริทึมจึงใด ไกลมีการรูปแบบนี้ หาร, หาร, หาร และจะลดลงเป็นปกติ บางสิ่งบางอย่างที่ ลอการิทึม log ฐาน 2 แต่จริงๆมันอาจเป็นอะไร, แต่เข้าสู่ระบบฐาน 2 

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

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

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

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

และนี่คือเหตุผลที่ดีกว่า ดีถ้าเรารู้อยู่แล้วว่าบันทึกที่ n คือดีกว่า n - ขวา? ที่เราเห็นในการค้นหาแบบไบนารี, สมุดโทรศัพท์ ตัวอย่างเช่น log n แน่นอน ดีกว่าเป็นเส้นตรง ดังนั้นนั่นหมายความว่าครั้ง n log n คือ แน่นอนดีกว่า n ครั้งอื่น n, AKA n squared และนั่นคือสิ่งที่เรารู้สึกว่าในที่สุด 

รอบใหญ่ดังนั้นจากเสียงปรบมือถ้า เราจะทำได้สำหรับคนเหล่านี้ 

[APPLAUSE] 

DAVID ลัน: พรากจากกันและของขวัญของคุณ - คุณอาจจะให้ตัวเลข หากคุณต้องการ และของที่ระลึกพรากจากกันของคุณได้ตามปกติ Oh, และเราจะส่ง ภาพมิเชลล์ ขอบคุณ ทั้งหมดขวา ช่วยตัวเองเพื่อลูกความเครียด 

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

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

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

ที่มันสำหรับขั้นตอนเดียว สำหรับขั้นที่สองซ้ำแล้วซ้ำเล่า รวมคู่ของรายการ 

DAVID ลัน: อืมมม เสียงเท่านั้นที่จะมา ออกจากคอมพิวเตอร์ของฉัน ลองนี้อีกครั้ง 

เพียงแค่เลือกที่พล - ตอนนี้เรามีสี่รายการ ก่อนที่จะเรียนรู้ 

DAVID ลัน: มีที่เราไป 

ผสาน-108 และ 15 เราจบ กับรายการ 15 108 ผสาน 50 และ 4 เรา จบลงด้วย 4, 50 ผสาน 8 และ 42 เรา จบลงด้วย 8, 42 และการรวม 23 และ 16 เรา จบลงด้วย 16, 23 

ตอนนี้สิ่งที่รายการของเรามี 2 ขนาด ขอให้สังเกตว่าแต่ละ สี่รายการจะเรียงลำดับตาม ดังนั้นเราจึงสามารถเริ่มต้นการควบรวมกิจการ คู่ของรายการอีกครั้ง ผสาน 15 และ 108 และ 4 และ 50 เรา ครั้งแรก 4 แล้ว 15 แล้ว 50 แล้ว 108 ผสาน 8, 42 และ 16, 23, ครั้งแรกที่เราใช้ 8 แล้ว 16 แล้ว 23, แล้ว 42 

ดังนั้นตอนนี้เรามีเพียงสองรายการขนาด 4 ซึ่งแต่ละอย่างจะถูกจัดเรียง ดังนั้นตอนนี้เรารวมทั้งสองรายการ ครั้งแรกที่เราใช้เวลา 4 แล้วเราใช้ 8 แล้วเราใช้เวลา 15 แล้ว 16 แล้ว 23 แล้ว 42 แล้ว 50 แล้ว 108 

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

DAVID ลัน: อีกครั้งแจ้งให้ทราบล่วงหน้าเขาไม่เคย สัมผัสถ้วยที่กำหนดมากกว่าหนึ่งครั้ง หลังจากที่ก้าวหน้าเกินกว่าที่มัน ดังนั้นเขาจึงไม่เคยซ้ำ ดังนั้นเขาจึงมักจะย้ายไปที่ด้านข้าง, และนั่นคือสิ่งที่เราได้ n ของเรา 

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

ดังนั้นสังเกตเห็นว่าคุณจะได้รับครึ่งหนึ่งเหล่านี้หรือ สี่เหล่านี้หรือ eighths เหล่านี้ ปัญหาที่ทั้งหมดในทันที เริ่มต้นที่จะใช้รูปทรงที่ดี และแล้วในที่สุดคุณจะเห็นที่ ปลายมากที่แบม, ทุกอย่างรวมกัน 

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

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

นี้จะเรียงลำดับการแทรก 

[เสียง PLAYING] 

DAVID ลัน: อีกครั้งพยายาม แทรกแต่ละองค์ประกอบ ในที่ที่มันเป็น นี้จะเรียงลำดับฟอง 

[เสียง PLAYING] 

DAVID ลัน: และคุณสามารถเรียงลำดับจากความรู้สึก วิธีการที่ค่อนข้างน้อยทำงานก็ทำ แต่ละขั้นตอน นี่คือสิ่งที่น่าเบื่อเสียงเหมือน 

[เสียง PLAYING] 

DAVID ลัน: นี้จะเรียงลำดับการเลือก, ที่เราเลือกองค์ประกอบที่เราต้องการโดย จะผ่านอีกครั้งและอีกครั้งและอีกครั้ง และวางไว้ที่จุดเริ่มต้น 

[เสียง PLAYING] 

DAVID ลัน: นี่คือการจัดเรียงรวมกันซึ่ง จริงๆคุณสามารถเริ่มต้นที่จะรู้สึก 

[เสียง PLAYING] 

[เสียงหัวเราะ] 

DAVID ลัน: สิ่งที่เรียกว่าคำพังเพย เรียงลำดับซึ่งเราไม่ได้มองที่ 

[เสียง PLAYING] 

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

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

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

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

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

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

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

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

แต่อีกครั้งนี้ยังไม่เพียงพอ เราต้องดำน้ำลึกลงไปใน ซึ่งหมายความว่าเราจะต้องตอบ คำถามสิ่งที่เป็นของ T-8? ดี T จาก 8 เพียง 2 ครั้ง T จาก 4 บวก 8 ดีว่า T จาก 4 อะไร T จาก 4 เป็นเพียงครั้ง T 2 จาก 2 บวก 4 ดี T จาก 2 อะไร T จาก 2 เป็นเพียง 2 ครั้งที 1 บวก 2 

และอีกครั้งที่เราไม่ชนิดของการ ติดอยู่ในวงจรนี้ แต่มันเกี่ยวกับการที่จะตีว่า กรณีฐานที่เรียกว่า เพราะสิ่งที่ T 1 เราไม่เรียกร้อง? 0 ดังนั้นตอนนี้ในที่สุดเราสามารถทำงานไปข้างหลัง 

ถ้า T จาก 1 เป็น 0 ตอนนี้ผมสามารถกลับไปขึ้นหนึ่ง สายผู้ชายคนนี้ที่นี่และฉันสามารถ เสียบ 0 T 1 ดังนั้นหมายความว่าเท่ากับครั้งที่ 2 ศูนย์ หรือที่เรียกว่า 0, บวก 2 และเพื่อให้การแสดงออกของทั้ง 2 

ตอนนี้ถ้าฉันใช้เวลา T 2, คำตอบ เป็น 2 เสียบลงในสายกลาง, T จาก 4 ที่ทำให้ผม 2 ครั้ง 2 บวก 4 ดังนั้น 8 ถ้าฉันแล้วเสียบใน 8 ถึงหน้าที่แล้ว เส้นที่ทำให้ผม 2 ครั้ง 8, 16 และถ้าเราแล้วดำเนินการต่อว่าด้วยความ 24 เพิ่ม 16 ในที่สุดเราได้รับ ค่าของ 64 

ขณะที่การจัดเรียงในและของตัวเองจากที่พูด ไม่มีอะไรที่จะสัญกรณ์ n, O ใหญ่, โอเมก้าที่เราได้ ได้พูดคุยเกี่ยวกับ แต่มันกลับกลายเป็นว่า 64 แน่นอน 16 ขนาดของอินพุท, เข้าสู่ระบบฐาน 2 จาก 16 และถ้าเป็นเพียงเล็กน้อยที่ไม่คุ้นเคยเพียง กลับคิดว่ามันจะกลับมา กับคุณในที่สุด ถ้าเป็น log ฐาน 2 ก็เช่น 2 ยกสิ่งที่ช่วยให้คุณ 16? โอ้ที่ 4 ดังนั้นจึงเป็นครั้ง 16 4 

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

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

ตอนนี้ออกกำลังกายน้อยความสนุกหากเราได้ เคยกระทำเช่นนี้ - และคุณอาจ จะได้ไม่ต้องเพราะการจัดเรียงของปกติ คนไม่คิดว่าการทำเช่นนี้ แต่ถ้าฉันไปที่ google.com และถ้า ฉันต้องการที่จะเรียนรู้บางสิ่งบางอย่างเกี่ยวกับ เรียกซ้ำตัวเองใส่ 

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

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

เราดังนั้นวิธีการไปเกี่ยวกับการทำเช่นนี้? ดีให้ฉันไปข้างหน้าและเขียน โปรแกรมด่วนที่นี่ ฉันจะไปข้างหน้าและทำ นี้ดังต่อไปนี้ ขอเรียกนี้ - สิ่งที่เราต้องการเรียกนี้หนึ่ง? 

ที่จริงไม่มี ผมขอย้อนกลับ ฉันไม่ต้องการที่จะทำ ยังน่าตื่นเต้น มันจะเสียความสนุกสนาน ขอทำนี้แทน 

สมมติว่าผมอยากจะเขียนเล็ก ๆ น้อย ๆ และโปรแกรมที่ตอนนี้อ้อมกอดนี้ ความคิดของการเรียกซ้ำ ชนิดของฉันได้ไปข้างหน้าของตัวเองมี ฉันจะทำต่อไปนี้ 

ครั้งแรกอย่างรวดเร็วรวมถึงมาตรฐาน io.h, เช่นเดียวกับการรวมของ cs50.h. แล้วฉันจะไปข้างหน้า และประกาศเป็นโมฆะหลัก int ในทางปกติ ฉันตระหนักฉันได้ misnamed ไฟล์ดังนั้น ให้ฉันเพียงแค่เพิ่ม. ขยายคที่นี่เพื่อให้ ที่เราสามารถรวบรวมได้อย่างถูกต้อง เริ่มฟังก์ชั่นนี้ออกไป 

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

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

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

ดังนั้นในระยะสั้นผมได้รับและ int จากผู้ใช้ ผมมั่นใจว่ามันเป็นบวก ฉันประกาศคำตอบที่เรียกว่าตัวแปร ชนิด int และเก็บในมันกลับมา ค่าของซิกผ่านใน n เป็น input แล้วฉันพิมพ์ออกมาตอบว่า 

แต่น่าเสียดายที่แม้ว่าซิกเสียง เหมือนบางสิ่งบางอย่างที่อาจจะมีใน ไฟล์ math.h การประกาศของ มันไม่จริง เพื่อที่ว่าตกลง ฉันสามารถใช้นี้เอง ฉันจะใช้ฟังก์ชั่นที่เรียกว่า ซิกและมันจะใช้เวลา พารามิเตอร์ - ให้เพียงเรียกมันเมตรเพียง ดังนั้นจึงเป็นเรื่องที่แตกต่างกัน แล้วขึ้นที่นี่ฉันจะบอกว่า ดีถ้า m มีค่าน้อยกว่า 1 - นี้เป็น น่าทึ่งมากโปรแกรม ดังนั้นฉันจะไปข้างหน้าและ ทันทีกลับ 0 มันก็ไม่ได้ทำให้ความรู้สึกที่จะเพิ่มขึ้นทั้งหมด ตัวเลขระหว่าง 1 และ ม. ถ้าเมตร ตัวเองเป็น 0 หรือเชิงลบ 

แล้วฉันจะไปข้างหน้า และทำซ้ำมาก ฉันจะทำเรียงลำดับของโรงเรียนเก่านี้ และฉันจะไปข้างหน้า และบอกว่าฉันกำลังจะไป ประกาศผลรวมเป็น 0 แล้วฉันจะมี สำหรับวงของ int - และแจ้งให้เราทำมันเพื่อให้ตรงกับของเรา รหัสการกระจายเพื่อให้คุณมีสำเนา ที่บ้าน int i ได้รับ 1 เมื่อขึ้นไป i น้อยกว่าหรือเท่ากับเมตร ผมบวกบวก แล้วภายในของนี้สำหรับวง - เราเกือบจะมี - ผลรวมจะได้รับผลบวกบวก 1 แล้วฉันจะกลับมารวมกัน 

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

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

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

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

แต่น่าเสียดายที่รหัสนี้ของ ไม่ได้ไปรวบรวมยัง หากฉันใช้ทำซิก 0 วิธี am ผมจะได้รับตะโกนใส่? มันเป็นสิ่งที่จะไม่ชอบ? 

ผู้ชม: [ได้ยิน] 

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

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

ดังนั้นตอนนี้ให้ฉันล้างหน้าจอ remake 0 ซิก ทั้งหมดดูเหมือนว่าจะตรวจสอบออก ให้ฉันทำงานซิก 0 บวกระหว่าง ฉันจะให้มันจำนวน 3 ให้มันง่าย ดังนั้นที่ควรให้ฉัน 3 บวก 2 บวก 1 ดังนั้น 6 ใส่และแน่นอนฉันได้รับ 6 

ฉันสามารถทำสิ่งที่ใหญ่กว่า - 50, 12, 75 เช่นเดียวกับที่สัมผัสผมจะทำ บางสิ่งบางอย่างที่ไร้สาระเช่นใหญ่จริงๆ จำนวน Oh, ที่จริงออกไปทำงาน - เอ๊ะฉันไม่คิดที่เหมาะสม ลองมาดูกัน Let 's ยุ่งกับมันจริงๆ 

นั่นเป็นปัญหา สิ่งที่เกิดขึ้น? รหัสไม่ใช่ว่าไม่ดี ก็ยังคงเป็นเส้นตรง Whistling เป็นผลดี แต่ สิ่งที่เกิดขึ้น? 

ไม่แน่ใจว่าฉันได้ยินมัน ดังนั้นมันจะเปิดออก - และ นี้เป็นกัน นี้ไม่ได้เป็นหลัก ความคิดของการเรียกซ้ำ มันจะเปิดออกเพราะฉันพยายามที่จะ เป็นตัวแทนของดังกล่าวเป็นจำนวนที่ใหญ่ที่สุด มีแนวโน้มที่จะมีการตีความผิด โดย C เป็นตัวเลขที่ไม่ดี, แต่จำนวนลบ 

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

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

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

ดังนั้นฉันจริง - ให้ฉันบันทึกแฟ้มนี้ ที่มีจำนวนรุ่นที่แตกต่างกัน เราจะเรียกรุ่นนี้ 1 แทน 0 และผมก็อ้างว่าฉันสามารถจริง reimplement นี้ในการเรียงลำดับของเรื่องนี้ ทางใจดัด 

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

อื่น ๆ - สังเกตเห็นสิ่งที่ฉันจะทำ อื่นฉันจะกลับมาเอ็มพลัส - ของ Sigma เมตรคืออะไร? ดีของ Sigma เมตรบวกลบ 1 เมตร, บวกลบ 2 เมตรบวกลบ 3 เมตร ฉันไม่ต้องการที่จะเขียนทั้งหมดออกว่า ทำไม่ได้เพราะเหตุใดฉันเพียงแค่ถ่อ? recursively เรียกตัวเองด้วยเล็กน้อย ปัญหาเล็กอัฒภาค และเรียกได้ว่าเป็นวัน? 

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

ผู้ชม: [ได้ยิน] 

DAVID ลัน: 23-26 ซึ่ง คือถ้าเงื่อนไขของฉัน เพราะมีอะไรที่ดีเกี่ยวกับ ลบที่นี่เพราะผมเก็บ ส่งซิกปัญหาที่มีขนาดเล็กมีขนาดเล็ก ปัญหาที่มีขนาดเล็ก - ยังไม่ได้ ครึ่งหนึ่งของขนาด เป็นเพียงขั้นตอนที่ทารกมีขนาดเล็กลง แต่ที่ตกลง เพราะในที่สุดเราจะทำงาน ทางลง 1 หรือ 0 ของเรา และเมื่อเรากด 0, ซิกไม่ จะเรียกตัวเองอีกต่อไป มันจะกลับทันที 0 

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

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

แต่ที่น่าตื่นเต้นที่ฉันไม่ ต้องการปล่อยให้เราเมื่อเป็นนี้ ให้ฉันไปข้างหน้าและเปิด ไฟล์จาก - จริงให้ฉันไปและ ทำเช่นนี้ได้อย่างรวดเร็วจริง ให้ฉันไปข้างหน้าและเสนอ ดังต่อไปนี้ ในรหัสของวันนี้ไฟล์นี้อยู่ที่นี่ หนึ่งนี้ที่นี่ noswap 

ดังนั้นนี่คือโปรแกรมเล็ก ๆ ที่โง่ วิปปิ้งขึ้นผมว่าการเรียกร้องที่จะทำ ดังต่อไปนี้ ในหลักของมันเป็นครั้งแรกที่ประกาศ เรียกว่า int x และกำหนดมัน ค่า 1 จากนั้นก็จะประกาศ int y และ จะกำหนดค่า 2 จากนั้นก็จะพิมพ์ออกจากสิ่งที่ x และ y คือ จากนั้นก็กล่าวว่าการแลกเปลี่ยน, dot dot dot 

จากนั้นก็จะอ้างว่าจะเรียกฟังก์ชั่น ที่เรียกว่า swap ผ่านใน x และ y, ความคิดของซึ่งเป็นที่หวัง x และ y จะกลับมา ที่แตกต่างกันตรงข้าม จากนั้นก็จะเรียกร้องเปลี่ยน! ที่มีเครื่องหมายอัศเจรีย์ จากนั้นก็จะพิมพ์ออก x และ y 

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

แต่ผมเรียกร้องว่าเมื่อฉันทำงานนี้ รหัสที่ผมจะทำตอนนี้ - ให้ฉันไปข้างหน้าและวางไว้ในที่นี่ ฉันจะเรียกนี้ noswap.c และเป็นชื่อที่แนะนำนี้ไม่ได้เป็น จะเป็นโปรแกรมที่ถูกต้อง ทำให้ noswap. swap / ไม่มี x 1, y คือ 2 แลกเปลี่ยน x 1, y คือ 2 นี้เป็นธรรมพื้นฐานแม้ แม้ว่านี้ดูเหมือนว่าสมบูรณ์แบบ ที่เหมาะสมกับผม และมีเหตุผล แต่เราไม่ จะเผยให้เห็นเหตุผลเพียง แต่ 

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

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

แต่ที่ร้องขอนี้ (กระซิบ) และคนเหล่านั้นออก ต้นจะไม่เสียใจมัน ในฐานะที่เป็นคนบนระเบียงที่มี ผมต้องขออภัยล่วงหน้าเพื่อ folks เมื่อ ระเบียงสำหรับเหตุผลที่จะ ล้างในเวลาเพียงสักครู่ 

เพื่อให้เรามีโชคดีที่มีหนึ่งใน CS50 ของพวกอดีตหัวหน้าการเรียนการสอนที่ บริษัท ที่เรียกว่า dropbox.com พวกเขาได้บริจาคเงินจำนวนมากอย่างไม่เห็นแก่ตัว คูปองรหัสที่นี่สำหรับพื้นที่มากนี้ ซึ่งเพิ่มขึ้นจาก ปกติ 2 กิกะไบต์ ดังนั้นสิ่งที่ฉันคิดว่าเราจะทำอะไรเกี่ยวกับเรื่องนี้ โน้ตตัวสุดท้ายคือทำบิตของแถม, ด้วยเหตุนี้ในเวลาเพียงสักครู่เราจะเปิดเผย ผู้ชนะและผู้ที่มีคูปอง รหัสที่คุณแล้วสามารถไปของพวกเขา เว็บไซต์พิมพ์ใน, และ voila รับ พื้นที่ Dropbox มากทั้งมากขึ้นสำหรับคุณ และเครื่องใช้สำหรับไฟล์ส่วนบุคคลของคุณ 

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

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

หนึ่งสองสาม 

[กรีดร้อง] 

-คุณจะได้รับรถ! คุณจะได้รับรถ! 

DAVID ลัน: เราจะเห็น คุณในวันพุธที่ 

-คุณจะได้รับรถ! คุณจะได้รับรถ! คุณจะได้รับรถ! คุณจะได้รับรถ! คุณจะได้รับรถ! 

DAVID ลัน: folks, ระเบียงมา ลงที่นี่ไปข้างหน้า ที่เรามีความพิเศษ 

ทุกคนได้รับรถ-! ทุกคนได้รับรถ! 

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

เล่าเรื่อง: ตอนต่อไป CS50 - 

5 SPEAKER: โอ้พุทโธ่เอ้ยเอ้ย my gosh! เอ้เอ้เอ้เอ้เอ้เอ้ย - 

[เล่นกีตาร์]