[เล่นเพลง] 

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

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

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

ลัน ESTRADA: อืม เดวิดเจลัน: แท้จริง ปัญหาการฉีกขาดในช่วงครึ่งปี 

ลัน ESTRADA: โอ้ มิลลิเมตร ดีมาก. 

เดวิดเจลัน: OK ดี ขอขอบคุณ. ลัน ESTRADA: ดีมาก ตกลง. 

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

[หัวเราะ] 

ลัน ESTRADA: ใช่ฉัน think-- 

เดวิดเจลัน: ส่วนสิ่งที่เรามีอะไรบ้าง? ลัน ESTRADA: Mufflers ดังนั้น 

เดวิดเจลัน: OK แต่ไมค์สมิ ธ เป็นไป จะเป็นหลังจาก Mufflers So-- 

[หัวเราะ] 

ทั้งหมดขวา ลัน ESTRADA: เรามองหาที่ไหน? เดวิดเจลัน: ไมค์สมิ ธ ลัน ESTRADA: ไมค์สมิ ธ เดวิดเจลัน: ตอนนี้เรากำลังอยู่ในการผ่าตัด ตอนนี้แพทย์ Now-- 

ลัน ESTRADA: Let's- ให้เป็นไปด้วยความจริง จริง. 

เดวิดเจลัน: จริง ตกลง. หากคุณต้องการจริง ในขณะนี้ซึ่งทางไมค์สมิ ธ 

ลัน ESTRADA: วิธีนี้ 

เดวิดเจลัน: ทางไหน? ลัน ESTRADA: รอ M สิทธิ is--? เราเริ่มต้น with-- 

เดวิดเจลัน: ใช่ พวกเขากำลังที่เหลือ คุณถูก. 

ลัน ESTRADA: ใช่ 

เดวิดเจลัน: ดังนั้นไมค์ที่นี่ ลัน ESTRADA: อะไรนะ? 

[หัวเราะ] 

ตัวอย่างที่ไม่ดีครับ ขอโทษ เดวิดเจลัน: นี้จะสอน คุณจะกระโดดออกมาจากเก้าอี้ของคุณ 

ลัน ESTRADA: โอ้ โอ้ ผมมีคุณ ผมมีคุณ โอ้ โอ้ is-- นี้ตกลงฉันมีคุณ สมิ ธ ที่นี่? 

เดวิดเจลัน: สมิ ธ ขอขอบคุณ ดังนั้นฉันจะให้มองถึงสมิ ธ 

ลัน ESTRADA: โอ้ใช่ ไม่ไม่ไม่. ไม่นะ. นี่เป็นของฉัน. 

เดวิดเจลัน: โอ้คุณมีสมิ ธ ตกลง. 

ลัน ESTRADA: ใช่ฉัน สมิ ธ ได้ที่นี่ ขอโทษนะเพื่อน. ผมคิดว่าเรา Michael-- เขากำลังมองหาไมเคิล ขอโทษ 

เดวิดเจลัน: มันตกลง สิทธิทั้งหมดตอนนี้เรากำลัง เข้า Paccini และบุตร 

ลัน ESTRADA: Paccini และบุตรชาย เดวิดเจลัน: เฉพาะคุณ และผมอยู่ในนี้ ตกลง. พบกับเราไมค์สมิ ธ สมิ ธ 

ลัน ESTRADA: สมิ ธ 

เดวิดเจลัน: สมิ ธ เราอยู่ในอาขยะ ลัน ESTRADA: แย่มาก โอ้ นี้จะใช้เวลาสักครู่ 

[หัวเราะ] เดวิดเจลันรองเท้า เราอยู่ในรองเท้า 

ลัน ESTRADA: ตอนนี้เรากำลัง gonna-- 

เดวิดเจลัน: ดี ลัน ESTRADA: Which-- [หัวเราะ] โอ้นี้เป็นที่ดี [หัวเราะ] 

เดวิดเจลัน: มันตกลง 

