[เล่นเพลง] 

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

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

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

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

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

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

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

นอกจากนี้มี psets เนื่องจากวันศุกร์ตอนเที่ยง ผมคิดว่ามีเจ็ดนาที ระยะเวลาผ่อนผันปลายที่เราให้คุณ ฮาร์วาร์ต่อครั้งที่พวกเขาได้รับอนุญาตให้ เจ็ดนาทีจะสายไปทุกอย่าง ดังนั้นที่นี่ที่เยลเราจะ เป็นไปตามที่ดี แต่สวยมากที่ 00:07, ถ้า pset ของคุณไม่ได้ใน มันจะถูกทำเครื่องหมายเป็นช่วงปลายเดือน ดังนั้นในขณะที่มันมีการทำเครื่องหมาย เป็นสาย TA-- ฉัน ยังจะได้รับการจัดลำดับ psets ของคุณ ดังนั้นคุณจะยังคงเห็นเกรดปรากฏ แต่รู้ว่าที่ ในตอนท้ายของภาคการศึกษาที่ psets ปลายทั้งหมดจะเป็นเพียง กลายเป็นศูนย์โดยอัตโนมัติโดยคอมพิวเตอร์ 

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

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

ผู้ชม: คุณบอกว่าเรา สามารถวางหนึ่ง psets หรือไม่ 

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

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

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

ผู้ชม: เรามีไอศครีม 

ANDI PENG: ดังนั้นที่เหมาะสมที่เรามี ไอศครีมที่เวลาทำการคืนที่ผ่านมา ในขณะที่ฉันไม่สามารถสัญญาว่า เราจะมีไอศครีมในเวลาทำการ ทุกสัปดาห์สิ่งที่ฉันสามารถสัญญาคุณ คือว่าจะมีอย่างมีนัยสำคัญ นักเรียนที่ดีกว่าอัตราส่วน TA เช่นเดียวกับที่ legit ก็เหมือน 3-1 ในขณะที่ความคมชัดด้วย วันพฤหัสบดีที่คุณได้มีประมาณ 150 เด็กเครียดจริงๆและไอศครีมไม่ และมันก็เป็นเพียงแค่ไม่ได้ผลิตสำหรับทุกคน ดังนั้นคุณธรรมของเรื่องราวเป็นมาในช่วงต้น ชั่วโมงสำนักงานและสิ่งที่ดี จะเกิดขึ้น. 

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

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

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

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

ผู้ชม: ดังนั้นคำถามคือ ไปได้ในระหว่างการบรรยาย? 

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

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

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

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

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

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

ดังนั้นอย่างไรก็ตามในขณะที่รหัสนี้เป็นอย่างมาก ที่สวยงามก็ไม่ได้ทำงานอย่างถูกต้อง ดังนั้นขอเรียก check50 เกี่ยวกับเรื่องนี้ ตรวจสอบ 50 20-- OOP 2? เป็น pset2 ที่? ใช่ โอ้ pset1 ตกลง. ดังนั้นเราจึงเรียก check50 

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

ตกลง. ดังนั้นเรามาดูซึ่งเป็นหนึ่งใน การตรวจสอบผมก็ล้มเหลวใน check50 เป็นค่าที่ป้อนข้อมูลของ 0.41 ดังนั้นคำตอบที่ถูกต้องที่ คุณควรจะได้รับเป็น 4 แต่สิ่งที่ผมพิมพ์ออก เป็น 3 n ซึ่งไม่ถูกต้อง เพื่อให้เพียงทำงานนี้ด้วยตนเองเพียง ตรวจสอบให้แน่ใจ check50 ที่ทำงาน ขอทำ ./greedy โอ๊ะฉันจะต้องทำโลภ เราจะไปที่นั่น. ตอนนี้ ./greedy 

วิธีที่เป็นหนี้มาก? ขอทำ 0.41 และครับเราจะเห็นที่นี่ ว่ามันแสดงผล 3 เมื่อคำตอบที่ถูกต้อง ในความเป็นจริงควรจะเป็น 4 ดังนั้นขอใส่ GDB และดูวิธีการที่เรา สามารถไปเกี่ยวกับการแก้ไขปัญหานี้ 

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

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

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

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

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

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

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

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

