[เล่นเพลง] 

เดวิดเจลัน: ทั้งหมดขวา ดังนั้นยินดีต้อนรับกลับ นี่คือ CS50 และเป็น ในตอนท้ายของสัปดาห์ที่สาม 

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

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

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

JENNIFER: [ได้ยิน] 

เดวิดเจลัน: ขอโทษ? 

JENNIFER: เจนนิเฟอร์ 

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

15 16 50 ทำได้อย่างดี ทั้งหมดขวา ตบมือให้เจนนิเฟอร์ 

[APPLAUSE] 

ทั้งหมดขวา ดังนั้นสิ่งที่กลยุทธ์ของคุณเป็น ค้นหาหมายเลข 50? 

JENNIFER: อืมผมคิดว่าบางทีถ้า - [เงียบสงัด] 

เดวิดเจลัน: โอ้ ให้มันเป็นหนึ่งในสอง ดังนั้นกลยุทธ์ของคุณเป็น ค้นหาหมายเลข 50? 

JENNIFER: ดังนั้นฉันเพียงแค่เริ่มต้นที่ จุดเริ่มต้นที่จะเห็นสิ่งที่หมายเลขแรก แล้วก็ผมคิดว่าบางทีถ้า พวกเขากำลังเรียงลำดับฉันเพิ่งจะเก็บ แตะที่สูงขึ้น? 

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

JENNIFER: โอ้ที่รัก 

เดวิดเจลัน: อ่า 

JENNIFER: ดังนั้นฉันเพียงแค่มีโชคดี 

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

JENNIFER: ดังนั้นหากพวกเขาได้รับการเรียงลำดับผม คิดว่าบางทีที่เล็กที่สุดไปหามากที่สุด 

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

JENNIFER: หรือถ้านี้จบลงด้วยการ ใหญ่จริงๆแล้วที่ใหญ่ที่สุดไปหาน้อยที่สุด 

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

JENNIFER: ทั้งหมดของพวกเขา 

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

JENNIFER: ใช่ 

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

JENNIFER: ตกลง 

เดวิดเจลัน: - ก่อนหน้านี้? 

JENNIFER: เริ่มต้นให้ กับครั้งแรกหนึ่ง 

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

JENNIFER: 4 มีขนาดเล็กจริงๆ ดังนั้นหากพวกเขากำลังจัดเรียงอาจจะมีขนาดเล็กที่สุด ที่ใหญ่ที่สุดที่ควรจะเป็น เป็นสองนั้นและ - 

เดวิดเจลัน: ตกลง ลองดูที่คุณคิดว่า? 

JENNIFER: ลองครั้งหนึ่ง ไนซ์ 

เดวิดเจลัน: ทำอย่างมาก ทั้งหมดขวา 

[APPLAUSE] 

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

JENNIFER: ตกลง 

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

JENNIFER: กลับไปที่จุดเริ่มต้น 

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

JENNIFER: ถ้าฉันไม่ได้ รู้ว่าพวกเขาเรียง 

เดวิดเจลัน: ถูกต้อง ดีถ้าคุณไม่ได้รู้ว่า พวกเขาจะถูกจัดเรียง - 

JENNIFER: โอ้ไม่ทราบว่าใช่ 

เดวิดเจลัน: - แต่คุณไม่ได้ ทราบว่าเป็น 50 หรือยัง? 

JENNIFER: เพียงแค่เก็บไป 

เดวิดเจลัน: ทั้งหมดขวา ตกลง เก็บไป ตกลงว่าผมสามารถทำงานร่วมกับ 

JENNIFER: ตกลง 

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

JENNIFER: เชิงเส้น - 

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

JENNIFER: เริ่มที่ตรงกลาง 

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

JENNIFER: ไปในช่วงครึ่งปีนี้ 

เดวิดเจลัน: และทำไมไปทางขวา? 

JENNIFER: หากพวกเขาจัดเรียงของที่เล็กที่สุด ที่ใหญ่ที่สุดแล้วควรจะเป็น 50 ในตอนท้ายว่า 

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

JENNIFER: 16 ดังนั้นยังคงมีขนาดเล็กสวย, เมื่อเทียบกับ 50 ดังนั้นบางทีฉันจะพยายาม, เช่นนี้เป็นหนึ่งใน 

เดวิดเจลัน: ทั้งหมดขวา 42 ทั้งหมดขวาดังนั้นตอนนี้สิ่งที่เป็นของคุณ สัญชาตญาณบอกคุณ? 

JENNIFER: ฉันสามารถโยนออกไป นี้แล้วก็ - 

เดวิดเจลัน: ตกลง ดีคุณสามารถโยนออกไป ซีกซ้ายมี 

JENNIFER: - เลือกหนึ่งนี้ 

เดวิดเจลัน: และขวา 