ลัน ESTRADA: โอ้นี่เป็นสิ่งที่ดี ฉันไม่คิดว่าฉันจะ มีเพื่อน PSAT หลังจากนี้ เดวิดเจลัน: ดี กีฬา ลัน ESTRADA: กีฬา อืม, L, M, N, O, พี เดวิดเจลัน: OK ดังนั้นขอฉีกนี้ในช่วงครึ่งปี ไม่เป็นไร. จบไม่ดีนี้ต่อไปเพราะไมค์ สมิ ธ จะไม่อยู่ในสมุดหน้าเหลือง 

ลัน ESTRADA: Aw 

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

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

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

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

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

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

ผู้ชม: ตกลงดังนั้น L เป็นเหมือนกลาง C เป็นจุดเริ่มต้น บีเจก่อนที่แอลบีคิว 

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

CAROLINE: เอ็มมาหลังจากทุม 

เดวิดเจลัน: OK 

CAROLINE: ทุม เดวิดเจลันโอ้, ดี 

CAROLINE: อี 

เดวิดเจลัน: E, เอฟใช่ 

CAROLINE: T, U, โวลต์ 

เดวิดเจลัน: V, T, U, โวลต์ดังนั้นจึง ดูเหมือนว่าคุณกำลัง making-- เก็บไป ดูเหมือนว่าคุณกำลังทำ กองใหญ่กว่าที่นี่ และชนิดของกองใหญ่ที่นั่น ดังนั้นในช่วงครึ่งแรกของตัวอักษร ช่วงครึ่งหลังของตัวอักษร ตกลง. ดี การแยกชนิดของปัญหาที่เกิดขึ้นในสอง M, N, เอ็กซ์ใช่ CAROLINE: เค เดวิดเจลัน: OK เคดังนั้นคุณชนิดของการเลือก พวกเขาเป็นหนึ่งหลังจากที่อื่น วางไว้ทั้งซ้ายหรือขวา หรือไปซีบนพื้น ตกลง. 

CAROLINE: Z ที่เกิดขึ้นบนพื้น 

เดวิดเจลัน: OK Y ที่เกิดขึ้นบนพื้น ตอนนี้เราสามารถใส่เอ็กซ์ 

CAROLINE: กรัม เดวิดเจลัน: จีไปซ้าย S เป็นไปทางด้านขวา สิทธิทั้งหมดจะไปตลอดทางซ้าย 

CAROLINE: A, B, C, D 

เดวิดเจลัน: ตอนนี้ดี เรามี A, B, W ของซีจะลงไปที่นั่น ทั้งหมดขวาที 

CAROLINE: H, I, เจ เดวิดเจลัน: H, I, ดีเจ CAROLINE: ในศูนย์ที่ฉัน gonna-- เดวิดเจลัน: OK ดังนั้นตอนนี้เรากำลังจะชนิด การผสานกองต่างๆเหล่านี้ ดังนั้น A ถึง C แล้วฉันจะดูดีและ E, และ F และ G และ H, และฉันดี เจเคแล้วกองนี้ คว่ำ แต่ที่ตกลง ตรวจสอบว่า เราสามารถตัดบางมุม ตกลง. และจากนั้นเราต้อง W, X, Y, ซี 

CAROLINE: ใช่ 

เดวิดเจลัน: ยอดเยี่ยม ดังนั้นใหญ่ขอบคุณ แคโรไลน์สำหรับการเรียงลำดับเหล่านี้ 

[เชียร์] 

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

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

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

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

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

การสาธิต one-- นี้จะ ไปได้เร็วขึ้นและเร็วขึ้นในขณะนี้ มาลง คุณชื่ออะไร? เทรเวอร์: เทรเวอร์ 

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

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

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

เทรเวอร์: ที่หนึ่ง 

เดวิดเจลัน: เลขที่ 

เทรเวอร์: OK อันนี้. 

เดวิดเจลัน: ใช่ นั่นเป็นสิ่งที่ดี. ทั้งหมดขวา ดังนั้นสิ่งที่เป็นอัลกอริทึมของคุณหรือ ขั้นตอนในการทำเช่นนี้เทรเวอร์? 

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

เทรเวอร์: OK 

เดวิดเจลัน: มีอะไร ขั้นตอนวิธีการของคุณจะเป็นอย่างไร 

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

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

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

จำนวน -The 50? 