ดังนั้น n ซึ่งคือลอยของเราที่ เราได้ initialized-- หรือ declared-- ขึ้นที่ด้านบนเราในขณะนี้ เท่ากับว่า GetFloat () ดังนั้นขอให้ก้าวข้ามว่า และเราจะเห็นที่ ด้านล่างนี่โปรแกรม จะแจ้งให้ผมใส่ค่า ดังนั้นขอค่าการป้อนข้อมูลที่เราต้องการ ในการทดสอบที่นี่ซึ่งเป็น 0.41 ที่ดี 

ดังนั้นตอนนี้ n-- ทำพวกคุณเห็น ที่นี่ที่ bottom-- มัน stored-- เพราะเรา โค้งมนไม่ได้เลยก็ เก็บไว้ในนี้เหมือนยักษ์ ลอยที่เป็น 0.4099999996, ซึ่งอยู่ใกล้พอที่จะของเรา วัตถุประสงค์ในขณะนี้ 0.41 และจากนั้นเราจะได้เห็นต่อไปในขณะที่เรา ยังคงก้าวมากกว่าโปรแกรม หลังจากที่นี่ได้กลายเป็น n โค้งมนและเซ็นต์ได้กลายเป็น 41 ที่ดี ดังนั้นเราจึงรู้ว่าการทำงานการปัดเศษของเรา เรารู้ว่าเรามี จำนวนที่ถูกต้องของเซนต์ เพื่อให้เรารู้ว่าที่ ไม่ได้จริงๆปัญหา 

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

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

เรายังคงต้องผ่านโปรแกรม ขั้นตอนที่มากกว่า เย็น เราไปกว่าสลึง ที่ดี เราจะเห็นว่าก็เอา ปิด $ 0.10 สำหรับค่าเล็กน้อย และตอนนี้เรามีสองเหรียญ ถูกต้อง. 

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

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

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

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

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

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

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

และนี่คือคำอธิบายภาพ ของวิธีการที่จะทำงาน ดังนั้นตัวอย่างเช่นถ้าเราจะเริ่มต้น กับอาร์เรย์ของห้าองค์ประกอบที่ดัชนี 0-4, 3, 5, 2, 6 และ 4 ค่า วางไว้ใน array-- ดังนั้นในขณะนี้ เราเพียงแค่จะถือว่า ว่าพวกเขากำลังไม่ได้เรียงลำดับทั้งหมด เพราะเราไม่ได้ทดสอบอย่างอื่น 

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

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

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

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

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

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

ANDI PENG: ขวา ดังนั้นคุณจะต้องการที่จะย้ำ ผ่านทุกพื้นที่ใช่มั้ย? ดังนั้นที่ดี ถ้าพวกคุณต้องการที่จะให้ฉัน ต่อไป line-- ใช่ในด้านหลัง 

ผู้ชม: ตรวจสอบพวกเขา ทั้งหมดที่เล็กที่สุด 

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

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

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

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

ผู้ชม: สำหรับวง 

ANDI เป็ง: เป็นห่วง? ที่แน่นอน ดังนั้นนี้อาจเป็น จะเป็นห่วง ตรวจสอบที่นี่จะบ่งบอกคืออะไร? โดยปกติแล้วถ้าคุณต้องการที่จะตรวจสอบ ถ้าสิ่งที่เป็นสิ่งที่ else-- 

ผู้ชม: ถ้า 

ANDI PENG: การถ้าใช่มั้ย? และแล้วการแลกที่นี่เราจะ ไปกว่าในภายหลังเพราะเดวิด ที่เดินผ่านในการบรรยายได้เป็นอย่างดี แล้วย้ำสอง implies-- 

ผู้ชม: อีกสำหรับวง 

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

เอ่อโอ้. ทำไมที่ not-- มีเป็น ตกลง. ขออภัยให้ฉันพยายามที่จะขยายอีกเล็กน้อย เราจะไปที่นั่น. ทั้งหมดที่ฉันทำที่นี่คือเราได้สร้าง โปรแกรมที่เรียกว่า "การเลือก / sort.c." เราได้สร้างอาเรย์ของเก้า ค่า, 4, 8, 2, 1, 6, 9, 7, 5, 3 ขณะนี้เท่าที่คุณสามารถ เห็นพวกเขาจะเรียงลำดับ n จะเป็นหมายเลขที่ บอกคุณจำนวนของค่า ที่คุณมีในอาร์เรย์ของคุณ ในกรณีนี้เรามีเก้าค่า และฉันได้เพียงแค่มีการห่วงที่นี่ ที่พิมพ์ออกมาไม่ได้เรียงลำดับอาร์เรย์ 

