>> [เล่นเพลง]
>> ศาสตราจารย์: สิทธิทั้งหมด
นี่คือ CS50 และนี่คือ ในตอนท้ายของสัปดาห์ที่สาม
ดังนั้นเราอยู่ที่นี่ในวันนี้ไม่ได้อยู่ในแซนเดอ โรงละครแทนใน Weidner ห้องสมุด
ภายในซึ่งเป็นสตูดิโอ ที่รู้จักกันเป็น Hauser สตูดิโอ,
หรือเราจะว่าสตูดิโอ H หรือจะ เรา say-- ถ้าคุณชอบเรื่องตลกที่
ก็จริงจาก เพื่อนร่วมชั้นมาร์คออนไลน์
ที่แนะนำให้มากที่สุดผ่านทาง Twitter
ตอนนี้สิ่งที่ดีๆเกี่ยวกับ มาอยู่ที่นี่ในสตูดิโอ
คือว่าผมกำลังล้อมรอบด้วยสีเขียวเหล่านี้ ผนังหน้าจอสีเขียวหรือ chromakey,
เพื่อที่จะพูดซึ่งหมายความว่า CS50 ของ ทีมผู้ผลิตถิ่นกับผม
ตอนนี้อาจจะมีการวาง ผมมากที่สุดที่ใดก็ได้ในโลก
ให้ดีขึ้นหรือแย่ลง
>> ตอนนี้สิ่งที่อยู่ข้างหน้าปัญหาตั้ง ทั้งสองอยู่ในมือของคุณในสัปดาห์นี้
แต่ที่มีปัญหาตั้ง สามสัปดาห์นี้มา
คุณจะได้รับการท้าทายกับ เกมที่เรียกว่า 15
ความโปรดปรานของบุคคลที่เก่าที่ คุณอาจได้รับจำ
เป็นเด็กที่มีพวงทั้งหมด ของตัวเลขที่สามารถเลื่อนขึ้นลง
ซ้ายและขวาและมีหนึ่งช่องว่าง ภายในปริศนาลงไปในที่ที่คุณ
จริงสามารถเลื่อนชิ้นส่วนปริศนาเหล่านั้น
ในท้ายที่สุดคุณจะได้รับนี้ ปริศนาในการสุ่มบางกึ่ง
และมีเป้าหมายที่จะ จัดเรียงบนลงล่าง
จากซ้ายไปขวาจากที่หนึ่ง ตลอดทางขึ้นถึง 15
>> แต่น่าเสียดายที่การดำเนินการ คุณจะมีที่อยู่ในมือ
เป็นไปได้ซอฟแวร์ ตามร่างกายไม่ได้
คุณจริงจะต้องมีการเขียน รหัสที่เป็นนักศึกษาหรือผู้ใช้สามารถ
เล่นเกมที่ 15
และในความเป็นจริงในแฮ็กเกอร์ รุ่นของเกมที่ 15
คุณจะเป็นสิ่งที่ท้าทายในการดำเนินการ ไม่ได้เป็นเพียงการเล่นของโรงเรียนเก่า
เกม แต่แก้ ของมันการใช้โหมดพระเจ้า
เพื่อที่จะพูดที่จริง แก้ปริศนาสำหรับมนุษย์
โดยให้พวกเขาด้วยคำแนะนำ, หลังจากที่คำแนะนำหลังจากที่คำใบ้
ดังนั้นเพิ่มเติมว่าในสัปดาห์หน้า
แต่นั่นคือสิ่งที่อยู่ข้างหน้า
>> สำหรับตอนนี้จำได้ว่าสัปดาห์ก่อนหน้านี้ เรามีเรื่องราวที่น่าตื่นเต้นนี้ถ้าคุณจะ
โดยที่ดีที่สุดที่เรากำลังทำเรียงลำดับ ฉลาดเป็นขีด จำกัด บนของขนาดใหญ่ของ n o
ยกกำลังสอง
ในคำอื่น ๆ , การจัดเรียงฟอง เลือกการเรียงลำดับเรียงลำดับแทรก
ทั้งหมดของพวกเขาในขณะที่ที่แตกต่างกัน ในการดำเนินงานของพวกเขา
เงินทองเป็น n ยืดทำงาน เวลาในกรณีที่เลวร้ายที่สุดมาก
และเรามักจะคิดว่า กรณีที่เลวร้ายที่สุดสำหรับการเรียงลำดับ
เป็นสิ่งหนึ่งที่ปัจจัยการผลิตของคุณ จะสมบูรณ์ไปข้างหลัง
และแน่นอนมันต้องใช้เวลาค่อนข้างไม่กี่ขั้นตอน ในการดำเนินการแต่ละขั้นตอนวิธีการเหล่านั้น
>> ตอนนี้ที่ปลายสุดของชั้น การเรียกคืนเราเมื่อเทียบกับการจัดเรียงฟอง
กับการจัดเรียงตัวเลือกกับคนอื่น ๆ ที่เราเรียกว่าการจัดเรียงผสานในเวลานั้น
และผมเสนอว่าจะพา ประโยชน์จากบทเรียนจากสัปดาห์
ศูนย์แบ่งและพิชิต
และอย่างใดบรรลุชนิดของ ลอการิทึมเวลาทำงานที่สุด
แทนการบางสิ่งบางอย่าง ที่ล้วนกำลังสอง
และก็ไม่ได้ลอการิทึมมาก มันเป็นบิตมากขึ้นกว่าที่
แต่ถ้าคุณจำได้จากชั้นเรียน มันเป็นมากเร็ว
ลองมาดูที่ที่เราปล่อยออกมา
>> เมื่อเทียบกับการจัดเรียงฟองเลือก เมื่อเทียบกับการจัดเรียงผสานการเรียงลำดับ
ตอนนี้พวกเขากำลังทั้งหมดที่ทำงานใน ทฤษฎีในเวลาเดียวกัน
ซีพียูทำงานที่ความเร็วเท่ากัน
แต่คุณสามารถรู้สึกว่าน่าเบื่อนี้ เป็นอย่างมากได้อย่างรวดเร็วจะกลายเป็น
และเพียงแค่วิธีการที่รวดเร็วเมื่อเราฉีด บิตของขั้นตอนวิธีการศูนย์สัปดาห์,
เราสามารถเร็วขึ้น
>> ดังนั้นการจัดเรียงเครื่องหมายลักษณะที่น่าตื่นตาตื่นใจ
วิธีการที่เราสามารถใช้ประโยชน์จากมันในการสั่งซื้อ การเรียงลำดับจำนวนขึ้นอย่างรวดเร็ว
ดีขอคิดว่ากลับ ส่วนผสมที่เรา
ได้กลับมาในสัปดาห์ที่ศูนย์ของ หาคนที่อยู่ในสมุดโทรศัพท์
และจำได้ว่า pseudocode ที่เรานำเสนอ
ผ่านทางที่เราสามารถหา คนที่ชอบไมค์สมิ ธ
มองสิ่งเล็กน้อยเช่นนี้
>> ตอนนี้มาดูโดยเฉพาะ ที่เส้น 7 และ 8 และ 10 และ 11,
ซึ่งก่อให้เกิดห่วงว่าด้วยเหตุนี้เราเก็บไว้ จะกลับไปที่สาย 3 อีกครั้งและอีกครั้ง
และอีกครั้ง.
แต่มันกลับกลายเป็นว่าเราสามารถดู อัลกอริทึมนี้ที่นี่ใน pseudocode,
เล็ก ๆ น้อย ๆ แบบองค์รวม
ในความเป็นจริงสิ่งที่ฉันกำลังมองหา ที่นี่บนหน้าจอ
เป็นอัลกอริทึมสำหรับการค้นหาสำหรับ ไมค์สมิ ธ ในชุดของบางหน้า
และแน่นอนเราสามารถลดความซับซ้อนนี้ อัลกอริทึมในเส้นที่ 7 และ 8
และ 10 และ 11 ที่จะเพียงแค่พูดแบบนี้ ซึ่งผมได้นำเสนอที่นี่ในสีเหลือง
ในคำอื่น ๆ ถ้าไมค์ สมิ ธ เป็นก่อนหน้านี้ในหนังสือเล่มนี้
เราไม่จำเป็นต้องระบุขั้นตอน โดยขั้นตอนในขณะนี้ว่าจะไปหาเขา
เราไม่ได้มีการระบุ ที่จะกลับไปสาย 3
ทำไมเราไม่เพียง แต่ พูดมากกว่าปกติ
ค้นหาไมค์ใน ครึ่งซ้ายของหนังสือเล่มนี้
>> ตรงกันข้ามถ้าไมค์เป็น จริงต่อมาในหนังสือเล่มนี้
ทำไมเราไม่เพียงแค่พูดค้นหาได้นำมาอ้าง สำหรับไมค์ในช่วงครึ่งขวาของหนังสือเล่มนี้
ในคำอื่น ๆ ว่าทำไมเราไม่เพียง การเรียงลำดับของถ่อกับตัวเองว่า
ค้นหาไมค์ในครั้งนี้ ส่วนหนึ่งของหนังสือเล่มนี้
และปล่อยให้มีอยู่ของเรา ขั้นตอนวิธีการที่จะบอกเรา
วิธีการค้นหาในไมค์ ว่าครึ่งหนึ่งทางด้านซ้ายของหนังสือเล่มนี้
ในคำอื่น ๆ ของเรา ขั้นตอนวิธีการทำงานไม่ว่าจะเป็น
สมุดโทรศัพท์ของความหนานี้นี้ ความหนาหรือความหนาใด ๆ
เพื่อให้เราสามารถซ้ำ กำหนดขั้นตอนวิธีนี้
ในคำอื่น ๆ ที่ หน้าจอที่นี่เป็นอัลกอริทึม
สำหรับการค้นหาสำหรับไมค์สมิ ธ หมู่หน้าของหนังสือเล่มโทรศัพท์
ดังนั้นในบรรทัดที่ 7 และ 10 ขอ เพียงแค่บอกว่าที่
และฉันจะใช้ระยะเวลาสักครู่นี้ ที่ผ่านมาและแน่นอนการเรียกซ้ำ
เป็น buzzword สำหรับตอนนี้ และเป็นขั้นตอนนี้
การทำสิ่งใดโดยวัฏจักร โดยใช้รหัสที่คุณมีอยู่แล้ว
และเรียกมันอีกครั้ง และอีกครั้งและอีกครั้ง
ตอนนี้ก็จะมีความสำคัญ ที่เราด้านล่างอย่างใด
ออกและไม่ได้ทำมานานแล้วว่าเพียบ
มิฉะนั้นเรากำลังจะไป มีแน่นอนวง จำกัด
แต่ขอดูว่าเราสามารถยืมความคิดนี้ เรียกซ้ำของการทำอะไรบางอย่างอีกครั้ง
และอีกครั้งและอีกครั้งที่จะแก้ปัญหา ปัญหาที่เกิดขึ้นผ่านทางผสานการเรียงลำดับ
เรียงลำดับทั้งหมดที่มีประสิทธิภาพมากขึ้น
>> ดังนั้นผมจึงให้คุณผสานการเรียงลำดับ
ลองมาดู
ดังนั้นนี่คือรหัสจำลองด้วย ซึ่งเราสามารถใช้การเรียงลำดับ
โดยใช้วิธีที่เรียกว่าการจัดเรียงผสาน
และมันก็เป็นมากเพียงนี้
กับการป้อนข้อมูลขององค์ประกอบ n, ในคำอื่น ๆ ถ้าคุณ
รับ n องค์ประกอบและตัวเลขและ จดหมายหรือสิ่งที่นำเข้าคือ
ถ้าคุณได้รับองค์ประกอบ n ถ้า n คือน้อยกว่า 2 ผลตอบแทนเ​​พียง
ใช่มั้ย?
เพราะถ้า n เป็นน้อยกว่า 2 ที่ หมายความว่ารายชื่อขององค์ประกอบของฉัน
มีทั้งขนาด 0 หรือ 1 และ ในทั้งสองกรณีที่น่ารำคาญเหล่านั้น
รายการจะถูกจัดเรียงอยู่แล้ว
หากมีรายชื่อไม่ก็เรียง
และถ้ามีรายชื่อของความยาว 1 ก็เรียงอย่างเห็นได้ชัด
ดังนั้นขั้นตอนวิธีเพียงต้องการที่จะ จริงๆทำอะไรบางอย่างที่น่าสนใจ
ถ้าเรามีสองคนหรือมากกว่า องค์ประกอบให้กับเรา
ดังนั้นให้ดูที่วิเศษแล้ว
เรียงลำดับอื่นครึ่งซ้ายขององค์ประกอบ แล้วเรียงครึ่งขวาขององค์ประกอบ
รวมแล้วครึ่งเรียง
และสิ่งที่ชนิดของใจดัด ที่นี่เป็นที่ฉันทำไม่ได้จริงๆ
ดูเหมือนจะได้บอกคุณ อะไรเพียง แต่ใช่มั้ย?
ทั้งหมดที่ฉันได้กล่าวว่าจะได้รับรายชื่อของ n องค์ประกอบเรียงลำดับครึ่งซ้าย
แล้วครึ่งขวาแล้ว รวมครึ่งเรียงที่
แต่ที่เป็นซอสลับที่เกิดขึ้นจริง?
ที่ไหนขั้นตอนวิธีการคืออะไร?
ดีปรากฎว่าทั้งสองเส้น ครั้งแรกครึ่งหนึ่งที่เหลือการเรียงลำดับขององค์ประกอบ
และจัดเรียงทางขวาครึ่งหนึ่งขององค์ประกอบ สาย recursive เพื่อที่จะพูด
>> หลังจากที่ทุกคนที่นี้ จุดในเวลาที่ฉันต้อง
อัลกอริทึมที่ไปยัง เรียงลำดับทั้งกลุ่มขององค์ประกอบ?
ใช่
มันอยู่ที่นี่
มันอยู่ที่นี่ในหน้าจอและ เพื่อให้สามารถใช้ชุดเดียวกับขั้นตอน
การจัดเรียงครึ่งซ้าย เท่าที่จะทำได้ครึ่งหนึ่งที่เหมาะสม
และแน่นอนอีกครั้งและอีกครั้ง
ดังนั้นอย่างใดหรืออื่น ๆ และเราจะเร็ว ๆ นี้ เห็นนี้ความมหัศจรรย์ของการเรียงลำดับการผสาน
ถูกฝังอยู่ในที่สุดท้ายมาก สายการรวมครึ่งเรียง
และที่ดูเหมือนว่าค่อนข้างใช้งานง่าย
คุณจะใช้สองส่วนและคุณ อย่างใดรวมเข้าด้วยกัน
และเราจะเห็นนี้ เป็นรูปธรรมในช่วงเวลาที่
>> แต่นี้เป็นขั้นตอนวิธีการที่สมบูรณ์แบบ
และเรามาดูกันว่าทำไม
ดีสมมติว่าเรากำลังได้รับเหล่านี้เหมือนกัน แปดองค์ประกอบที่นี่บนหน้าจอหนึ่ง
ถึงแปด แต่พวกเขากำลัง เพื่อสุ่ม
และเป้าหมายที่อยู่ในมือคือ การจัดเรียงองค์ประกอบเหล่านี้
ดีฉันจะไปเกี่ยวกับ ทำมันใช้อีกครั้ง
ผสานเรียงลำดับตาม pseudocode นี้หรือไม่?
และอีกครั้งในนี้ติดตัว ใจของคุณเพื่อรอสักครู่
กรณีแรกสวย เล็ก ๆ น้อย ๆ ถ้ามันน้อยกว่า 2,
เพียงแค่กลับมามีงานที่จะทำไม่มี
ดังนั้นจริงๆมีเพียงสาม ขั้นตอนจริงๆที่จะเก็บไว้ในใจ
อีกครั้งและอีกครั้งผม จะต้องการที่จะมี
การจัดเรียงครึ่งซ้าย เรียงลำดับครึ่งขวา
และครั้งเดียวของพวกเขาแล้ว ทั้งสองส่วนมีการเรียงลำดับ
ฉันต้องการที่จะผสานเข้าด้วยกัน เข้าไปในรายการที่เรียงลำดับหนึ่ง
ดังนั้นเก็บที่ในใจ
>> ดังนั้นนี่คือรายการเดิม
ขอรักษานี้เป็น อาร์เรย์ที่เราเริ่มที่จะ
ในสัปดาห์ที่สองซึ่งเป็น บล็อกติดกันของหน่วยความจำ
ในกรณีนี้มีแปด ตัวเลขกลับไปกลับไปกลับ
และให้นำไปใช้ในขณะนี้การจัดเรียงผสาน
ดังนั้นครั้งแรกที่ผมต้องการเรียงลำดับ ครึ่งทางด้านซ้ายของรายการนี​​้
และขอดังนั้น มุ่งเน้นไปที่ 4, 8, 6, และ 2
>> ตอนนี้ฉันจะไปเกี่ยวกับ การเรียงลำดับรายการขนาด 4 หรือไม่?
ดีฉันจะต้องพิจารณาในขณะนี้ เรียงลำดับทางด้านซ้ายของครึ่งซ้าย
อีกครั้งขอย้อนกลับเพื่อรอสักครู่
ถ้าเป็น pseudocode นี้ และฉันได้รับแปดองค์ประกอบ
8 มากขึ้นอย่างเห็นได้ชัดคือ มากกว่าหรือเท่ากับ 2
ดังนั้นด้วยกรณีแรกใช้ไม่ได้
ดังนั้นในการจัดเรียงแปดองค์ประกอบแรกที่ผม เรียงลำดับครึ่งซ้ายขององค์ประกอบ
แล้วผมเรียงลำดับครึ่งขวาแล้วผมผสาน ทั้งสองส่วนที่เรียงลำดับแต่ละขนาด 4
ตกลง.
>> แต่ถ้าคุณได้เพียงแค่บอกผมว่าเรียงลำดับ ซีกซ้ายซึ่งขณะนี้มีขนาด 4
ฉันจะเรียงลำดับครึ่งซ้าย?
ดีถ้าฉันมี ป้อนข้อมูลของธาตุทั้งสี่
ครั้งแรกที่ผมเรียงลำดับซ้าย สองแล้วขวาสอง
และจากนั้นผมผสานเข้าด้วยกัน
ดังนั้นอีกครั้งมันจะกลายเป็นบิต ของจิตใจดัดเกมที่นี่
เพราะคุณชนิดของต้อง จำได้ว่าคุณจะอยู่ที่ไหนในเรื่อง
แต่ในตอนท้ายของวัน กำหนดจำนวนขององค์ประกอบใด ๆ
ก่อนอื่นคุณต้องการที่จะเรียงลำดับ ครึ่งซ้ายแล้วครึ่งขวา
แล้วผสานเข้าด้วยกัน
ขอเริ่มต้นที่จะทำตรงนั้น
นี่คือการป้อนข้อมูลของแปดองค์ประกอบ
ตอนนี้เรากำลังมองหาที่ซีกซ้ายที่นี่
ฉันจะเรียงลำดับธาตุทั้งสี่ได้อย่างไร?
ดีครั้งแรกที่ผมเรียงลำดับครึ่งซ้าย
ตอนนี้ฉันจะเรียงลำดับครึ่งซ้าย?
ดีฉันได้รับสององค์ประกอบ
ดังนั้นขอเรียงลำดับทั้งสององค์ประกอบ
2 มากกว่าหรือ เท่ากับ 2 ของหลักสูตร
ดังนั้นกรณีแรกที่ใช้ไม่ได้
>> ดังนั้นตอนนี้ผมมีการจัดเรียงซ้าย ครึ่งหนึ่งของทั้งสององค์ประกอบ
ครึ่งซ้ายของหลักสูตรเพียง 4
ดังนั้นฉันจะเรียงลำดับรายชื่อขององค์ประกอบหนึ่งหรือไม่?
ดีตอนนี้ที่ฐานกรณีพิเศษ ขึ้นด้านบนเพื่อที่จะพูด, มีผลบังคับใช้
1 น้อยกว่า 2 และของฉัน ย่อมเป็นรายการที่มีขนาด 1
ดังนั้นฉันเพิ่งกลับมา
ฉันไม่ได้ทำอะไร
และแน่นอนมองสิ่งที่ฉันได้ ทำ 4 จะถูกจัดเรียงอยู่แล้ว
เหมือนฉันแล้ว ที่ประสบความสำเร็จบางส่วนที่นี่
>> ตอนนี้ที่ดูเหมือนว่าชนิดของโง่ ที่จะเรียกร้อง แต่มันเป็นความจริง
4 เป็นรายการขนาด 1
มันเรียงแล้ว
นั่นเป็นครึ่งซ้าย
ตอนนี้ผมเรียงลำดับครึ่งหนึ่งที่เหมาะสม
การป้อนข้อมูลของฉันเป็นหนึ่งในองค์ประกอบที่ 8 ในทำนองเดียวกันเรียงแล้ว
โง่เกินไป แต่อีกครั้ง หลักการพื้นฐานนี้
เป็นไปเพื่อช่วยให้เราสามารถสร้างตอนนี้ ด้านบนของนี้ประสบความสำเร็จ
เรียง 4, 8 เรียงตอนนี้ สิ่งที่เป็นขั้นตอนสุดท้ายที่?
ดังนั้นขั้นตอนที่สามและครั้งสุดท้ายใด ๆ เวลาที่คุณกำลังเรียงลำดับรายการการเรียกคืน
คือการผสานสองครึ่ง ด้านซ้ายและด้านขวา
ดังนั้นเรามาทำตรงนั้น
ครึ่งซ้ายของฉันคือของหลักสูตร 4
ครึ่งขวาของฉันคือ 8
>> ถ้าอย่างนั้นเราทำเช่นนี้
ครั้งแรกที่ฉันกำลังจะไปจัดสรร บางหน่วยความจำเพิ่มเติม
ที่ฉันจะได้เป็นตัวแทนของที่นี่ เช่นเดียวกับอาร์เรย์รอง
ที่มีขนาดใหญ่พอที่จะใส่นี้
แต่คุณสามารถจินตนาการขยาย ที่สี่เหลี่ยมความยาวทั้งหมด
ถ้าเราต้องการเพิ่มเติมในภายหลัง
ผมใช้เวลา 4 และ 8 วิธีและผสาน ทั้งสองรายการที่มีขนาด 1 ด้วยกันไหม?
นี่เกินไปง่ายสวย
4 มาก่อนแล้วก็มาถึง 8
เพราะถ้าผมต้องการที่จะเรียงลำดับ ครึ่งซ้ายแล้วครึ่งขวา
แล้วรวมทั้งสองส่วน ร่วมกันในการเรียงลำดับ
4 มาก่อนแล้วก็มาถึง 8
>> ดังนั้นเราจึงดูเหมือนจะทำให้ความคืบหน้าแม้ แต่ผมยังไม่ได้ทำงานจริงใด ๆ
แต่อย่าลืมว่าเราอยู่ที่ไหนในเรื่อง
เราเดิมเอาแปดองค์ประกอบ
เราเรียงครึ่งซ้ายซึ่งเป็น 4
จากนั้นเราก็เรียงครึ่งซ้าย ครึ่งซ้ายซึ่งเป็น 2
และที่นี่เราไป
เรากำลังทำตามขั้นตอนที่ว่า
>> ดังนั้นหากเราได้เรียง ครึ่งซ้ายของ 2, ตอนนี้เรา
ต้องจัดเรียงครึ่งขวา 2
ดังนั้นในช่วงครึ่งขวาของ 2 ทั้งสองค่าที่นี่, 6 และ 2
ดังนั้นตอนนี้ให้มาใส่ของขนาด 2 และเรียงลำดับครึ่งซ้ายแล้ว
ครึ่งขวาแล้ว ผสานเข้าด้วยกัน
ดีฉันจะเรียงลำดับรายการที่มีขนาด 1, ที่มีเพียงหมายเลข 6 ได้หรือไม่?
ฉันทำมาแล้ว
รายการที่มีขนาด 1 ที่จะถูกจัดเรียง
>> ฉันไม่เรียงลำดับรายชื่อของผู้อื่นอย่างไร ขนาด 1 ครึ่งขวาที่เรียกว่า
ดีมันมากเกินไปจะถูกจัดเรียงอยู่แล้ว
หมายเลข 2 คือคนเดียว
ดังนั้นตอนนี้ฉันมีสองส่วนซ้ายและ ขวาฉันต้องผสานเข้าด้วยกัน
ผมขอให้ตัวเองบางพื้นที่พิเศษ
และใส่ 2 ในนั้น แล้ว 6 ในนั้นจึง
การเรียงลำดับรายการที่ซ้ายและขวา และการรวมกันในที่สุด
ดังนั้นผมอยู่ในรูปร่างที่ดีขึ้นเล็กน้อย
ฉันไม่ได้ทำเพราะอย่างชัดเจน 4, 8, 2, 6 ไม่ได้สั่งซื้อสุดท้ายที่ฉันต้องการ
แต่ตอนนี้ผมมีสองรายการที่มีขนาด 2 ที่ ทั้งสองตามลำดับการเรียง
ดังนั้นถ้าคุณย้อนกลับในใจของคุณ ตาที่ไม่ว่าปล่อยให้เรา?
ฉันเริ่มต้นด้วยแปดองค์ประกอบแล้วฉัน เหลาลงไปครึ่งซ้ายของ 4
แล้วครึ่งทางด้านซ้ายของ 2 แล้วครึ่งขวาของ 2,
ฉันเสร็จแล้วจึงเรียงลำดับซ้าย ครึ่งหนึ่งของที่ 2 และครึ่งขวาของ 2,
ดังนั้นสิ่งที่เป็นขั้นตอนที่สามและครั้งสุดท้ายที่นี่?
ฉันต้องรวมกัน สองรายการที่มีขนาด 2
ถ้าอย่างนั้นเราไปข้างหน้า
และบนหน้าจอที่นี่ให้ ฉันบางหน่วยความจำเพิ่มเติม
แม้ว่าในทางเทคนิคสังเกตเห็นว่าฉันได้ มีทั้งกลุ่มของช่องว่างขึ้นด้านบน
ที่นั่น
ถ้าผมต้องการที่จะเป็นโดยเฉพาะอย่างยิ่ง พื้นที่ที่มีประสิทธิภาพที่ชาญฉลาด
ฉันจะเริ่มต้นการย้ายองค์ประกอบ ไปมาบนและด้านล่าง
แต่เพื่อความชัดเจนภาพ ฉันจะวางมันลงด้านล่าง
เพื่อให้สิ่งที่ดีและสะอาด
>> ดังนั้นผมจึงได้มีสองรายการที่มีขนาด 2
รายการแรกมี 4 และ 8
รายการที่สองมี 2 และ 6
ลองผสานเหล่านั้น ร่วมกันในการเรียงลำดับ
2 ของหลักสูตรมาก่อน แล้ว 4 แล้ว 6 จากนั้น 8
และตอนนี้เราดูเหมือนจะได้รับ ที่ไหนสักแห่งที่น่าสนใจ
ตอนนี้ผมได้เรียงครึ่งหนึ่งของ รายการและบังเอิญมัน
ทั้งหมดแม้ตัวเลข แต่ที่ เป็นจริงเพียงแค่เรื่องบังเอิญ
และตอนนี้ผมได้เรียงซ้าย ครึ่งหนึ่งเพื่อที่จะเป็น 2, 4, 6, และ 8
ไม่มีอะไรออกมาของการสั่งซื้อ
ที่รู้สึกเหมือนความคืบหน้า
>> ตอนนี้มันรู้สึกเหมือนฉัน รับการพูดคุยตลอดไปตอนนี้
ดังนั้นสิ่งที่คงที่จะเห็นว่านี้ อัลกอริทึมเป็นจริงมีประสิทธิภาพมากขึ้น
แต่เรากำลังจะผ่าน มันสุดยอดระบบ
คอมพิวเตอร์ของหลักสูตร จะทำเช่นนั้น
เพื่อที่เรามีอะไรบ้าง
เราเริ่มต้นด้วยแปดองค์ประกอบ
ผมเรียงครึ่งซ้ายของ 4
ฉันดูเหมือนจะทำได้ด้วยการที่
ดังนั้นตอนนี้ขั้นตอนต่อไปคือการ เรียงลำดับครึ่งขวา 4
และส่วนนี้เราสามารถไป ผ่านน้อยมาก
ได้อย่างรวดเร็วถึงแม้ว่าคุณ ยินดีที่จะย้อนกลับหรือหยุดเพียง
คิดว่าผ่านได้ที่ ก้าวของคุณเอง แต่สิ่งที่
เรามีตอนนี้เป็นโอกาสให้กับ ขั้นตอนวิธีการทำเดียวกันแน่นอนสี่
ตัวเลขที่แตกต่าง
>> ถ้าอย่างนั้นเราไปข้างหน้าและมุ่งเน้นไปที่ ครึ่งขวาซึ่งเราอยู่ที่นี่
ครึ่งที่ด้านซ้ายของ ครึ่งขวาและตอนนี้
ครึ่งซ้ายของด้านซ้าย ครึ่งหนึ่งของครึ่งที่เหมาะสมนั้น
และฉันจะเรียงลำดับรายการที่มีขนาด 1 ที่มีเพียงหมายเลข 1?
มันทำมาแล้ว
ฉันจะทำเช่นเดียวกันสำหรับรายการ ขนาด 1 ที่มีเพียง 7?
มันทำมาแล้ว
ขั้นตอนที่สามสำหรับครึ่งนี้แล้ว คือการที่จะรวมทั้งสององค์ประกอบ
เป็นรายการใหม่ของขนาด 2, 1 และ 7
ดูเหมือนจะไม่ได้ทำทุก งานที่น่าสนใจมาก
ลองดูสิ่งที่เกิดขึ้นต่อไป
ฉันเพียงแค่เรียงครึ่งซ้ายของ ครึ่งขวาของการป้อนข้อมูลเดิมของฉัน
ตอนนี้ขอเรียงลำดับที่ถูกต้อง ครึ่งหนึ่งซึ่งมี 5 และ 3
ลองมาดูอีกครั้งด้านซ้าย ครึ่งเรียงครึ่งขวาเรียงลำดับ
และรวมทั้งสองเข้าด้วยกัน ในบางส่วนพื้นที่เพิ่มเติม
3 มาก่อนแล้วก็มาถึง 5
ดังนั้นตอนนี้เราได้เรียง ครึ่งซ้ายของครึ่งที่เหมาะสม
ของปัญหาเดิมและ ครึ่งขวาของครึ่งปีที่ที่เหมาะสม
ของปัญหาเดิม
ขั้นตอนที่สามและครั้งสุดท้ายคืออะไร?
ดีที่จะรวมทั้งสองส่วนเข้าด้วยกัน
เพื่อให้ฉันได้รับตัวเองบางส่วน พื้นที่พิเศษ แต่อีกครั้งฉัน
อาจจะใช้พื้นที่ว่างขึ้นด้านบน
แต่เรากำลังจะเก็บ มันง่ายสายตา
ผมขอรวมในตอนที่ 1 และ แล้ว 3 แล้ว 5 แล้ว 7
จึงทิ้งฉันตอนนี้มี ครึ่งขวาของปัญหาเดิม
ที่เรียงได้อย่างสมบูรณ์แบบ
>> ดังนั้นสิ่งที่เหลืออยู่?
ฉันรู้สึกเหมือนฉันให้บอกว่า สิ่งเดียวกันอีกครั้งและอีกครั้ง
แต่ที่สะท้อนแสงของ ความจริงที่ว่าเรากำลังใช้เรียกซ้ำ
กระบวนการของการใช้ ขั้นตอนวิธีการอีกครั้งและอีกครั้ง
ในส่วนย่อยขนาดเล็ก ปัญหาเดิม
ดังนั้นตอนนี้ผมได้เรียงซ้าย ครึ่งหนึ่งของปัญหาเดิม
ฉันมีครึ่งเรียงที่เหมาะสม ของปัญหาเดิม
อะไรคือขั้นตอนที่สามและครั้งสุดท้าย?
โอ้มันผสาน
ดังนั้นขอให้ทำอย่างนั้น
ขอจัดสรรเพิ่มเติมบางอย่าง หน่วยความจำ แต่พระเจ้าของเรา
สามารถใส่ได้ทุกที่ในขณะนี้
เรามีพื้นที่มากจึงมี ให้เรา แต่เราจะให้มันง่าย
แทนที่จะไปกลับ มากับหน่วยความจำเดิมของเรา
ขอเพียงแค่ทำมัน สายตาลงที่นี่ด้านล่าง
ที่จะเสร็จสิ้นการรวม ซีกซ้ายและอีกครึ่งหนึ่งที่เหมาะสม
>> ดังนั้นโดยการรวมสิ่งที่ฉันต้องทำอย่างไร
ฉันต้องการที่จะใช้องค์ประกอบในการสั่งซื้อ
ดังนั้นมองที่ครึ่งซ้าย ผมเห็นตัวเลขแรกคือ 2
ฉันมองไปที่ครึ่งขวา ผมเห็นตัวเลขแรก
1 เพื่อให้ชัดซึ่ง จำนวนฉันต้องการที่จะถอนออก
และใส่ครั้งแรกในรายการสุดท้ายของฉันได้อย่างไร
แน่นอน 1
ตอนนี้ผมต้องการที่จะถามคำถามเดียวกันว่า
ในครึ่งซ้ายฉัน ยังคงมีจำนวน 2
ในครึ่งขวา ฉันมีจำนวน 3
ฉันจะเป็นที่หนึ่งต้องการที่จะเลือก?
แน่นอนจำนวน 2 ตอนนี้สังเกตเห็นผู้สมัคร
4 ด้านซ้าย 3 ด้านขวา
ลองของหลักสูตรให้เลือก 3
ตอนนี้มีผู้สมัคร 4 ซ้าย 5 ด้านขวา
เราแน่นอนให้เลือก 4
6 ด้านซ้าย 5 ด้านขวา
เราแน่นอนให้เลือก 5
6 ด้านซ้าย 7 ด้านขวา
เราเลือก 6 และจากนั้นเรา เลือก 7 แล้วเราเลือกที่ 8
Voila
>> ดังนั้นจำนวนมากของคำพูดต่อมาเรา ได้เรียงรายการแปดองค์ประกอบนี้
เข้าไปในรายการหนึ่งถึงแปด ที่เพิ่มขึ้นกับแต่ละขั้นตอน
แต่วิธีการมากเวลาได้ มันพาเราไปทำอย่างนั้น
ดีฉันได้จงใจ สิ่งที่ออกมาวาง pictorially
ที่นี่เพื่อให้เราสามารถชนิดของ เห็นหรือชื่นชมส่วน
ในการชนะที่ได้รับการเกิดขึ้น
>> อันที่จริงถ้าคุณมองย้อนกลับไปที่การปลุก, ฉันซ้ายทั้งหมดของเส้นประเหล่านี้
ในผู้ถือสถานที่ที่คุณสามารถจะทำได้ ชนิดของการมองเห็นในการสั่งซื้อกลับ
ถ้าคุณชนิดของการมองย้อนกลับไปใน ประวัติศาสตร์ตอนนี้รายการเดิมของฉัน
เป็นของหลักสูตรที่มีขนาด 8
และจากนั้นก่อนหน้านี้ผมก็ การจัดการกับสองรายการที่มีขนาด 4
และจากนั้นสี่รายการที่มีขนาด 2 แล้วแปดรายการขนาด 1
>> ดังนั้นนี้ไม่ทำอะไร ชนิดของการเตือนของคุณ?
ดีจริงใด ๆ ขั้นตอนวิธีการที่เราได้
มองไปที่ป่านนี้ที่เรา หารและหารและหาร
ให้มีสิ่งอีกครั้งและ อีกครั้งส่งผลให้ในความคิดทั่วไปนี้
และเพื่อให้มีบางสิ่งบางอย่าง ลอการิทึมเกิดขึ้นที่นี่
และก็ไม่ได้เข้าสู่ระบบค่อนข้าง n แต่ มีองค์ประกอบลอการิทึม
กับสิ่งที่เราได้ทำเพียงแค่
>> ตอนนี้ขอพิจารณาวิธีการที่เป็นจริง
ดังนั้นการเข้าสู่ระบบของ n อีกครั้งเป็น เป็นเวลาการทำงานที่ดี
เมื่อเราได้สิ่งที่ต้องการ การค้นหาแบบไบนารีที่เราตอนนี้เรียกว่า
แบ่งและพิชิตกลยุทธ์ ผ่านทางที่เราพบไมค์สมิ ธ
ตอนนี้ในทางเทคนิค
นั่นเป็นฐานเข้าสู่ระบบที่ 2 ของ n แม้ แต่ในส่วนการเรียนคณิตศาสตร์
10 มักจะเป็นฐานที่คุณสมมติ
แต่นักวิทยาศาสตร์คอมพิวเตอร์เกือบตลอดเวลา คิดและพูดคุยในแง่ของฐานที่ 2
ดังนั้นโดยทั่วไปเราก็บอกว่าเข้าสู่ระบบของ n แทนการเข้าสู่ระบบฐานที่ 2 ของ n,
แต่พวกเขากำลังว่าหนึ่งและ เหมือนกันในโลกของคอมพิวเตอร์
วิทยาศาสตร์และเป็นกัน มีปัจจัยคง
ความแตกต่างระหว่างทั้งสองจึงเป็น สงสัยต่อไปด้วยเหตุผลที่เป็นทางการมากขึ้น
>> แต่ตอนนี้สิ่งที่เราสนใจ เกี่ยวกับการเป็นตัวอย่างนี้
ถ้าอย่างนั้นเราได้พิสูจน์โดยตัวอย่าง แต่ใน อย่างน้อยใช้ตัวอย่างของตัวเลขที่
ที่อยู่ในมือการตรวจสอบสติถ้าคุณจะ
ก่อนหน้านี้ดังนั้นสูตรเป็นฐานเข้าสู่ระบบ 2 n แต่สิ่งที่เป็น n ในกรณีนี้
ผมมีตัวเลขเดิม n หรือ 8 จำนวนเดิมโดยเฉพาะ
ตอนนี้จะได้รับเพียงเล็กน้อย ในขณะที่ แต่ฉันรัก
แน่ใจว่าการเข้าสู่ระบบฐาน 2 ของมูลค่า 8 3
และแน่นอนสิ่งที่ดีเกี่ยวกับการที่ ที่ 3 คือว่าจำนวนครั้งที่
ที่คุณสามารถแบ่งรายการ ความยาว 8 อีกครั้งและอีกครั้ง
และอีกครั้งจนกว่าคุณจะเหลือ กับรายการที่มีขนาดเพียง 1
ใช่มั้ย?
8 ไป 4 ไป 2 ไปที่ 1 และที่
สะท้อนของว่าที่ ภาพที่เรามีเพียงแค่ช่วงเวลาที่ผ่านมา
ดังนั้นการตรวจสอบสุขภาพจิตดีเล็ก ๆ น้อย ๆ เป็นที่ที่ ลอการิทึมที่มีส่วนเกี่ยวข้องจริง
>> ดังนั้นตอนนี้สิ่งอื่นที่เกี่ยวข้องกับที่นี่? n
แจ้งให้ทราบเพื่อให้ทุก เวลาที่ฉันแยกรายการ
แม้ว่าในลำดับที่กลับในประวัติศาสตร์ ที่นี่ผมก็ยังคงทำสิ่งที่ n
ขั้นตอนการควบรวมต้องมี ฉันสัมผัสทุกคนของตัวเลข
เพื่อที่จะเลื่อนลง ตำแหน่งที่เหมาะสมของ
ดังนั้นแม้ว่าความสูงนี้ แผนภาพเป็น n ล็อกขนาดของ n หรือ 3
โดยเฉพาะในคำอื่น ๆ ฉันไม่สามฝ่ายที่นี่
วิธีการทำงานมากผมทำในแนวนอน พร้อมแผนภูมิแต่ละครั้งนี้หรือไม่
>> ดีฉันไม่ได้ทำตามขั้นตอนของ n ทำงานเพราะถ้าฉันได้
มีธาตุทั้งสี่และสี่องค์ประกอบ และฉันต้องการที่จะรวมเข้าด้วยกัน
ฉันจะต้องไปผ่าน สี่เหล่านี้และสิ่งเหล่านี้สี่
ท้ายที่สุดจะผสานพวกเขา กลับเข้ามาในแปดองค์ประกอบ
ตรงกันข้ามถ้าฉันมีแปดนิ้ว มากกว่าที่นี่ซึ่งผมไม่ได้และแปด
fingers-- sorry-- ถ้าฉันได้ มีสี่นิ้วกว่าที่นี่
ซึ่งผมทำสี่นิ้ว มากกว่าที่นี่ซึ่งผมทำ
แล้วที่เดียวกัน ตัวอย่างเช่นเมื่อก่อนถ้าผมทำ
มีแปดนิ้วแม้ว่าจะอยู่ใน ทั้งหมดที่ฉันสามารถชนิดของการทำ
ผมว่าสามารถทำที่นี่ แล้วฉันสามารถอย่างแน่นอน
รวมทั้งหมดของรายการเหล่านี้ ขนาด 1 ร่วมกัน
แต่แน่นอนฉันต้องมอง ที่แต่ละองค์ประกอบครั้งว่า
ดังนั้นความสูงของกระบวนการนี​​้คือ n บันทึก ความกว้างของขั้นตอนนี้เพื่อที่จะพูด
เป็น n ดังนั้นสิ่งที่เราดูเหมือน ที่จะมีในที่สุดคือ
เป็นเวลาการทำงานของขนาด n log n ครั้ง
>> ในคำอื่น ๆ ที่เราแบ่งออก รายการบันทึก n ครั้ง
แต่ทุกครั้งที่เราทำที่เรามี สัมผัสทุกหนึ่งในองค์ประกอบ
เพื่อที่จะตัดพวกเขา ทั้งหมดเข้าด้วยกันซึ่ง
ถูก n ขั้นตอนเพื่อให้เรามีเวลา n log n, หรือเป็นนักวิทยาศาสตร์คอมพิวเตอร์จะพูดว่า
asymptotically ซ​​ึ่ง จะเป็นคำที่ยิ่งใหญ่
เพื่ออธิบายบน ผูกพันในเวลาทำงาน,
เรากำลังทำงานในขนาดใหญ่ o ของบันทึก n เวลาเพื่อที่จะพูด
>> ตอนนี้มีความสำคัญเพราะ จำสิ่งที่เวลาทำงานได้
มีการจัดเรียงฟองและการเลือก เรียงลำดับและการจัดเรียงแทรก
และแม้กระทั่งไม่กี่คนอื่น ๆ ที่มีอยู่ n squared คือที่ที่เราอยู่ที่
และคุณสามารถชนิดของโปรดดูที่นี่
ถ้า n ยกกำลังสองจะเห็นได้ชัด n ครั้ง n แต่ที่นี่เรามีครั้ง n log n,
และเรารู้อยู่แล้วว่าจากสัปดาห์ ศูนย์ n บันทึกที่ลอการิทึมที่
จะดีกว่าการเชิงเส้นบางสิ่งบางอย่าง
หลังจากที่ทุกคนจำภาพ ที่มีสีแดงและสีเหลือง
และสายสีเขียวที่เราเข้ามาที่ สายสีเขียวลอการิทึมเป็นที่ต่ำกว่ามาก
และดังนั้นจึงดีมากขึ้นและเร็วขึ้น กว่าเส้นเหลืองและสีแดงตรง
ครั้ง n log n มีจริงดีกว่า กว่าครั้ง n n หรือ n ยกกำลังสอง
>> ดังนั้นเราจึงดูเหมือนจะมี ระบุผสานอัลกอริทึม
การจัดเรียงที่ทำงานในมาก เวลาที่เร็วกว่าและแน่นอน
นั่นคือเหตุผลที่สัปดาห์ก่อนหน้านี้เมื่อ เราเห็นการแข่งขันระหว่างฟองที่
การเรียงลำดับเรียงลำดับการเลือกและผสาน เรียงลำดับผสานเรียงจริงๆได้รับรางวัลจริงๆ
และแน่นอนเราไม่ได้รอ สำหรับการจัดเรียงฟองและการเรียงลำดับการเลือก
จะเสร็จสิ้น
>> ตอนนี้ขอใช้เวลาหนึ่งผ่านอื่น ๆ นี้จากเล็กน้อย
มุมมองอย่างเป็นทางการใน กรณีนี้สะท้อนที่ดีขึ้น
กว่าการอภิปรายระดับที่สูงขึ้น
ดังนั้นนี่คือขั้นตอนวิธีการอีกครั้ง
ลองถามตัวเอง สิ่งที่เวลาทำงาน
เป็นขั้นตอนนี้ขั้นตอนวิธีการที่แตกต่างกัน?
ขอแบ่งออกเป็นครั้งแรก กรณีและกรณีที่สอง
ถ้าและอื่นในกรณีที่หาก ถ้า n เป็นน้อยกว่า 2 ผลตอบแทนเ​​พียง
รู้สึกเหมือนเวลาคง
มันเป็นชนิดของเช่นเดียวกับขั้นตอนที่สอง ถ้า n เป็นน้อยกว่า 2 แล้วกลับ
แต่ที่เรากล่าวว่าในวันจันทร์ที่ เวลาคงที่หรือใหญ่ o 1,
สามารถเป็นสองขั้นตอนที่สาม ขั้นตอนแม้ 1,000 ขั้นตอน
สิ่งที่สำคัญคือว่ามันเป็น จำนวนคงที่ของขั้นตอน
ดังนั้นสีเหลืองเน้น pseudocode ที่นี่ทำงานในเราจะเรียกว่า
เวลาคง
เพื่อให้มากขึ้นอย่างเป็นทางการและ เรากำลังจะ to-- นี้
จะมีขอบเขตที่เรา พิธีสิทธินี้ now-- T ของ n,
เวลาทำงานของปัญหา ที่ใช้เวลา somethings n เป็น input
เท่ากับใหญ่ o หนึ่ง ถ้า n เป็นน้อยกว่า 2
ดังนั้นจึงเป็นเงื่อนไขในการที่
ดังนั้นเพื่อให้มีความชัดเจนถ้า n มีค่าน้อยกว่า 2 เรามีรายการสั้นมากแล้ว
เวลาทำงาน, เสื้อของ n โดยที่ n คือ 1 หรือ 0 ในกรณีที่เฉพาะเจาะจงมากนี้
มันเป็นเพียงแค่จะเป็นเวลาอย่างต่อเนื่อง
มันจะใช้เวลาหนึ่ง ขั้นตอนที่สองขั้นตอนใด
มันเป็นจำนวนคงที่ของขั้นตอน
>> ดังนั้นส่วนฉ่ำก็จะต้องอยู่ใน กรณีอื่น ๆ ใน pseudocode
กรณีอื่น
เรียงครึ่งซ้ายขององค์ประกอบจัดเรียงทางขวา ครึ่งหนึ่งขององค์ประกอบรวม​​ครึ่งเรียง
นานเท่าไหร่ในแต่ละขั้นตอนเหล่านั้นใช้เวลา?
ดีถ้าการทำงาน เวลาในการจัดเรียงองค์ประกอบ n
คือขอเรียกว่ามาก ทั่วไป, เสื้อของ n,
แล้วคัดแยกซ้าย ครึ่งหนึ่งขององค์ประกอบ
เป็นชนิดของเช่นว่า T ของ n หารด้วย 2
และในทำนองเดียวกันการเรียงลำดับครึ่งหนึ่งที่เหมาะสม ขององค์ประกอบที่เป็นชนิดของเช่นว่า
T ของ n แบ่งออก 2 แล้ว ผสานครึ่งเรียง
ดีถ้าฉันมีบางอย่าง จำนวนขององค์ประกอบที่นี่
เช่นสี่และจำนวนบางส่วน ขององค์ประกอบที่นี่เช่นสี่
และฉันต้องผสานแต่ละเหล่านี้สี่ ในและแต่ละเหล่านี้สี่หนึ่ง
หลังจากที่อื่น ๆ เพื่อให้ ในที่สุดฉันมีแปดองค์ประกอบ
มันให้ความรู้สึกเช่นเดียวกับที่มีขนาดใหญ่ o ขั้นตอน n?
ถ้าฉันมีนิ้วมือและแต่ละ n พวกเขาจะต้องมีการควบรวมกิจการในสถานที่
ที่เหมือนขั้นตอน n อีก
>> ดังนั้น formulaically แน่นอน เราสามารถแสดงนี้
แม้ว่า scarily เล็ก ๆ น้อย ๆ ในตอนแรก ได้อย่างรวดเร็ว แต่มันเป็นบางสิ่งบางอย่าง
ที่จับตรรกะที่ว่า
เวลาทำงาน, เสื้อของ n ถ้า n มีค่ามากกว่าหรือเท่ากับ 2
ในกรณีนี้กรณีอื่นที่เป็นเสื้อของ n โดยแบ่งออกเป็น 2 บวกของ n T หารด้วย 2
บวกใหญ่ของ n o บาง จำนวนเชิงเส้นของขั้นตอน
อาจจะตรง n อาจจะ 2 ครั้ง n แต่ก็ประมาณลำดับของ n
เพื่อที่ว่าก็เป็นวิธีการที่เราสามารถ แสดง formulaically นี้
ตอนนี้คุณจะไม่ทราบว่านี้นอกจาก คุณได้บันทึกไว้ในใจของคุณ
หรือมองมันได้ใน ด้านหลังของตำราเรียนที่
อาจจะมีเล็ก ๆ น้อย ๆ โกงแผ่นที่สิ้นสุด
แต่นี่คือจริงไป ทำให้เรามีขนาดใหญ่ o ของ n n ล็อก,
เพราะการเกิดซ้ำที่ คุณเห็นที่นี่ในหน้าจอ
ถ้าคุณไม่จริงมันออกมาด้วย จำนวนอนันต์ของตัวอย่าง
หรือคุณคิดว่ามัน formulaically คุณจะ เห็นว่านี้เพราะสูตรนี้
ตัวเองเป็น recursive กับเสื้อของ n มากกว่าสิ่งที่ด้านขวา
และเสื้อของ n มากกว่าด้านซ้ายนี้สามารถ จะแสดงจริงในที่สุด
เป็นไปใหญ่ของ n ล็อก n
ถ้าไม่เชื่อว่า ดีสำหรับตอนนี้เพียงแค่
ใช้เวลาบนความเชื่อที่ว่าเป็นจริง สิ่งที่เกิดซ้ำที่นำไปสู่​​,
แต่เป็นเพียงเล็กน้อยของ วิธีการทางคณิตศาสตร์ที่จะมอง
ในเวลาทำงานของการจัดเรียงผสาน ขึ้นอยู่กับ pseudocode เพียงอย่างเดียว
>> ตอนนี้ขอใช้เวลาบิตของการเป็น ชีวิตจากทุกที่
และดูที่หนึ่ง สมาชิกวุฒิสภาบางอย่างในอดีตที่
อาจจะดูคุ้นเคยเล็ก ๆ น้อย ๆ ที่ทรุดตัวลงนั่งกับเอริคของ Google
ชมิดท์เวลาที่ผ่านมาสำหรับการสัมภาษณ์ บนเวทีในด้านหน้าของทั้งกลุ่ม
ของคนที่พูดคุยเกี่ยวกับในท้ายที่สุด หัวข้อที่สวยตอนนี้คุ้นเคย
ลองมาดู
>> Eric Sc​​hmidt: ตอนนี้สมาชิกวุฒิสภา คุณอยู่ที่นี่ที่ Google,
และผมชอบที่จะคิดว่า ประธานาธิบดีเป็นการสัมภาษณ์งาน
ตอนนี้มันเป็นเรื่องยากที่จะได้รับงานเป็นประธาน
ประธานาธิบดีโอบามา: ขวา
Eric Sc​​hmidt: และคุณ จะทำ [ไม่ได้ยิน] ในขณะนี้
นอกจากนี้ยังเป็นเรื่องยากที่จะได้รับงานที่ใช้ Google
ประธานาธิบดีโอบามา: ขวา
>> Eric Sc​​hmidt: เรามีคำถาม และเราถามคำถามที่ผู้สมัครของเรา
และเป็นหนึ่งในนี้มาจากลาร์รีชวิมเม
>> ประธานาธิบดีโอบามา: OK
>> Eric Sc​​hmidt: อะไรนะ?
พวกคุณคิดว่าฉันล้อเล่น?
มันอยู่ที่นี่
วิธีที่มีประสิทธิภาพมากที่สุดในการคืออะไร เรียงลำดับล้านจำนวนเต็ม 32 bit?
>> ประธานาธิบดีโอบามา: Well--
Eric Sc​​hmidt: บางครั้ง บางทีฉันขอโทษ maybe--
ประธานาธิบดีโอบามา: ไม่มีไม่มี ไม่มีไม่ฉัน think--
Eric Sc​​hmidt: ที่ไม่ it--
ประธานาธิบดีโอบามา: ฉัน คิดว่าผมคิดว่าฟอง
การเรียงลำดับจะเป็นวิธีที่ผิดไป
Eric Sc​​hmidt: มา
ใครบอกเขาว่านี้หรือไม่?
ตกลง.
ฉันไม่ได้วิทยาศาสตร์คอมพิวเตอร์ on--
>> ประธานาธิบดีโอบามา: เราได้ มีสายลับของเราในการมี
ศาสตราจารย์: สิทธิทั้งหมด
ขอปล่อยให้อยู่ข้างหลังเราตอนนี้ โลกทฤษฎีของขั้นตอนวิธี
ในการวิเคราะห์เชิง ดังกล่าวและกลับไปที่หัวข้อ
จากสัปดาห์ที่ศูนย์และหนึ่งและเริ่มต้น ที่จะเอาล้อการฝึกอบรมบาง
ถ้าคุณจะ.
เพื่อให้คุณเข้าใจจริงๆ ในท้ายที่สุดจากพื้นดินขึ้นสิ่งที่
ที่เกิดขึ้นภายใต้ประทุนเมื่อคุณ เขียนรวบรวมและรันโปรแกรม
จำโดยเฉพาะอย่างยิ่งว่านี่คือ โปรแกรม C แรกที่เรามองไปที่
ยอมรับโปรแกรมใช้งานง่าย แปลกค่อนข้างพูด
นั้น, พิมพ์มัน Hello World
และจำได้ว่าผมพูดว่ากระบวนการ รหัสแหล่งที่มาที่ไปผ่าน
คือตรงนี้
คุณจะใช้รหัสต้นฉบับของคุณผ่าน มันผ่านการคอมไพเลอร์เช่นเสียงดังกราว,
และออกมาพร้อมรหัสวัตถุที่ อาจมีลักษณะเช่นนี้ศูนย์และคน
ที่ CPU ของคอมพิวเตอร์ของกลาง หน่วยประมวลผลหรือสมอง
ในที่สุดเข้าใจ
>> ปรากฎว่าที่เป็น บิตของเปลือกที่
ว่าเราอยู่ในขณะนี้ ตำแหน่งที่จะหยอกล้อออกจากกัน
จะเข้าใจสิ่งที่ได้รับจริงๆ ที่เกิดขึ้นภายใต้ฝากระโปรง
เวลาที่คุณทำงานทุก เสียงดังกราวหรือมากกว่าปกติ
เวลาที่คุณทำให้โปรแกรมทุก ใช้ตรวจและ CF 50 IDE
โดยเฉพาะอย่างยิ่งสิ่งที่ชอบ นี้ถูกสร้างขึ้นครั้งแรก
เมื่อคุณรวบรวมโปรแกรมของคุณ
ในคำอื่น ๆ เมื่อคุณ ใช้รหัสต้นฉบับของคุณ
และรวบรวมสิ่งที่เป็นครั้งแรก ถูกออกมาโดยเสียงดังกราว
เป็นสิ่งที่รู้จักกันในชื่อรหัสการชุมนุม
และในความเป็นจริงมันมีลักษณะเหมือนกับนี้
>> ฉันวิ่งคำสั่งที่ บรรทัดคำสั่งก่อนหน้านี้
รีบเสียงดังกราวทุน s hello.c, และสร้างไฟล์
สำหรับผมเรียกว่า hello.s, ภายในซึ่งเป็นว่า
เนื้อหาเหล​​่านี้และน้อยมาก ด้านบนและด้านล่างขึ้นเล็ก ๆ น้อย ๆ
แต่ฉันได้ใส่ฉ่ำ ที่นี่ข้อมูลบนหน้าจอ
และถ้าคุณมองอย่างใกล้ชิดคุณจะเห็น อย่างน้อยไม่กี่คำหลักที่คุ้นเคย
เรามีหลักที่ด้านบน
เราได้ printf ลงตรงกลาง
และเรายังมีทักทายโลก n เครื่องหมายในเครื่องหมายคำพูดลงมาด้านล่าง
>> และทุกอย่างอื่นในที่นี่ เป็นคำแนะนำระดับที่ต่ำมาก
ที่ CPU ของคอมพิวเตอร์เข้าใจ
คำแนะนำของ CPU ที่ย้ายหน่วยความจำ รอบที่สายโหลดจากหน่วยความจำ
และท้ายที่สุดการพิมพ์ สิ่งที่อยู่บนหน้าจอ
ตอนนี้สิ่งที่เกิดขึ้น แต่หลังจากที่ รหัสการชุมนุมนี้ถูกสร้างขึ้น?
ในที่สุดคุณจะทำจริง ยังคงสร้างรหัสวัตถุ
แต่ขั้นตอนที่มีจริงๆ รับไปในใต้ฝากระโปรง
ดูเล็ก ๆ น้อย ๆ เช่นนี้
รหัสที่มาจะกลายเป็นรหัสการชุมนุม ซึ่งก็จะกลายเป็นรหัสวัตถุ
และทำงานที่นี่มีคำว่า เมื่อคุณรวบรวมซอร์สโค้ดของคุณ
ออกมาพร้อมรหัสการชุมนุมแล้ว เมื่อคุณรวบรวมรหัสการชุมนุมของคุณ
ออกมารหัสวัตถุ
>> ตอนนี้เสียงดังกราวมีความซับซ้อนสุด ชอบมากของคอมไพเลอร์ที่
และมันไม่ทุกขั้นตอนเหล่านี้ ร่วมกันและมันไม่จำเป็นต้อง
ออกกลางใด ๆ ไฟล์ที่คุณยังสามารถดู
มันก็จะรวบรวมสิ่งที่ ซึ่งเป็นคำทั่วไปที่
อธิบายถึงกระบวนการทั้งหมดนี้
แต่ถ้าคุณต้องการจริงๆ โดยเฉพาะอย่างยิ่งที่จะได้มี
มากขึ้นที่เกิดขึ้นมีทั้ง
>> แต่ขอยังพิจารณาว่าแม้ในขณะนี้ ว่าโปรแกรมง่ายสุด hello.c,
เรียกว่าฟังก์ชั่น
มันเรียกว่า printf
แต่ผมไม่ได้เขียน printf จริง ที่มาพร้อมกับคเพื่อที่จะพูด
มันเป็นฟังก์ชั่นการเรียกคืนที่ ประกาศใน io.h มาตรฐานซึ่ง
ไฟล์ส่วนหัวที่ เป็นเรื่องที่เราจะได้จริง
ดำน้ำในระดับความลึกมากขึ้นก่อนที่จะยาว
แต่ไฟล์ส่วนหัวเป็น มักจะมาพร้อมกับ
โดยไฟล์รหัสแฟ้มรหัสต้นฉบับดังนั้น เหมือนมีอยู่ io.h. มาตรฐาน
>> บางครั้งที่ผ่านมาใครบางคน หรือใครบางคนยังเขียน
ไฟล์ที่เรียกว่า io.c มาตรฐานใน ซึ่งคำจำกัดความที่เกิดขึ้นจริง
หรือการใช้งานของ printf, และอัดแน่นของฟังก์ชั่นอื่น ๆ
ถูกเขียนจริง
เพื่อให้ได้รับถ้าเราพิจารณามี ที่นี่ด้านซ้าย, hello.c ว่าเมื่อ
รวบรวมจะช่วยให้เรา hello.s แม้ว่า เสียงดังกราวไม่รำคาญประหยัดในสถานที่
เราสามารถมองเห็นมันและรหัสการชุมนุมว่า ได้รับการประกอบเป็น hello.o ซึ่ง
เป็นแท้จริงชื่อเริ่มต้น เมื่อใดก็ตามที่คุณได้รับการรวบรวมแหล่งที่มา
รหัสลงในรหัสวัตถุ แต่ไม่ ค่อนข้างพร้อมที่จะดำเนินการมันยัง
เพราะขั้นตอนอื่น ที่เกิดขึ้นและมี
ที่เกิดขึ้นที่ผ่านมาไม่กี่คน สัปดาห์ถิ่นอาจจะอยู่กับคุณ
>> โดยเฉพาะที่ใดที่หนึ่ง ใน CS50 IDE และนี้
เกินไปจะเป็นบิตของ เปลือกสักครู่
มีหรืออยู่กับเวลา ไฟล์ที่เรียกว่ามาตรฐาน io.c,
ว่าคนที่เรียบเรียง io.s มาตรฐานหรือเทียบเท่า
ว่าคนที่ประกอบแล้ว เข้า io.o มาตรฐาน
หรือมันจะเปิดออกเป็น ไฟล์ที่แตกต่างกันเล็กน้อย
รูปแบบที่สามารถมีที่แตกต่างกัน ไฟล์นามสกุลทั้งหมด
แต่ในทางทฤษฎีและแนวคิดว่า ขั้นตอนเหล่านั้นจะเกิดขึ้นได้ในบางรูปแบบ
ซึ่งก็คือการกล่าวว่าในขณะนี้ เมื่อผมเขียนโปรแกรม
hello.c ที่เพิ่งพูดว่าสวัสดีโลก และฉันใช้รหัสของคนอื่น
เช่น printf ซึ่งครั้งหนึ่งเคยอยู่บน เวลาในไฟล์ที่เรียกว่ามาตรฐาน io.c,
แล้วอย่างใดฉันต้องใช้เวลาของฉัน รหัสวัตถุศูนย์ของฉันและคน
และวัตถุของบุคคลนั้น รหัสหรือศูนย์และคน,
และอย่างใดเชื่อมโยงพวกเขาเข้าด้วยกันเป็น หนึ่งไฟล์สุดท้ายที่เรียกว่าสวัสดีที่
มีทั้งหมดของศูนย์และ คนจากฟังก์ชั่นหลักของฉัน
และทั้งหมดของค่าศูนย์ และคนสำหรับ printf
>> และแน่นอนว่าขั้นตอนสุดท้ายคือ ที่เรียกว่าการเชื่อมโยงรหัสวัตถุของคุณ
การส่งออกของที่ เป็นแฟ้มที่ปฏิบัติการ
ดังนั้นในความเป็นธรรมที่ ท้ายของวันที่ไม่มีอะไร
มีการเปลี่ยนแปลงตั้งแต่หนึ่งสัปดาห์เมื่อเรา แรกเริ่มรวบรวมโปรแกรม
อันที่จริงทั้งหมดนี้ได้รับการ ที่เกิดขึ้นภายใต้ประทุน
แต่ตอนนี้เราอยู่ในตำแหน่ง ที่เราสามารถทำได้จริง
หยอกล้อออกจากกันตามขั้นตอนต่างๆเหล่านี้
และแน่นอนในตอนท้าย ในวันนี้เราก็ยังคง
ทิ้งให้อยู่กับศูนย์และคนที่ เป็นจริงทำต่อดีในขณะนี้
ความสามารถของ C อีกว่า เราไม่ได้มีการใช้ประโยชน์จากโอกาสมากที่สุด
ถึงวันที่รู้จักในฐานะผู้ประกอบการระดับบิต
ในคำอื่น ๆ ป่านนี้เราได้ทุกที่ทุกเวลา จัดการกับข้อมูลใน C หรือตัวแปรใน C,
เราได้มีสิ่งที่ต้องการ และตัวอักษรลอยและอิน
และปรารถนาและคู่ผสมและชอบ แต่ ทุกคนเป็นอย่างน้อยแปดบิต
เราไม่เคยยังสามารถที่จะ จัดการบิตของแต่ละบุคคล
แม้ว่าบิตของแต่ละบุคคลเรา รู้ว่าสามารถเป็นตัวแทนของ 0 และ 1
ตอนนี้ก็ปรากฎว่าใน C คุณ สามารถได้รับการเข้าถึงบิตของแต่ละบุคคล
ถ้าคุณรู้ไวยากรณ์ ที่จะได้รับพวกเขา
>> ดังนั้นลองมาดู ผู้ประกอบการที่ค่าที่เหมาะสม
ภาพดังนั้นที่นี่เป็นสัญลักษณ์ไม่กี่ที่ เราได้ชนิดของการเรียงลำดับของ, เห็นมาก่อน
ฉันเห็นเครื่องหมายเป็นแนวตั้ง บาร์และอื่น ๆ ได้เป็นอย่างดี
และจำได้ว่าเครื่องหมายเครื่องหมาย เป็นสิ่งที่เราได้เห็นมาก่อน
ตรรกะและผู้ประกอบการที่คุณมี พวกเขาทั้งสองร่วมกันหรือตรรกะหรือ
ผู้ประกอบการที่คุณ มีสองแถบแนวตั้ง
ผู้ประกอบการระดับบิตซึ่งเราจะ เห็นทำงานบนบิตเป็นรายบุคคล
เพียงแค่ใช้เครื่องหมายเดียว แถบแนวตั้งเดียวสัญลักษณ์ลูกศร
ที่มาต่อไปเล็ก ๆ น้อย ๆ ตัวหนอนและทิ้งแล้ว
วงเล็บวงเล็บซ้ายหรือ วงเล็บวงเล็บที่ถูกต้องเหมาะสม
แต่ละเหล่านี้มีความหมายที่แตกต่างกัน
>> ในความเป็นจริงลองดู
ให้เป็นไปในวันนี้โรงเรียนเก่าและใช้งาน หน้าจอสัมผัสจากปีกลายที่
ที่รู้จักกันเป็นกระดานไวท์บอร์ด
และคณะกรรมการนี​​้สีขาว เป็นไปเพื่อให้เรา
ในการแสดงสัญลักษณ์บางอย่างที่ค่อนข้างง่าย หรือค่อนข้างบางสูตรที่ค่อนข้างง่าย
ที่เราสามารถทำได้ในท้ายที่สุดแล้ว ใช้ประโยชน์ในการสั่งซื้อ
ในการเข้าถึงของแต่ละบุคคล บิตภายในโปรแกรม C
ในคำอื่น ๆ ขอให้ทำเช่นนี้
การพูดคุยครั้งแรกลองหา ช่วงเวลาที่เกี่ยวกับเครื่องหมาย,
ซึ่งเป็นค่าที่เหมาะสมและผู้ประกอบการ
ในคำอื่น ๆ นี้ ผู้ประกอบการที่ช่วยให้
ผมที่จะมีตัวแปรซ้าย โดยทั่วไปและตัวแปรทางด้านขวามือ
หรือค่าของแต่ละบุคคลว่าถ้าเราและ พวกเขาร่วมกันให้ฉันผลสุดท้าย
ดังนั้นสิ่งที่ฉันหมายความว่าอย่างไร
ถ้าในโปรแกรมคุณมีตัวแปร ว่าร้านค้าหนึ่งในค่าเหล่านี้
หรือขอให้มันง่ายและเพียงแค่ เขียนออกศูนย์และคนเป็นรายบุคคล
นี่คือวิธีการทำงานของผู้ประกอบเครื่องหมาย
0 0 เครื่องหมายเป็นไปเท่ากับ 0
ตอนนี้ทำไมเป็นอย่างนั้น?
>> มันคล้ายกับ การแสดงออกบูลีน
ที่เราได้กล่าวถึงป่านนี้
หากคุณคิดว่าหลังจากทั้งหมด 0 เท็จ 0 เป็นเท็จเท็จและเท็จ
เป็นอย่างที่เราได้กล่าวถึง เหตุผลยังเท็จ
ดังนั้นเราจึงได้รับ 0 ที่นี่เช่นกัน
ถ้าคุณใช้เครื่องหมาย 0 1, ดีว่ามากเกินไป
เป็นไปได้ที่ 0 เพราะนี้ การแสดงออกทางด้านซ้ายมือจะเป็นจริงหรือ 1
มันจะต้องเป็นจริงและเป็นความจริง
แต่ที่นี่เรามีที่ผิดพลาด และเป็นความจริงหรือ 0 และ 1
ตอนนี้อีกครั้งถ้าเรามี 1 เครื่องหมาย 0 ที่มากเกินไปจะเป็น 0,
และถ้าเรามี 1 เครื่องหมาย 1, ในที่สุดเราก็จะมี 1 บิต
ดังนั้นในคำอื่น ๆ ที่เราไม่ได้ทำ สิ่งที่น่าสนใจกับผู้ประกอบการนี​​้
เพียง แต่ผู้ประกอบการเครื่องหมายนี้
มันเป็นค่าที่เหมาะสมและผู้ประกอบการ
แต่เหล่านี้เป็นส่วนผสม ผ่านทางที่เราสามารถทำได้
สิ่งที่น่าสนใจที่เราจะเห็นทันที
>> ตอนนี้ให้ดูที่เพียงแค่คนเดียว แถบแนวตั้งมากกว่าที่นี่ด้านขวา
ถ้าฉันมีบิต 0 และฉัน หรือมันกับค่าที่เหมาะสม
หรือผู้ประกอบการอีก 0 บิต ที่จะให้ฉัน 0
ถ้าผมใช้เวลา 0 บิตและหรือมันด้วย 1 บิตแล้วฉันจะได้รับ 1
และในความเป็นจริงเพียงเพื่อ ความคมชัดให้ฉันกลับไป
เพื่อให้แถบแนวตั้งของฉัน ไม่ได้เข้าใจผิดว่าเป็น 1
ผมขอเขียนทั้งหมดของ 1 ของฉันน้อยมาก
อย่างชัดเจนเพื่อที่เราจะได้เห็นต่อไปถ้าผม มี 1 หรือ 0, ที่จะเป็นที่ 1,
และถ้าผมมี 1 หรือ 1 ที่ เกินไปเป็นไปได้ที่ 1
ดังนั้นคุณจะเห็นว่ามีเหตุผลหรือ ผู้ประกอบการทำงานแตกต่างกันมาก
นี้จะช่วยให้ฉันหรือ 0 0 0 ให้ฉัน แต่ ทุกชุดอื่น ๆ ทำให้ผม 1
ตราบใดที่ฉันมีหนึ่ง 1 ใน สูตรผลที่เป็นไปได้ที่ 1
>> ในทางตรงกันข้ามกับและ ผู้ประกอบการ, เครื่องหมาย,
แต่ถ้าฉันมีสอง 1 ใน สมการไม่จริงผมได้รับ 1
ตอนนี้มีไม่กี่อื่น ๆ ผู้ประกอบการเป็นอย่างดี
หนึ่งในนั้นคือมีส่วนร่วมน้อยมาก
เพื่อให้ฉันไปข้างหน้าและลบ นี้เพื่อเพิ่มพื้นที่ว่างบาง
และขอใช้เวลาดูที่ สัญลักษณ์ลูกศรเพื่อรอสักครู่
นี้เป็นปกติ ตัวอักษรที่คุณสามารถพิมพ์
บนแป้นพิมพ์ของคุณกด Shift ถือครองและ จากนั้นหนึ่งของตัวเลขที่อยู่บนยอดของสหรัฐ
แป้นพิมพ์
>> ดังนั้นนี้เป็นพิเศษ หรือผู้ประกอบการ แต่เพียงผู้เดียวหรือ
ดังนั้นเราจึงเห็นผู้ประกอบการหรือ
นี้เป็นพิเศษหรือผู้ประกอบการ
สิ่งที่เป็นจริงแตกต่างกันอย่างไร
ดีขอเพียงแค่มองไปที่สูตร และใช้เป็นส่วนผสมในท้ายที่สุด
0 0 แฮคเกอร์
ฉันจะพูดอยู่เสมอ 0
นั่นคือความหมายของการ XOR
0 แฮคเกอร์ 1 เป็นไปได้ที่ 1
แฮคเกอร์ 1 0 เป็นไปได้ที่ 1, และแฮคเกอร์ 1 1 เป็นไปได้?
ผิด?
หรือขวา?
ฉันไม่รู้
0
ตอนนี้สิ่งที่เกิดขึ้นที่นี่?
ดีคิดเกี่ยวกับ ชื่อของผู้ประกอบการนี​​้
แต่เพียงผู้เดียวหรือเพื่อให้เป็น ชื่อชนิดของการแสดงให้เห็น,
คำตอบคือได้เพียงไปได้ 1 ถ้าปัจจัยการผลิตที่มี แต่เพียงผู้เดียว
ที่แตกต่างกันโดยเฉพาะ
ดังนั้นนี่คือปัจจัยการผลิตที่มี เดียวกันเพื่อการส่งออกเป็น 0
นี่คือปัจจัยการผลิตที่มี เดียวกันเพื่อการส่งออกเป็น 0
นี่คือผลที่มีแตกต่างกันพวกเขา เป็นพิเศษและเพื่อการส่งออกเป็น 1
ดังนั้นจึงเป็นคล้ายกับ และก็คล้ายกันมาก
หรือค่อนข้างจะคล้ายกับ หรือ แต่เพียงในวิธีพิเศษ
หนึ่งนี้จะไม่เป็นที่ 1, เพราะเรามีสอง 1,
และไม่เฉพาะเพียงหนึ่งของพวกเขา
ทั้งหมดขวา
สิ่งที่เกี่ยวกับคนอื่น ๆ ?
ตัวหนอนดีในขณะเดียวกันคือ จริงที่ดีและง่ายขอบคุณ
และนี่คือเอก ผู้ประกอบการซึ่งหมายความว่า
ก็นำไปใช้เพียงคนเดียวที่ป้อนข้อมูล ถูกดำเนินการอย่างใดอย่างหนึ่งเพื่อที่จะพูด
ไม่ไปทางซ้ายและขวา
ในคำอื่น ๆ ถ้าคุณใช้ตัวหนอนของ 0 คำตอบจะเป็นตรงข้าม
และถ้าคุณใช้ตัวหนอนของ 1, คำตอบจะมีตรงข้าม
ดังนั้นผู้ประกอบการเป็นตัวหนอน วิธีการกวนเล็กน้อยที่
หรือพลิกบิตจาก 0-1 หรือ 1-0
>> และนั่นทำให้เราที่สุด มีเพียงสองผู้ประกอบการขั้นสุดท้าย
การเปลี่ยนแปลงทางด้านซ้ายที่เรียกว่าและ ผู้ประกอบการที่เหมาะสมเพื่อการเปลี่ยนแปลงที่เรียกว่า
ลองมาดูที่วิธีการทำงานเหล่านั้น
ผู้ประกอบการเปลี่ยนแปลงซ้ายเขียน กับสองวงเล็บมุมเช่นนั้น
ดำเนินดังต่อไปนี้
ถ้าใส่ฉันหรือถูกดำเนินการของฉันไปทางซ้าย ผู้ประกอบการเปลี่ยนแปลงค่อนข้างเป็นเพียง 1
และจากนั้นผมก็บอกกับคอมพิวเตอร์ ซ้ายกะที่ 1 กล่าวว่าเจ็ดสถานที่
ผลที่ได้คือว่าผม ใช้เวลาที่ 1 และย้ายไป
เจ็ดสถานที่ไปยัง ซ้ายและตามค่าเริ่มต้น
เรากำลังจะไปคิดว่า พื้นที่ที่จะเหมาะสม
เป็นไปได้ที่เบาะด้วยศูนย์
ในคำอื่น ๆ ที่เหลือ 1 กะ 7 ที่เกิดขึ้น จะให้ฉันที่ 1 ตามมาด้วย 1, 2, 3,
4, 5, 6, 7 ศูนย์
ดังนั้นในทางที่จะช่วยให้คุณ ใช้จำนวนเล็ก ๆ เช่น 1,
อย่างเห็นได้ชัดและทำให้มันมาก มากมีขนาดใหญ่ในลักษณะนี้
แต่เราจริงจะไปดู วิธีการที่ชาญฉลาดมากขึ้นนั้น
แทนที่จะเป็นอย่างดี
>> ทั้งหมดขวา
นั่นมันสำหรับสัปดาห์ที่สาม
เราจะเห็นคุณในครั้งต่อไป
นี่คือ CS50
>> [เล่นเพลง]
>> ลำโพงที่ 1: เขาเป็นที่ว่าง บาร์กินไอศกรีมใส่ผลไม้ร้อนเหลวไหล
เขามีให้ทั่วใบหน้าของเขา
เขาสวมใส่เช่นช็อคโกแลตที่เครา
ลำโพง 2: สิ่งที่คุณกำลังทำอะไร?
ลำโพงที่ 3: อืม?
อะไร?
>> ลำโพงที่ 2: คุณไม่เพียงแค่จุ่มคู่?
คุณดับเบิลจุ่มชิป
ลำโพงที่ 3: ขอโทษนะ
ลำโพงที่ 2: คุณจุ่มชิปคุณ เอากัดและคุณจุ่มลงอีกครั้ง
ลำโพงที่ 3:
ลำโพง 2: เพื่อให้เป็นเหมือนกับการใส่ ปากของคุณทั้งหมดที่ถูกต้องในกรมทรัพย์สินทางปัญญา
ครั้งต่อไปที่คุณจะใช้ชิป เพียงจุ่มครั้งและจบมัน
>> ลำโพงที่ 3: คุณรู้ว่าสิ่งที่แดน?
คุณจุ่มวิธีการที่คุณต้องการที่จะจุ่ม
ฉันจะจุ่มวิธีการที่ฉันต้องการที่จะจุ่ม