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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ลำโพง 2: เมื่อคุณสุ่ม หมายเลขสิ่งที่หมายความว่า? 

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

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

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

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

และเรามีการตรวจสอบนี้ และการตรวจสอบนี้ควรจะทำงานใช่มั้ย? มัน A. มันควรจะเปลี่ยน ตัวอักษรสามตัวไปข้างหน้า แต่ถ้าคุณสังเกตเห็นเรา ได้รับสิ่งที่แตกต่างกัน ดังนั้นในกรณีนี้ขึ้นที่นี่ก็ถูกจับ มันและอื่น ๆ สายนี้ดำเนินการ ซึ่งการปรับเปลี่ยนของเรา B. แต่ในกรณีนี้ที่นี่ เรามีก็แค่ข้ามมัน และเดินไปที่ [? L Siff ?] ดังนั้นสิ่งที่เกิดขึ้นที่นั่น อะไรที่บอกคุณคือว่า เรารู้ว่ามันควรจะจับนี่ แต่มันก็ไม่ได้ ทุกคนสามารถมองเห็นสิ่งที่เรา ปัญหาอยู่ในบรรทัดที่? มันเป็นสิ่งที่มากนาที และคุณยังสามารถดูรหัสของคุณ นอกจากนี้ยัง line-- ลืมสิ่งที่มันเป็นเส้น ในตรงนี้ แต่มันอยู่ใน [ไม่ได้ยิน] ใช่? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MM-HM? 

นักเรียน: [ไม่ได้ยิน] ผู้สอน: ใช่ มีบางอย่างที่เป็น ที่จะหาที่อยู่ตรงกลาง 

นักศึกษา: ดังนั้นเราจึงสามารถใช้ที่ ตกลง 

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

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

นักเรียน: [ไม่ได้ยิน] 

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

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

นักเรียน: [ไม่ได้ยิน] ตรงกลาง หากพวกเขามีกรณีที่ มีจำนวนมากของตัวเลขขนาดเล็กของ และไม่ชอบจำนวนมากอย่างใดอย่างหนึ่ง? 

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

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

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

นักเรียน: พิมพ์ออก 

ผู้สอน: ดีเรา ไม่ต้องการที่จะพิมพ์ออก ดังนั้นนี่คือบูลที่นี่ดังนั้นเรา ต้องการที่จะกลับมาจริงหรือเท็จ เรากำลังพูดถึงก็คือจำนวนนี้ [? RRA? ?] ดังนั้นถ้ามันเป็น เราก็กลับมามันเป็นความจริง ถ้าผมสามารถสะกดความจริง 

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

ดังนั้นถ้าเรามีหลัก int (void) และบางสิ่งบางอย่างเช่นนี้ และคุณมีถ้าเป็นบน การป้อนข้อมูลบางอย่างและคุณ ถามว่าคุณสามารถทำ บางอย่างเช่นนี้หรือไม่? ใช่มั้ย? นักเรียน: ผมพยายาม ที่จะทำมัน [ไม่ได้ยิน] เพราะถ้า it's-- ผู้สอน: ขวา ดังนั้นคุณจึงอยากให้เรื่องนี้เป็นเท็จใช่มั้ย? นักเรียน: ใช่ ผู้สอน: ดังนั้นในกรณีนี้คุณ ต้องการที่จะดำเนินการถ้ามันไม่เป็นความจริง ดังนั้นสิ่งดีๆที่คุณทำมีนี้ ดังนั้นจำอัศเจรีย์ จุดขัดแย้งสิ่ง? มันบอกว่า [ไม่ได้ยิน] หมายความว่าไม่ ดังนั้นหากเรามองไปที่เพียงแค่ ส่วนที่นี่คุณต้องการ บอกว่าประเมิน เป็นเท็จที่คุณต้องการให้ ไม่เท็จเป็นความจริงที่ หมายความว่าเรื่องนี้จะดำเนินการ ที่ทำให้รู้สึก? นักเรียน: ใช่ ผู้สอน: เจ๋ง ตกลง ดังนั้นเราก็จะกลับมา ความจริงในกรณีนี้ ดังนั้นตอนนี้เรามีสองอื่น ๆ กรณีในกรณีนี้ สิ่งที่สองกรณีอื่น ๆ ของเรามีอะไรบ้าง ขอเพียงทำมันด้วยวิธีนี้ ดังนั้นขอเริ่มต้นด้วยอื่น ถ้าค่าที่อยู่ตรงกลาง มีค่าน้อยกว่าค่าที่เราต้องการ ดังนั้นค่าของเราอยู่ตรงกลางน้อย กว่ามูลค่าที่เรากำลังมองหา 

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

นักเรียน: ต่ำ 

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

นักเรียน: [? ไม่มีค่า?] มากเท่ากับมัน 

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

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

นักเรียน: มันไม่สำคัญ ไม่ว่าจะเป็น n ของคุณได้หรือคี่? 

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

ดังนั้นในกรณีที่ดีที่สุดก็เพียง หนึ่งที่เราเรียกว่าเวลาคงที่ ทุกคนสามารถบอกฉันว่าทำไมที่อาจจะมี? สิ่งที่ประเภทของสถ​​านการณ์ที่จะมอบให้? MM-HM 

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

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