และในตอนท้ายที่ฉันได้ยังมีสำหรับ วงที่เพิ่งพิมพ์มันออกมาอีกครั้ง ดังนั้นในทางทฤษฎีถ้าโปรแกรมนี้ ทำงานอย่างถูกต้องในตอนท้าย คุณจะเห็นพิมพ์สำหรับวง ที่ 1, 2, 3, 4, 5, 6, 7, 8, 9 มีทั้งหมดอย่างถูกต้องในการสั่งซื้อ 

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

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

ANDI เป็ง: ใช่รู้สึก ฟรี to-- ขออภัยคุณ ไม่ต้องยืน up-- รู้สึก อิสระที่จะยกระดับเสียงของคุณสักหน่อย 

ผู้ชม: สำหรับฉัน int เท่ากับ 0-- 

ANDI เป็ง: ใช่ดี 

ผู้ชม: ฉันเป็นน้อยกว่าความยาวอาร์เรย์ 

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

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

ผู้ชม: มันจะไม่ลบ 1 n? ANDI เป็ง: มันเป็นไป n ลบ 1 ตรง ที่ทำให้รู้สึกว่าทำไม มันเป็น n ลบ 1 ทุกคน? มันเป็นเพราะอาร์เรย์จะเป็นศูนย์การจัดทำดัชนี พวกเขาเริ่มต้นที่ 0 และวิ่งขึ้นไป n ลบ 1 ใช่มันเป็นบิตหากิน ตกลง. และ then-- ผู้ชม: Isnt'1 ว่า แล้วดูแลว่า โดยเพียงแค่ไม่ได้บอกว่า "น้อยกว่าหรือ เท่ากับ "และเพียงแค่พูดว่า" น้อยกว่า " 

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

ขวา อาจจะเป็นชื่อที่ดีกว่าสำหรับการที่ จะ be-- "ชั่วคราว" ทั้งหมด works-- อาจจะเป็นชื่อเหมาะเจาะมากขึ้นจะเป็น ถ้าเราต้องการ value-- ที่เล็กที่สุด 

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

ผู้ชม: เพ​​ราะดี เราเริ่มต้นด้วย 0 ดังนั้นเพราะเรามีอะไรที่จะเปรียบเทียบ มันไปต่ำสุดที่จะจบลงด้วยการ 0 

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

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

ANDI เป็ง: ใช่เจเสียงดีกับฉัน เท่ากับ? 

ผู้ชม: ดังนั้นฉันจะบวก 1 เพราะ คุณกำลังเริ่มต้นที่ค่าถัดไป และจากนั้นไปที่ end-- ดังนั้นอีกครั้งญคือ น้อยกว่า n ลบ 1 และจากนั้นเจ ++ ANDI PENG: Great 

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

ผู้ชม: ถ้างบ 

ANDI PENG: ถ้างบ ดังนั้น if-- และสิ่งที่เป็นไปได้ เงื่อนไขที่ว่าเราต้องการภายใน ของคำสั่งถ้าของเราหรือไม่ 

ผู้ชม: ถ้าค่าของเจ มีค่าน้อยกว่าค่าของ i-- 

ANDI PENG: แน่นอน ดังนั้นเพื่อให้ if-- อาร์เรย์นี้จะเรียกว่า "อาเรย์." ที่ดี ดังนั้นหาก array-- สิ่งที่เป็นที่? บอกได้เลยว่าอีกครั้ง 

ผู้ชม: ถ้าอาร์เรย์ญน้อยกว่า อาร์เรย์ฉันแล้วเราจะเปลี่ยนนาที ดังนั้นนาทีจะเป็นเจ 

ANDI PENG: ที่ทำให้รู้สึก? ตกลง. และตอนนี้ที่นี่เราจริง ต้องการที่จะใช้แลกเปลี่ยนใช่มั้ย? ดังนั้นจำในการบรรยายที่ดาวิดเมื่อ เขาพยายามที่จะสลับ the-- สิ่งที่เป็น น้ำส้ม it-- และ milk-- 

