>> [เล่นเพลง]
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! เอ้เอ้เอ้เอ้เอ้เอ้ย -
>> [เล่นกีตาร์]