ถ้าคุณมีถุงคลั่งไคล้นี้ ของตัวเลขและคุณกำลังบอกว่า ตกลงผมจะไปตรวจสอบกลาง จำนวนและตัวเลขฉันกำลังมองหา น้อยกว่าที่ฉันแค่ไป ให้พลโยนออกครึ่งหนึ่ง คุณจะไม่ทราบว่าของคุณ ตัวเลขในอีกครึ่งหนึ่งที่ รายการของคุณจะต้องมีการแยก เช่นกันนี้อาจเป็น ไปข้างหน้าเล็กน้อย แต่คุณต้องมีการเข้าถึงแบบสุ่ม คุณจะต้องสามารถที่จะเพียงแค่ ไปที่องค์ประกอบกลางที่ หากคุณมีการสำรวจ ผ่านสิ่งที่ หรือจะนำคุณขั้นตอนพิเศษ ที่จะได้รับไปยังองค์ประกอบกลางนั้น มันไม่ log n อีกต่อไปเพราะ คุณกำลังเพิ่มการทำงานมากขึ้นเป็นมัน และนี่จะทำให้เล็ก ๆ น้อย ๆ รู้สึกมากขึ้นในสองสัปดาห์ที่ผ่านมา แต่ฉันเพียงแค่ชนิดของต้องการที่จะคำนำ ให้พวกคุณคิดในสิ่งที่เป็น ที่จะมา แต่ผู้ที่มีสอง สมมติฐานที่สำคัญ ที่คุณต้องการสำหรับรายการไบนารี ให้แน่ใจว่ามันถูกจัดเรียง นั่นเป็นหนึ่งในที่ยิ่งใหญ่สำหรับ พวกคุณได้ในขณะนี้ และในวันที่เราจะได้เข้าไป ส่วนที่เหลือของทุกประเภทของเรา ดังนั้นสี่ฟอง sorts--, แทรกการเลือกและการรวม พวกเขากำลังทั้งหมดชนิดของเย็น ถ้าพวกคุณตัดสินใจที่จะใช้ CS 124, คุณจะได้เรียนรู้เกี่ยวกับทุกประเภทของทุกประเภท และถ้าคุณเป็นแฟน XKCD มี เป็นเรื่องเกี่ยวกับการ์ตูนที่เจ๋งจริงๆ เหมือนทุกประเภทไม่ได้ผลจริงๆซึ่งผม ขอแนะนำให้คุณไปดูที่ หนึ่งในนั้นคือการจัดเรียงเช่นตื่นตระหนกซึ่ง เป็นเหมือนโอ้ไม่กลับอาร์เรย์แบบสุ่ม ระบบปิด ออกจาก ดังนั้นอารมณ์ขัน geeky ดีอยู่เสมอ 

เพื่อให้ทุกคนไม่จำชนิด เช่นเดียวกับความคิดทั่วไป ของวิธีการทำงานการจัดเรียงฟอง คุณจำได้ไหม? 

นักเรียน: ใช่ 

ผู้สอน: ไปมัน 

นักเรียน: คุณกำลังจะผ่านและ ถ้ามันใหญ่แล้วคุณสลับสอง 

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

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

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

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

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

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

นักเรียน: สิ่งที่จะทำงาน เป็นไปเพื่อการแลกเปลี่ยนองค์ประกอบ? 

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

ดังนั้นวิธีที่คุณคิดว่าเราอาจจะ ย้ำผ่านอาร์เรย์ของเราหรือไม่ เรามีเคล็ดลับและฉันเท่ากับ 0 เราต้องการฉันจะน้อย กว่า n ลบ 1 ลบ k และฉันจะอธิบายว่าในครั้งที่สอง ดังนั้นนี่คือการเพิ่มประสิทธิภาพที่นี่ที่ไหน จำได้ว่าผมบอกว่าทุกครั้งหลังจากผ่าน เราผ่านอาร์เรย์ รู้ว่าสิ่ง on-- 

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

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

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

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

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

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

นักเรียน: 10 

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

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

นักเรียน: อะไรหยุดพักทำอย่างไร 

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

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

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

นักเรียน: [ไม่ได้ยิน] int หลักมักจะ คุณจะต้องมีที่สำหรับการนี​​้ 

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

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

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

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

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

ตกลง ดังนั้นตอนนี้สิ่งที่เป็นจริงในกรณีที่ดีที่สุด? นักเรียน: ศูนย์? หรือ 1? 

ผู้สอน: 1 ดังนั้นจะ เป็นหนึ่งในการเปรียบเทียบ ขวา 

นักเรียน: ยังไม่มีลบ 1? 

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

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

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

นักเรียน: โดยทั่วไปผ่านไป สั่งซื้อและสร้างรายการใหม่ และเช่นเดียวกับที่คุณกำลังวางองค์ประกอบ ในการใส่ไว้ในสถานที่ที่เหมาะสม ในรายการใหม่ 

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

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

ส่วนที่เรียงลำดับที่คุณเพียงแค่ปล่อยให้อยู่คนเดียว MM-HM? 

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

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

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

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

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

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

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

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

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

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

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

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

นักเรียน: สำหรับขนาดที่คุณไม่เคย จริงๆกำหนดหรือเปลี่ยนมัน วิธีที่จะรู้หรือไม่? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ดังนั้นมันจะจบลงด้วยการที่ ประมาณ n ยกกำลัง ถ้ามันถูกต้องแล้วคุณ พูด, OK, 2, คุณดี 3 คุณเมื่อเทียบกับ 2 คุณดี 4 คุณเพียงแค่เปรียบเทียบกับหาง คุณดี 6 เปรียบเทียบกับหางคุณดี ดังนั้นสำหรับทุกจุดถ้ามันมีอยู่แล้ว เรียงลำดับที่คุณกำลังทำเปรียบเทียบหนึ่ง จึงเป็นเพียง n และเพราะเรามี runtime กรณีที่ดีที่สุด ของ n และรันไทม์กรณีที่เลวร้ายที่สุดของ n ยกกำลังเราไม่มี runtime คาดว่า 

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

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

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

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

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

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

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

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

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

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

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

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

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