ผู้ชม: นั่นเป็นขั้นต้น 

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

ผู้ชม: ตัวแปรชั่วคราว 

ANDI PENG: ตัวแปรชั่วคราว เพื่อขอทำอุณหภูมิ int ดูนี้จะดีกว่า เวลา to-- โอ้โฮสิ่งที่เป็นที่? ตกลง. ดังนั้นนี้จะได้รับที่ดีกว่า เวลาที่จะตั้งชื่อตัวแปร "ชั่วคราว". เพื่อขอทำอุณหภูมิ int สิ่งที่เราจะไป ตั้งอุณหภูมิเท่ากับที่นี่? ผู้ชม: มิน? ANDI เป็ง: มันเป็นบิตหากิน มันจริงไม่สำคัญว่าในท้ายที่สุด มันไม่สำคัญว่าสิ่งที่ เพื่อที่คุณเลือกที่จะสลับใน ตราบใดที่คุณกำลังทำแน่ใจว่าคุณ ติดตามความเคลื่อนไหวของสิ่งที่คุณกำลังการแลกเปลี่ยน 

ผู้ชม: มันอาจจะเป็นอาร์เรย์ฉัน 

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

ANDI PENG: OK ดังนั้นเรามาทำงานนี้และดู ถ้ามันจะไปทำงาน ที่สถานที่ที่เกิดขึ้น? โอ้ว่าปัญหา ดูในบรรทัด 40 เรา พยายามที่จะใช้อาร์เรย์ญ? แต่ที่ไม่เพียงเจอยู่มีอะไรบ้าง? 

ผู้ชม: ในการห่วง ANDI PENG: ขวา ดังนั้นสิ่งที่เราจะต้องทำอย่างไร 

ผู้ชม: กำหนดมันนอก the-- ผู้ชม: ใช่ผมคิดว่าคุณมี ที่จะใช้คำสั่งอื่นถ้าใช่มั้ย? ดังนั้นเช่นถ้า minimum-- สิ่งที่ถูกต้องให้ฉันคิดว่า 

ANDI PENG: ผู้ชายลอง ที่จะใช้ให้ดูที่ เห็นสิ่งที่บางสิ่งบางอย่างที่เราสามารถทำได้ที่นี่? 

ผู้ชม: ตกลง ดังนั้นหากขั้นต่ำไม่เท่ากับ j-- ดังนั้นหากขั้นต่ำยังคง i-- แล้วเราจะไม่ต้องสลับ 

ANDI PENG: ไม่เท่ากับที่ฉัน? อะไรที่คุณอยากจะบอกว่าที่นี่? 

ผู้ชม: ใช่หรือถ้า ขั้นต่ำไม่เท่ากับฉันใช่ ANDI PENG: OK ดีที่แก้ชนิดของปัญหาของเรา แต่ที่ยังไม่ได้แก้ ปัญหาของการเกิดอะไรขึ้นถ้า j-- ตั้งแต่เจ ไม่ได้อยู่ด้านนอกของมันสิ่งที่ คุณจะทำเราต้องการที่จะทำอะไรกับมันได้หรือไม่ ประกาศมันนอก? ลองทำงานนี้ เอ่อโอ้. การจัดเรียงของเราไม่ได้ทำงาน 

ในขณะที่คุณสามารถดูครั้งแรกของเรา อาร์เรย์มีค่าเหล่านั้น และหลังจากนั้นมันควรจะมี รับใน 1, 2, 3, 4, 5, 6, 7, 8, 9 มันไม่ได้ทำงาน อ่า พวกเราทำอะไร? ผู้ชม: การแก้ปัญหา ANDI PENG: สิทธิทั้งหมดที่เราสามารถพยายามที่ เราสามารถแก้ปัญหา ซูมออกเล็กน้อย ลองตั้งจุดพักของเรา Let 's go ตกลง like-- 

ดังนั้นเพราะเรารู้อยู่แล้วว่า เส้นเหล่านี้ 15 ผ่าน 22 จะ working-- เพราะทั้งหมดที่ฉันทำอยู่ เพียงแค่ทำซ้ำผ่านและ printing-- ฉันสามารถไปข้างหน้าและข้าม ขอเริ่มต้นที่เส้น 25 Oop ให้ฉันได้รับการกำจัดที่ 

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

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

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

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