JENNIFER: ใช่ 

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

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

JENNIFER: หนึ่งนี้ควรเช่นอาจจะ ลดลงครึ่งหนึ่งเวลาหรือมากยิ่งขึ้นครับ 

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

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

1 SPEAKER: [ได้ยิน] 

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

JENNIFER: พี่ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[interposing VOICES] 

เดวิดเจลัน: อุ๊เสียใจ แมลง ทั้งหมดขวา ดีที่นี่เราไป หมายเลขห้า หมายเลขหก หนึ่งสองสามสี่ ห้าหกเจ็ด โอ้นี้เป็นที่น่าอึดอัดใจ 

2 SPEAKER: ฉันเพิ่งจะได้รับ - 

เดวิดเจลัน: จัดการที่ดี ทั้งหมดขวา ขอบคุณสำหรับการมีส่วนร่วม 

[APPLAUSE] 

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

เกรซ: สวัสดีครับผมเกรซ ฉันที่ในปี Leverett บ้าน 

แบรนสัน: Hi ผมแบรนสัน ผมน้องใหม่ในเชื่อม 

gabe: Hi ผมเกบ ฉันจูเนียร์ในแคบอต 

NEIL: ฉันนีล ฉันครั้งแรกในแมตทิว 

JASON: ฉันเจสัน ฉันครั้งแรกในกรี 

MIKE: ฉันไมค์ ผมน้องใหม่ในสีเทา 

JESS: ฉันเจ ฉันที่ในปี Leverett 

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

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

1 SPEAKER: น้อยไปหามากที่สุด 

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

1 SPEAKER: [ได้ยิน] 

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

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

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

gabe: ถูกต้อง 

เดวิดเจลัน: ถูกต้อง และเป็นหนึ่งในหก? Nope แลกเปลี่ยน เพื่อที่ว่าสองแลกเปลี่ยน หกและสาม? Nope แลกเปลี่ยน หกและเจ็ด? ดูดี เจ็ดห้า? 

JESS: [ได้ยิน] 

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

และตอนนี้สิ่งที่ควรอัลกอริทึมของฉัน เมื่อผ่านที่สองเป็นอย่างไร 

1 SPEAKER: สิ่งเดียวกัน 

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

ดังนั้นตอนนี้ที่นี่เราไปอีกครั้ง สองและสี่ เลขที่ และเป็นหนึ่งในสี่? ah, มีแน่นอนบางอย่าง ยังคงทำงานที่จะต้องทำ และสาม? ดี สี่และหก? หกห้า? หกและเจ็ด? ตกลงตอนนี้ทำ ตกลงไม่มี ผมต้องกลับไป 

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

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

1 SPEAKER: เลขที่ 

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

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

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

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

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

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

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

MIKE: ไมค์ 

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

NEIL: นีล 

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

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

จัดเรียงฟองดังนั้นขอเรียก n squared เวลาทำงานของอัลกอริทึมนี้ ประสิทธิภาพการทำงานของอัลกอริทึมนี้ ประสิทธิภาพของอัลกอริทึมนี้ เราก็ต้องอธิบายมากขึ้น โดยทั่วไปเป็น n squared ซึ่งเป็นสิ่งที่ดีเพราะผมสามารถทำอะไรได้ เช่นเดียวกันกับคนแปดคนเก้า คนล้านคนและที่ คำตอบไม่ได้จะเปลี่ยน 

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

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

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

ทุกวิธีทางที่จุดเริ่มต้น ดังนั้นนีลมาพร้อมกับผม และสิ่งที่เป็นชื่อของคุณอีกครั้ง? 

เกรซ: เก​​รซ 

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

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

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

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

JASON: เจสัน 

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

gabe: เกบ 

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

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

ลำโพงที่ 3: มัน n ขั้นตอน [ได้ยิน] 

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

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

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

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

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

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

แบรนสัน: 

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

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

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

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

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

[APPLAUSE] 

ทั้งหมดขวา มีคุณไป ขอบคุณสำหรับ - 

แบรนสัน: [เงียบสงัด] ตัวเลขให้ 

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

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

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

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

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

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

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

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

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

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

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

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

[interposing VOICES] 

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

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

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

ลำโพง 1: n 

เดวิดเจลัน: n ผมได้ยิน 

ลำโพง 1: 2 

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

[interposing VOICES] 

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

กรณีที่เลวร้ายทำงานคืออะไร เวลาของการจัดเรียงการเลือก? 

4 SPEAKER: n squared 

เดวิดเจลัน: n ตารางผมได้ยิน แต่ทำไม n ยืด, สังหรณ์ใจ? 

4 SPEAKER: เพราะเราก็ไม่ได้ 

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

5 SPEAKER: [ได้ยิน] 

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

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

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

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

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

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

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

[APPLAUSE]