จำนวน -The 50 และคุณสามารถที่จะเปิดเผยสิ่งที่ ที่อยู่เบื้องหลังแต่ละประตูเหล่านี้ ง่ายๆโดยการสัมผัสด้วยนิ้วมือ ประณามมัน 

[หัวเราะ] 

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

-ตกลง. 

และอื่นถ้าคุณพบว่าคุณเก็บภาพยนตร์ หากคุณพบว่ามันไม่คุณจะให้มันกลับมา 

-ชาย. 

โอ้! 

- [ไม่ได้ยิน] ตกลง ดังนั้นฉันจะไปตรวจสอบปลาย ครั้งแรกเพื่อตรวจสอบว่า there's-- โอ้ 

[APPLAUSE] 

[จบเล่นภาพ] เดวิดเจลัน: OK ดังนั้นการเรียงลำดับประตูอย่างชัดเจน นำไปสู่​​การมีประสิทธิภาพมากขึ้น และเพื่อให้สองครั้งที่รวดเร็ว คือสิ่งที่ฉันมีความหมาย และเพื่อให้มีโชคดีเจทั้งสองครั้ง และเขายังมีโชคดีในการที่ผ่านมา ปีที่ผมสั่งบางแผ่น Blu-ray ที่จริงให้ออก ฉันขอโทษในปีนี้เรา ไม่ได้มีเดียวกันเทรเวอร์ แต่ดีกว่ายังคงเป็นไม่กี่ปีหลัง และบางส่วนของคุณอาจจะรู้ว่านี้ เพื่อนฌอนซึ่งเมื่อเขาอยู่ใน CS50, กำลังถูกท้าทายด้วยแน่นอน ปัญหาเดียวกันแม้ว่าใน SD, ในขณะที่คุณจะเห็นทันทีกลับในวันที่ และคุณจะพบว่าไม่เพียง แต่ เขาใช้เวลานานกว่าเจ นานกว่าเทรเวอร์ก็คือ จริงนี้โอกาสที่ยอดเยี่ยม จะมีส่วนร่วมเกือบทุกคนใน ฝูงชนลาราคาที่เหมาะสมให้กำลังใจ เขาไปหาตัวเลขที่เรากำลังมองหา ลอง ใช้ดูอย่างรวดเร็ว 

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

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

[หัวเราะ] 

มันไม่ได้เป็นคำถามเคล็ดลับ หนึ่ง 

[หัวเราะ] ณ จุดนี้คะแนนของคุณไม่ได้มาก ที่ดีดังนั้นคุณอาจรวมทั้งให้ไป สาม 

[หัวเราะ] 

ต่อไป. ตรงไปตรงมาผมไม่สามารถช่วย แต่สงสัย สิ่งที่คุณได้คิดเกี่ยวกับ so-- 

[หัวเราะ] เฉพาะแถวบนสุดเพื่อ คุณมีสามด้านซ้าย ดังนั้นหาฉันเจ็ด 

[หัวเราะ] 17 เซเว่น 

[APPLAUSE] 

ทั้งหมดขวา 

[จบเล่นภาพ] 

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

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

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

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

อันนัน: อันนัน 

เดวิดเจลัน: อันนัน เดวิด คุณชื่ออะไร? 

JOSEPH: โจเซฟ 

เดวิดเจลัน: โจเซฟ คุณเป็นอันดับสอง 

SERENA: เซเรน่าเลขที่สาม สเตฟาน, บ้านเลขที่สี่ CYNTHIA: ซินเทีย เดวิดเจลัน: ซินเทียหมายเลขห้า [ไม่ได้ยิน] เดวิดเจลัน: [ไม่ได้ยิน] เดวิดเลขหก MATT: แมตต์ เดวิดเจลัน: หมายเลขเจ็ดของแมตต์ และ? 

WAVERLY: เวเวอร์ลีย์ 

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