ใช่เพื่อให้เราสามารถจริง ออกจากบั๊กที่นี่ ดังนั้นลองมาดูที่ pseudocode ของเรา For-- เรากำลังจะไป เริ่มต้นที่ฉันมีค่าเท่ากับ 0 เรากำลังจะไปถึง n ลบ 1 ขอตรวจสอบไม่เรามีสิทธิที่? อ้างว่าเป็นสิทธิ 

ดังนั้นแล้วภายในที่นี่เรากำลัง จะสร้างค่าต่ำสุด และการตั้งค่าที่เท่ากับผม เราไม่ทำเช่นนั้น? ครับไม่ว่า ตอนนี้ในด้านของเราสำหรับวงเรา จะทำเจเท่ากับ i เพื่อ n ลบ 1 เราไม่ทำเช่นนั้น? อันที่จริงเราไม่ว่า 

ดังนั้น แต่สิ่งที่เราเปรียบเทียบที่นี่? 

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

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

ถ้าอย่างนั้นเราก็บอกว่าเราได้ ได้เช่น 2, 5, 1, 8 ตอนนี้ฉันจะมีค่าเท่ากับ 0 และเจมีค่าเท่ากับ 0 และนั่นคือค่าต่ำสุดของเรา ถ้าอาร์เรย์เจบวก i-- ดังนั้นถ้าหนึ่ง นั่นคือหลังจากที่เรากำลังมองหาที่ มีค่ามากกว่าหนึ่งก่อนที่จะมัน มันจะกลายเป็นขั้นต่ำ 

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

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

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

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

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

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

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

ทั้งหมดขวา ดังนั้นฉันก็จะทำงานได้อย่างรวดเร็ว ผ่านส่วนที่เหลือของแปลกที่ อัลกอริทึมสำหรับ ฟอง sort-- จำ นี่เป็นครั้งแรกหนึ่ง ดาวิดก็ข้ามในการบรรยาย โดยพื้นฐานแล้วคุณก้าว ผ่านรายการทั้งหมด และคุณ swap-- คุณเพียงแค่ เปรียบเทียบสองในเวลา และหากเป็นมากขึ้น กว่าที่คุณเพียงแค่สลับพวกเขา ดังนั้นหากเหล่านี้มีมากขึ้นคุณจะสลับ ฉันมีอย่างเป็นทางการที่นี่ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ตกลงไม่มีใครต้องการ ให้ฉันรันไทม์ที่เลวร้ายที่สุด? ใช่ 

ผู้ชม: n กำลังสอง 

ANDI เป็ง: มันยกกำลัง n และทำไมมันยืด n? 

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

ผู้ชม: n ลบ 1 เพราะ คนแรกที่ยกกำลังสองแล้ว 

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

ดังนั้นในกรณีที่ดีที่สุด มันจริงเพียงจะเป็น n หากคุณมี 1, 2, 3, 4, 5, 6, 7, 8, คุณ จะวิ่งผ่าน ว่ารายการทั้งหมดในครั้งเดียว เพื่อตรวจสอบเพื่อดูว่าดีทุกอย่าง คือทุกคนที่ชัดเจนเกี่ยวกับการทำงาน ครั้งของการเลือกเช่นกัน? ฉันรู้ว่าฉันจะผ่าน เหล่านี้ได้อย่างรวดเร็วจริงๆ เพียง แต่รู้ว่าถ้าคุณรู้ว่า แนวความคิดโดยทั่วไปแล้วคุณควรจะดี ตกลง. ดังนั้นฉันจะให้พวกคุณอาจจะชอบ นาทีที่จะพูดคุยกับเพื่อนบ้านของคุณ ในสิ่งที่เป็นเพียงบางส่วน ความแตกต่างหลัก ระหว่างเหล่านี้ประเภทของทุกประเภท เราจะไปกว่าว่าเร็ว ๆ นี้ ผู้ชม: โอ้, OK ANDI เป็ง: ใช่ ตกลง. เย็นขอ reconvene เป็นชั้น ตกลง. ดังนั้นนี้คือชนิดของ คำถามปลายเปิดในความรู้สึก ที่มีจำนวนมากของคำตอบให้กับพวกเขา และเราจะไปกว่าบางส่วนของพวกเขาในเวลาสั้น ๆ ฉันแค่อยากที่จะได้รับพวกคุณ คิดเกี่ยวกับสิ่งที่แตกต่าง ทั้งสามประเภทของแปลก และข้าพเจ้าได้ยินยังดี คำถามของสิ่งที่จะผสานการเรียงลำดับทำอย่างไร คำถามที่ดีเนื่องจากว่าเป็น สิ่งที่เรากำลังครอบคลุมต่อไป 

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

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

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

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

