>> [เล่นเพลง]
>> เดวิดเจลัน: ทั้งหมดขวา
ดังนั้นยินดีต้อนรับกลับ
นี่คือ 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]