ที่ดีเยี่ยม ตกลง. ดังนั้นตอนนี้เรากำลังจะถาม คำถามที่แตกต่างกันไม่กี่ วิธีที่เราสามารถไปเกี่ยวกับการเรียงลำดับ คนเหล่านี้ขึ้นที่นี่? เพราะเรามีวิธีการไม่กี่ ก่อนหน้านี้โดยที่เราอยู่ ชนิดของการทำสองถังที่แตกต่างกัน แล้วเราโดยทั่วไป piecing สิ่งร่วมกัน ทันทีที่เราเห็นตัวเลขสอง ที่เป็นกัน เราเอามารวมกัน ตัวอักษรสองตัวที่อยู่ร่วมกัน 

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

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

ตกลง. ดังนั้นสองและสี่ให้ฉันไป ไปข้างหน้าและเพียงแค่สลับคุณทั้งสอง หากคุณสามารถย้ายร่างกาย ตัวเองและกระดาษของคุณ ฉันดูเหมือนจะมีอากาศ รายการอยู่ในสถานะที่ดีกว่า 

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

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

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

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

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

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

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

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

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

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

อันนัน: อันนัน 

เดวิดเจลัน: อันนัน และถ้าคุณสามารถเข้าร่วมเราได้ที่ จุดเริ่มต้นของรายการ ขอนำคุณที่คุณอยู่ Unfortunately-- คุณชื่ออะไร? 

STEFAN: สเตฟาน 

เดวิดเจลัน: สเตฟานเป็นในทาง ดังนั้นก่อนที่สเตฟานแก้นี้ ปัญหาสิ่งที่เราควรทำอย่างไร? เราจะทำอย่างไรกับสเตฟาน? 

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

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

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

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

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

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

JOSEPH: โจเซฟ 

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

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

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

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

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

JOSEPH: โจเซฟ 

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

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

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

อันนัน: อันนัน 

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

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

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

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

[APPLAUSE] 

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

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

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

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

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

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

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

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

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

ในความเป็นจริงถ้าคุณเปรียบเทียบในขณะนี้ 499,000,000,000 เลขที่ 999 ล้านบาท 500,000 กับค่าเดิมของเรา 500,000,000,000, มันจึงแช่งใกล้ ใช่มั้ย? n squared หารด้วย 2 จะช่วยให้ us-- หรือมากกว่า n squared หารด้วย 2 ทำให้เรา 500000000000 นั่นเป็นสาปสวยใกล้เคียง เพื่อ 499,999,500,000, ซึ่งก็คือการบอกว่าลบออก 500,000 หรือมากกว่าโดยทั่วไปลบออก n ยืดไม่ได้จริงๆเป็นเรื่องใหญ่ n ที่ทำให้สองเหล่านี้ ตัวเลขที่เติบโตอย่างรวดเร็วจริงๆ 

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

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

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

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

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

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

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

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

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

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

ตกลง. ฉันเรียกร้องในขณะนี้ก็อยู่ในสถานที่ แต่ตอนนี้ไม่ seven-- ที่เจ็ดไป? แน่นอนว่ามันจะไปมากกว่าที่นี่ ดังนั้นผมจึงต้องย้ายแปดมากกว่าที่เดียว ตอนนี้หกที่มันไม่ไป? ดีสิ่งที่ถูกต้อง ตอนนี้ผมต้องย้ายแปดมากกว่า สถานที่ที่เจ็ดและสถานที่ และจากนั้นผมป๋อมลงหก 

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

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

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

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

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

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

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

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

เพราะจะหาไมค์สมิ ธ ในโทรศัพท์ หนังสือหน้า n ในกรณีที่เลวร้ายที่สุด อาจใช้เวลา me n ขั้นตอน สิ่งที่เกี่ยวกับการเข้าร่วมประชุม? หนึ่งสองสามสี่ห้าหก. อะไรเวลาทำงานนี้ อัลกอริทึมสำหรับการเข้าร่วมประชุม? Big O ของ n เพราะในทฤษฎีฉัน ต้องชี้ทุกคนในห้อง 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[beeping] 

ด้วยเหตุนี้คุณกำลังใช้ความถี่ ขึ้นอยู่กับความสูงของบาร์บาร์ นี้จะเรียงลำดับฟอง 

[เหย beeping] 

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

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

และที่มัน เราจะเห็นคุณในครั้งต่อไป 

[whooshing และดนตรี]