และจากนั้นเราจะดูที่มันสายตา เพราะผมเป็นผู้เรียนมองเห็น มันทำงานได้ดีสำหรับฉัน ดังนั้นเราจะดูตัวอย่างภาพที่นี่ 

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

ดังนั้นเราจึงรู้ว่า 3, 5, 2, 4, 6, 1, ด้วยตัวเองจะถูกจัดเรียง และตอนนี้เราสามารถนำพวกเขากลับมารวมกัน ดังนั้นเราจึงรู้ว่า 3, 5 เราใส่ร่วมกัน เรารู้ว่าที่เรียง 2 ยังคงมี เราสามารถใส่ 4 และ 6 ร่วมกัน เรารู้ว่าที่เรียงลำดับ ดังนั้นเราจึงนำที่ร่วมกัน และจะมี 1 

และจากนั้นคุณเพียงแค่มอง ทั้งสองแบ่งเท่า ๆ กันที่นี่ คุณมี 3, 5, 2, 2, 3, 5 คุณก็สามารถเปรียบเทียบ จุดเริ่มต้นของทุกสิ่ง เพราะคุณรู้ว่านี้จะถูกจัดเรียง และคุณรู้ว่าที่เรียง ดังนั้นแล้วคุณไม่ได้มีการ เปรียบเทียบ 5 คุณเพียงแค่เปรียบเทียบ 3 และ 2 น้อยกว่า 3 ดังนั้น คุณรู้ว่า 2 จะต้องไปในที่สุด 

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

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

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

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

ผู้ชม: ดังนั้นคุณเพียงแค่เสมอ เปรียบเทียบ [ไม่ได้ยิน] 

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

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

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

ผู้ชม: เป็นกรณีที่เลวร้าย n ล็อก n? ANDI PENG: แน่นอน และทำไมมัน log n n 

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

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

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

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

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

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

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

ดังนั้นวิธีการที่เราจะไปเกี่ยวกับ การดำเนินการค้นหาแบบทวิภาค คือถ้าเรามีอาร์เรย์ ดัชนี 0-6 เจ็ดองค์ประกอบ เราสามารถมองอยู่ตรงกลาง right-- ขออภัยหากคำถามของเรา first-- ถ้าเราต้องการที่จะถามคำถามของไม่ อาร์เรย์มีองค์ประกอบ 7, เห็นได้ชัดว่าเป็นมนุษย์และมี เช่นอาร์เรย์ขนาดเล็กมันเป็นเรื่องง่ายสำหรับเรา จะบอกว่าใช่ แต่วิธีการที่จะใช้ไบนารี การค้นหาจะมองที่อยู่ตรงกลาง 

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

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

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

ดังนั้นผมคิดขอให้คุณเขียน ฟังก์ชั่นการค้นหาที่เรียกว่า () ที่กลับมา ค่าค่าบูลีน, ว่าเป็นความจริงหรือ false-- ชอบ ความจริงถ้าคุณคิดว่า ค่าที่เป็นเท็จถ้าคุณไม่ได้ แล้วคุณได้ ส่งผ่านไปในค่าที่คุณ เขากำลังมองหาเข้าไปในค่านิยมที่ เป็น array-- โอ้ฉันใส่แน่นอน ที่อยู่ในสถานที่ที่ไม่ถูกต้อง ตกลง. Anyways ที่ควรจะมี รับไปทางขวาของค่า และแล้ว int n เป็นจำนวน ขององค์ประกอบในอาร์เรย์ที่ วิธีที่คุณจะไปเกี่ยวกับการพยายาม เพื่อ pseudocode ปัญหาในการที่? ฉันจะให้พวกที่ชอบ สามนาทีที่จะทำ ไม่ฉันคิดว่ามีเท่านั้นหากต้องการดู ใช่มีหนึ่งขวาขึ้นที่นี่ ผู้ชม: ฉันสามารถ? ANDI PENG: ใช่ฉันมีคุณ คือการทำงานที่? ตกลงเย็น 

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

ผู้ชม: [ไม่ได้ยิน] ผู้ชม: คุณต้องการ ย้ำ through-- ผู้ชม: เพ​​ียงแค่อีกวง? ผู้ชม: --for 

ANDI PENG: ดังนั้นนี้เป็นบิตหากิน คิด about-- คุณต้องการ เพื่อให้ทำงานวงนี้ ซ้ำแล้วซ้ำอีกจนเมื่อ? 

ผู้ชม: จนกระทั่ง [ไม่ได้ยิน] ค่าเท่ากับค่าที่ ANDI PENG: แน่นอน เพื่อให้คุณสามารถจริงเพียง write-- เรายังสามารถลดความซับซ้อนมากขึ้น เราก็สามารถทำวงในขณะที่ใช่มั้ย? ดังนั้นคุณก็สามารถมี loop-- เรารู้ว่ามันเป็นในขณะที่ แต่สำหรับตอนนี้ผมกำลังจะ จะพูดว่า "ห่วง" - ผ่านอะไร? ห่วง until-- สิ่งที่เป็น สภาพสิ้นสุดของเราหรือไม่ ฉันคิดว่าฉันได้ยินมัน ผมได้ยินคนพูดว่า 

ผู้ชม: ค่าเท่ากับกลาง ANDI PENG: Say มันอีกครั้ง ผู้ชม: หรือจน ค่าที่คุณกำลังค้นหา สำหรับเท่ากับค่ากลาง 

ANDI PENG: อะไรถ้ามันไม่ได้อยู่ในที่นั่น? เกิดอะไรขึ้นถ้าค่าที่คุณกำลังค้นหา หาไม่ได้จริงในอาร์เรย์นี้หรือไม่? ผู้ชม: คุณกลับ 1 

ANDI PENG: แต่ทำในสิ่งที่เราต้องการ ห่วงจนถ้าเรามีเงื่อนไขหรือไม่? ใช่ 

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

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

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

ผู้ชม: ใช่ 

ANDI PENG: OK ดังนั้นถ้าเป็นเงื่อนไขสำหรับวงของเรา ทำในสิ่งที่เราต้องการภายในของวงนี้หรือไม่? สิ่งที่เรากำลังจะได้รับการต้องการที่จะทำอย่างไร ดังนั้นตอนนี้เราได้มี สูงสุดและต่ำสุดขวา อาจจะสร้างขึ้นที่นี่ที่ไหนสักแห่ง เรากำลังจะไปอาจต้องการ ที่จะหาตรงกลางขวาหรือไม่? พวกเราจะไปได้ สามารถที่จะหาตรงกลาง? อะไร mathematical-- ผู้ชม: แม็กซ์บวกนาทีโดยแบ่งออกเป็น 2 ANDI PENG: แน่นอน ที่ทำให้รู้สึก? และพวกคุณเห็นว่าทำไมเรา ไม่ได้เพียงแค่ use-- เหตุผลที่เราทำอย่างนี้ แทนการทำเพียงแค่แบ่ง n 2? ก็เพราะ n เป็นค่า ที่จะยังคงเหมือนเดิม ใช่มั้ย? แต่ที่เราปรับขั้นต่ำของเราและ ค่าสูงสุดที่พวกเขากำลังจะมีการเปลี่ยนแปลง และเป็นผลกลางของเรา จะเปลี่ยนมากเกินไป เพื่อที่ว่าทำไมเราต้องการ จะทำที่นี่ ตกลง. 

และแล้วในขณะนี้ว่า เราพบ our-- ใช่ 

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

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

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

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

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

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

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

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

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

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

ผู้ชม: รอ ฉันมีคำถาม. 

ANDI เป็ง: ใช่ 

ผู้ชม: ดังนั้นผมจึงเริ่มทำ การค้นหาเชิงเส้นใน helpers.c และมันก็ไม่ได้จริงๆทำงาน แต่แล้วต่อมาผมพบว่าเราเพียงแค่ ต้องลบมันและทำค้นหาแบบทวิภาค ดังนั้นมันไม่สำคัญว่าถ้ามันไม่ทำงาน? 

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

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

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

ผู้ชม: ด้วยพิเศษ ฟังก์ชั่นไม่เรามองเหล่านั้นขึ้น? 

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