1 00:00:00,000 --> 00:00:03,332 >> [เล่นเพลง] 2 00:00:03,332 --> 00:00:06,490 >> ANDI PENG: ยินดีต้อนรับสู่สัปดาห์ที่ 3 ของส่วน 3 00:00:06,490 --> 00:00:09,550 ขอขอบคุณพวกคุณทั้งหมดมา นี้เวลาเริ่มต้นก่อนหน้านี้ในวันนี้ 4 00:00:09,550 --> 00:00:11,466 เรามีความสุขเล็ก ๆ น้อย ๆ กลุ่มที่ใกล้ชิดในวันนี้ 5 00:00:11,466 --> 00:00:14,570 ดังนั้นหวังว่าเราจะได้รับ เสร็จบางทีต้น 6 00:00:14,570 --> 00:00:15,780 ในช่วงต้นในวันนี้นิด ๆ หน่อย ๆ 7 00:00:15,780 --> 00:00:22,057 อย่างรวดเร็วเพียงบางส่วน ประกาศสำหรับวาระการประชุมในวันนี้ 8 00:00:22,057 --> 00:00:23,890 ก่อนที่เราจะเริ่มต้นเรา ไปเพียงแค่ไปมากกว่า 9 00:00:23,890 --> 00:00:28,910 บางประเด็นจิสติกส์สั้น ๆ pset คำถามสอบถามสิ่งที่ต้องการที่ 10 00:00:28,910 --> 00:00:30,250 และจากนั้นเราจะดำน้ำที่เหมาะสมในการ 11 00:00:30,250 --> 00:00:34,710 เราจะใช้บั๊กที่เรียกว่า GDB ไป เริ่มต้น debunking รหัสของเราซึ่งเดวิด 12 00:00:34,710 --> 00:00:36,550 อธิบายในการบรรยายในวันอื่น ๆ 13 00:00:36,550 --> 00:00:39,420 เราจะไปกว่าสี่ประเภทของทุกประเภท 14 00:00:39,420 --> 00:00:42,310 เราจะไปเหนือพวกเขาสวยได้อย่างรวดเร็ว ตั้งแต่พวกเขากำลังเข้มสวย 15 00:00:42,310 --> 00:00:45,710 แต่รู้ว่าสไลด์ทั้งหมดและ รหัสแหล่งที่มาอยู่เสมอออนไลน์ 16 00:00:45,710 --> 00:00:50,810 ดังนั้นรู้สึกฟรีที่อ่านของคุณจะ กลับไปดูที่ว่า 17 00:00:50,810 --> 00:00:53,930 >> เราจะผ่านไป สัญกรณ์ asymptotic ซึ่ง 18 00:00:53,930 --> 00:00:55,944 เป็นเพียงวิธีแฟนซี พูดว่า "runtimes" 19 00:00:55,944 --> 00:00:58,360 ที่เรามีโอขนาดใหญ่ซึ่ง เดวิดอธิบายในการบรรยาย 20 00:00:58,360 --> 00:01:01,550 และเรายังมีโอเมก้าซึ่ง เป็นรันไทม์ขีด จำกัด ล่าง 21 00:01:01,550 --> 00:01:06,450 และเราจะพูดคุยมากขึ้นอีกนิด ในเชิงลึกเกี่ยวกับวิธีการทำงานเหล่านั้น 22 00:01:06,450 --> 00:01:10,160 และสุดท้ายเราจะไปกว่าการค้นหาไบนารี เพราะจำนวนมากของคุณที่มีอยู่แล้ว 23 00:01:10,160 --> 00:01:15,190 เหลือบมองไปที่ psets ของคุณอาจจะรู้ว่า นั่นคือคำถามที่อยู่ใน pset ของคุณ 24 00:01:15,190 --> 00:01:17,470 ดังนั้นทุกท่านจะมีความสุข ที่เราจะกล่าวถึงนี้ในวันนี้ 25 00:01:17,470 --> 00:01:20,610 >> และสุดท้ายต่อของคุณ ส่วนข้อเสนอแนะที่จริงผม 26 00:01:20,610 --> 00:01:23,000 ที่เหลือประมาณ 15 นาที ท้ายที่สุดจะเพียงแค่ไปกว่า 27 00:01:23,000 --> 00:01:27,730 โลจิสติกของ pset3 คำถามใด ๆ บางทีบิตของคำแนะนำถ้าคุณจะ 28 00:01:27,730 --> 00:01:28,990 ก่อนที่เราจะเริ่มต้นการเขียนโปรแกรม 29 00:01:28,990 --> 00:01:30,890 ถ้าอย่างนั้นเราพยายามที่จะได้รับผ่าน วัสดุที่สวยได้อย่างรวดเร็ว 30 00:01:30,890 --> 00:01:33,880 และจากนั้นเราสามารถใช้เวลาบางส่วน คำถามที่เกิดขึ้นสำหรับ pset 31 00:01:33,880 --> 00:01:35,230 ตกลง. 32 00:01:35,230 --> 00:01:39,570 >> ได้อย่างรวดเร็วดังนั้นเพียงไม่กี่ ประกาศก่อนที่เราจะเริ่มต้นในวันนี้ 33 00:01:39,570 --> 00:01:45,410 ประการแรกยินดีที่จะทำ มันผ่านสอง psets ของคุณ 34 00:01:45,410 --> 00:01:49,432 ผมเอาดูที่ใช่ your-- ขอ ได้รับเสียงปรบมือที่หนึ่ง 35 00:01:49,432 --> 00:01:51,140 ที่จริงผมเป็นจริงๆ ประทับใจมาก 36 00:01:51,140 --> 00:01:55,800 ผมให้คะแนน pset แรกสำหรับคุณผู้ชาย สัปดาห์ที่แล้วและพวกคุณได้อย่างไม่น่าเชื่อ 37 00:01:55,800 --> 00:01:58,290 >> สไตล์อยู่บนจุด นอกเหนือจากการแสดงความคิดเห็นไม่กี่ 38 00:01:58,290 --> 00:02:00,660 ให้แน่ใจว่าคุณเสมอ แสดงความคิดเห็นรหัสของคุณ 39 00:02:00,660 --> 00:02:03,040 แต่ psets ของคุณอยู่บนจุด 40 00:02:03,040 --> 00:02:05,549 และให้มันขึ้น 41 00:02:05,549 --> 00:02:08,090 และมันก็เป็นสิ่งที่ดีสำหรับเกรดไป เห็นว่าพวกคุณจะวาง 42 00:02:08,090 --> 00:02:10,704 ในความพยายามที่มากที่สุดเท่าที่ในสไตล์ของคุณ และการออกแบบของคุณในรหัสของคุณ 43 00:02:10,704 --> 00:02:12,120 ที่เราอยากให้คุณเห็น 44 00:02:12,120 --> 00:02:16,450 ดังนั้นฉันผ่านไปความกตัญญูของฉัน สำหรับส่วนที่เหลือของครูที่ 45 00:02:16,450 --> 00:02:19,210 >> อย่างไรก็ตามมี สอบถามคำถามไม่กี่ 46 00:02:19,210 --> 00:02:22,010 ผมแค่อยากจะไปกว่าที่ จะทำให้ชีวิตของทั้งสองของฉัน 47 00:02:22,010 --> 00:02:24,900 และจำนวนมากของคนอื่น ๆ ครูผู้มีชีวิตอยู่บิตง่ายขึ้น 48 00:02:24,900 --> 00:02:28,220 ประการแรกผมได้สังเกตเห็นนี้ ที่ผ่านมา week-- วิธีการหลายท่าน 49 00:02:28,220 --> 00:02:32,301 ได้รับการทำงานใน check50 รหัสของคุณก่อนที่จะส่ง? 50 00:02:32,301 --> 00:02:32,800 ตกลง. 51 00:02:32,800 --> 00:02:36,690 ดังนั้นทุกคนควรจะทำ check50, because-- secret-- เราจริง 52 00:02:36,690 --> 00:02:41,540 check50 ทำงานเป็นส่วนหนึ่งของความถูกต้องของเรา สคริปต์สำหรับการทดสอบรหัสของคุณ 53 00:02:41,540 --> 00:02:45,480 ดังนั้นถ้ารหัสของคุณเป็นความล้มเหลว check50 ในทุกโอกาส 54 00:02:45,480 --> 00:02:47,570 มันอาจจะ ล้มเหลวในการตรวจสอบของเราเช่นกัน 55 00:02:47,570 --> 00:02:49,320 บางครั้งพวกคุณ มีคำตอบที่ถูกต้อง 56 00:02:49,320 --> 00:02:52,200 เช่นเดียวกับในโลภบางส่วนของ คุณมีจำนวนที่เหมาะสม 57 00:02:52,200 --> 00:02:53,960 คุณเพียงแค่พิมพ์ออกมาบางสิ่งที่พิเศษ 58 00:02:53,960 --> 00:02:55,940 และที่ว่าสิ่งที่พิเศษ จริงล้มเหลวในการตรวจสอบ 59 00:02:55,940 --> 00:02:58,440 เนื่องจากคอมพิวเตอร์ไม่ได้ จริงๆรู้ว่าสิ่งที่กำลังมองหา 60 00:02:58,440 --> 00:03:00,981 ดังนั้นมันก็จะวิ่งผ่าน เห็นว่าการส่งออกของคุณไม่ 61 00:03:00,981 --> 00:03:03,810 ตรงกับสิ่งที่เราคาดหวังคำตอบ ที่จะเป็นและทำเครื่องหมายมันเป็นความผิด 62 00:03:03,810 --> 00:03:06,560 >> และฉันรู้ที่เกิดขึ้นใน บางส่วนของกรณีของคุณในสัปดาห์นี้ 63 00:03:06,560 --> 00:03:09,870 ดังนั้นผมจึงเดินกลับด้วยตนเอง regraded รหัสของทุกคน 64 00:03:09,870 --> 00:03:12,780 ในอนาคตว่า กรุณาโปรดให้แน่ใจว่า 65 00:03:12,780 --> 00:03:14,570 ที่คุณกำลังทำงาน การตรวจสอบ 50 รหัสของคุณ 66 00:03:14,570 --> 00:03:17,970 เพราะมันเป็นชนิดของความเจ็บปวดสำหรับ TA ที่ ที่จะมีการกลับไปและตนเอง regrade 67 00:03:17,970 --> 00:03:21,197 ทุก pset เดียวสำหรับทุก เดียวเช่นพลาดเล็ก ๆ น้อย ๆ 68 00:03:21,197 --> 00:03:22,530 ดังนั้นผมจึงไม่ได้ใช้ออกจากจุดใด ๆ 69 00:03:22,530 --> 00:03:25,210 ผมคิดว่าผมอาจจะเอาออก หนึ่งหรือสองสำหรับการออกแบบ 70 00:03:25,210 --> 00:03:27,710 ในอนาคต แต่ถ้า คุณกำลังล้มเหลว check50, 71 00:03:27,710 --> 00:03:31,330 จุดที่จะได้รับ ออกความถูกต้อง 72 00:03:31,330 --> 00:03:35,020 >> นอกจากนี้มี psets เนื่องจากวันศุกร์ตอนเที่ยง 73 00:03:35,020 --> 00:03:38,990 ผมคิดว่ามีเจ็ดนาที ระยะเวลาผ่อนผันปลายที่เราให้คุณ 74 00:03:38,990 --> 00:03:42,434 ฮาร์วาร์ต่อครั้งที่พวกเขาได้รับอนุญาตให้ เจ็ดนาทีจะสายไปทุกอย่าง 75 00:03:42,434 --> 00:03:44,350 ดังนั้นที่นี่ที่เยลเราจะ เป็นไปตามที่ดี 76 00:03:44,350 --> 00:03:47,910 แต่สวยมากที่ 00:07, ถ้า pset ของคุณไม่ได้ใน 77 00:03:47,910 --> 00:03:49,720 มันจะถูกทำเครื่องหมายเป็นช่วงปลายเดือน 78 00:03:49,720 --> 00:03:53,160 ดังนั้นในขณะที่มันมีการทำเครื่องหมาย เป็นสาย TA-- ฉัน 79 00:03:53,160 --> 00:03:54,870 ยังจะได้รับการจัดลำดับ psets ของคุณ 80 00:03:54,870 --> 00:03:56,760 ดังนั้นคุณจะยังคงเห็นเกรดปรากฏ 81 00:03:56,760 --> 00:03:58,820 แต่รู้ว่าที่ ในตอนท้ายของภาคการศึกษาที่ 82 00:03:58,820 --> 00:04:02,270 psets ปลายทั้งหมดจะเป็นเพียง กลายเป็นศูนย์โดยอัตโนมัติโดยคอมพิวเตอร์ 83 00:04:02,270 --> 00:04:04,490 >> เราทำเช่นนี้ด้วยเหตุผลสองประการ 84 00:04:04,490 --> 00:04:09,220 หนึ่งบางครั้งที่เราได้รับ ขอเหมือนข้อแก้ตัวของคณบดี 85 00:04:09,220 --> 00:04:10,762 ภายหลังที่ฉันไม่รู้ยัง 86 00:04:10,762 --> 00:04:13,761 ดังนั้นเราจึงต้องการที่จะทำให้แน่ใจว่าเรากำลังจัดลำดับ ทุกอย่างในกรณีเช่นผม 87 00:04:13,761 --> 00:04:15,080 ข้ออ้างที่ขาดหายไปของคณบดี 88 00:04:15,080 --> 00:04:17,000 และประการที่สองเก็บไว้ใน ใจคุณยังคงสามารถ 89 00:04:17,000 --> 00:04:19,370 วาง pset หนึ่งว่า มีจุดขอบเขต 90 00:04:19,370 --> 00:04:21,430 และเพื่อให้เราชอบที่จะเกรด ทั้งหมดของ psets ของคุณเพียงแค่ 91 00:04:21,430 --> 00:04:24,730 เพื่อให้แน่ใจว่าขอบเขตของคุณ มีและคุณกำลังพยายามที่พวกเขา 92 00:04:24,730 --> 00:04:29,150 ดังนั้นแม้ว่าจะเป็นช่วงปลายคุณจะยังคง ได้รับเครดิตสำหรับขอบเขตจุดที่ผมคิดว่า 93 00:04:29,150 --> 00:04:33,730 >> ดังนั้นคุณธรรมของเรื่องคือให้ psets แน่ใจว่าคุณอยู่ในเวลา 94 00:04:33,730 --> 00:04:38,350 และถ้าพวกเขาไม่ได้ในเวลา รู้ว่ามันไม่ดี 95 00:04:38,350 --> 00:04:41,678 ใช่ก่อนที่ผมจะย้ายไปไม่มีใครมี คำถามใด ๆ เกี่ยวกับข้อเสนอแนะ pset? 96 00:04:41,678 --> 00:04:42,178 ใช่ 97 00:04:42,178 --> 00:04:43,630 >> ผู้ชม: คุณบอกว่าเรา สามารถวางหนึ่ง psets หรือไม่ 98 00:04:43,630 --> 00:04:44,296 >> ANDI เป็ง: ใช่ 99 00:04:44,296 --> 00:04:47,050 ดังนั้นจึงมีเก้า psets โดยรวม ในช่วงเวลาของภาคการศึกษา 100 00:04:47,050 --> 00:04:50,610 และถ้าคุณมีขอบเขต points-- ขอบเขตเพื่อให้เป็นเพียงแค่ 101 00:04:50,610 --> 00:04:53,567 สวยมากที่คุณกำลังพยายาม ปัญหาที่คุณใส่ในเวลา 102 00:04:53,567 --> 00:04:56,150 คุณแสดงให้เห็นว่าคุณได้ แสดงให้เห็นถึงคุณได้อ่านข้อมูลจำเพาะ 103 00:04:56,150 --> 00:04:57,191 นั่นคือขอบเขตสวยมาก 104 00:04:57,191 --> 00:04:59,370 และถ้าคุณตอบสนอง จุดขอบเขตเรา 105 00:04:59,370 --> 00:05:03,360 สามารถวางที่ต่ำที่สุด หนึ่งในขอบเขต 106 00:05:03,360 --> 00:05:06,790 ดังนั้นที่อยู่ในประโยชน์ของคุณ เสร็จสมบูรณ์และพยายามทุก pset 107 00:05:06,790 --> 00:05:10,320 >> แม้ upload-- ถ้าไม่มี พวกเขาทำงานอัปโหลดพวกเขาทั้งหมด 108 00:05:10,320 --> 00:05:13,711 และจากนั้นเราหวังว่าจะสามารถ ให้คุณบางจุดเหล่านั้นกลับมา 109 00:05:13,711 --> 00:05:14,210 เย็น 110 00:05:14,210 --> 00:05:16,780 คำถามใด ๆ อื่น ๆ ? 111 00:05:16,780 --> 00:05:17,840 ที่ดี 112 00:05:17,840 --> 00:05:21,960 >> ประการที่สองสำนักงาน hours-- ไม่กี่ บันทึกย่อเกี่ยวกับเวลาทำการ 113 00:05:21,960 --> 00:05:24,300 ดังนั้นก่อนมาในช่วงต้นสัปดาห์ 114 00:05:24,300 --> 00:05:26,909 ไม่มีใครที่เคย เวลาทำการในวันจันทร์ 115 00:05:26,909 --> 00:05:28,700 คริสมาถึง เวลาทำการคืนที่ผ่านมา 116 00:05:28,700 --> 00:05:29,691 ใช่คริส 117 00:05:29,691 --> 00:05:32,190 และสิ่งที่พวกเราได้ที่สำนักงาน ชั่วโมงคืนที่ผ่านมาคริส? 118 00:05:32,190 --> 00:05:33,020 >> ผู้ชม: เรามีไอศครีม 119 00:05:33,020 --> 00:05:36,160 >> ANDI PENG: ดังนั้นที่เหมาะสมที่เรามี ไอศครีมที่เวลาทำการคืนที่ผ่านมา 120 00:05:36,160 --> 00:05:39,390 ในขณะที่ฉันไม่สามารถสัญญาว่า เราจะมีไอศครีมในเวลาทำการ 121 00:05:39,390 --> 00:05:43,230 ทุกสัปดาห์สิ่งที่ฉันสามารถสัญญาคุณ คือว่าจะมีอย่างมีนัยสำคัญ 122 00:05:43,230 --> 00:05:45,380 นักเรียนที่ดีกว่าอัตราส่วน TA 123 00:05:45,380 --> 00:05:47,650 เช่นเดียวกับที่ legit ก็เหมือน 3-1 124 00:05:47,650 --> 00:05:50,350 ในขณะที่ความคมชัดด้วย วันพฤหัสบดีที่คุณได้มีประมาณ 150 125 00:05:50,350 --> 00:05:52,830 เด็กเครียดจริงๆและไอศครีมไม่ 126 00:05:52,830 --> 00:05:55,360 และมันก็เป็นเพียงแค่ไม่ได้ผลิตสำหรับทุกคน 127 00:05:55,360 --> 00:05:58,730 ดังนั้นคุณธรรมของเรื่องราวเป็นมาในช่วงต้น ชั่วโมงสำนักงานและสิ่งที่ดี 128 00:05:58,730 --> 00:06:00,310 จะเกิดขึ้น. 129 00:06:00,310 --> 00:06:02,110 >> นอกจากนี้ยังมาพร้อมที่จะถามคำถาม 130 00:06:02,110 --> 00:06:03,200 คุณรู้? 131 00:06:03,200 --> 00:06:05,420 ไม่ว่าสิ่งที่สอนผม คิดว่าได้รับการกล่าวว่า 132 00:06:05,420 --> 00:06:10,710 เราได้รับนักเรียนคู่ ที่เข้ามาในวันพฤหัสบดีที่เหมือน 10:50 133 00:06:10,710 --> 00:06:15,100 ไม่ได้มีการอ่านข้อมูลจำเพาะ เป็นเหมือนช่วยฉันช่วยฉัน 134 00:06:15,100 --> 00:06:18,200 แต่น่าเสียดายที่จุดที่มี ไม่มากที่เราสามารถทำได้เพื่อช่วยให้คุณ 135 00:06:18,200 --> 00:06:19,590 ดังนั้นโปรดมาในช่วงต้นสัปดาห์ 136 00:06:19,590 --> 00:06:22,040 ก่อนที่จะมาเวลาทำการ 137 00:06:22,040 --> 00:06:23,350 มาเตรียมความพร้อมที่จะถามคำถาม 138 00:06:23,350 --> 00:06:25,310 ให้แน่ใจว่าคุณเป็น นักเรียนจะอยู่ที่ไหน 139 00:06:25,310 --> 00:06:27,620 คุณจะต้องมีเพื่อให้ ครูสามารถแนะนำคุณพร้อม 140 00:06:27,620 --> 00:06:32,850 ซึ่งเป็นสิ่งที่เวลาทำงาน ควรจะกำหนดให้สำหรับ 141 00:06:32,850 --> 00:06:37,380 >> ประการที่สองเพื่อให้ฉันรู้อาจารย์ ชอบที่จะแปลกใจเรามีการทดสอบ 142 00:06:37,380 --> 00:06:39,439 ผมมีอาจารย์เหล่านั้น เหมือน yo, โดยวิธีการที่ 143 00:06:39,439 --> 00:06:41,230 จำกลางเทอมที่ คุณมีวันจันทร์ถัดไป 144 00:06:41,230 --> 00:06:42,855 ใช่ฉันไม่ทราบเกี่ยวกับมิดเทอมที่ 145 00:06:42,855 --> 00:06:45,630 ดังนั้นฉันจะเป็นไปได้ว่า TA ที่เตือนคุณทุกคนที่ตอบคำถาม 146 00:06:45,630 --> 00:06:47,270 0-- เพราะคุณรู้ว่าเรากำลังพัฒนา 147 00:06:47,270 --> 00:06:50,730 ตอนนี้ที่เราได้ทำอาร์เรย์คุณจะได้รับ ทำไมมันตอบคำถาม 0 ไม่ตอบคำถาม 1 ใช่มั้ย? 148 00:06:50,730 --> 00:06:51,320 ตกลง. 149 00:06:51,320 --> 00:06:52,490 โอ้ผมได้หัวเราะเบา ๆ บางคนที่หนึ่ง 150 00:06:52,490 --> 00:06:53,120 ตกลง. 151 00:06:53,120 --> 00:06:59,710 >> ตอบคำถามดังนั้น 0 จะเป็น 14 ตุลาคมถ้า คุณอยู่ในส่วนของวันจันทร์ถึงวันพุธ 152 00:06:59,710 --> 00:07:02,920 และ 15 ตุลาคมถ้าคุณอยู่ใน ส่วนวันอังคารพฤหัสบดี 153 00:07:02,920 --> 00:07:05,630 นี้ไม่ได้นำไปใช้สำหรับ บรรดาของคุณที่ Harvard 154 00:07:05,630 --> 00:07:10,350 who-- ฉันคิดว่าคุณทุกคนจะ การทดสอบของคุณในวันที่ 14 155 00:07:10,350 --> 00:07:13,560 >> เพื่อใช่ในสัปดาห์ถัดไปถ้า เดวิดในการบรรยายไป 156 00:07:13,560 --> 00:07:15,747 ใช่มากเกี่ยวกับว่า ตอบคำถามในสัปดาห์หน้าทุกท่าน 157 00:07:15,747 --> 00:07:17,580 จะไม่ต้องตกใจเพราะ คุณมาส่วน 158 00:07:17,580 --> 00:07:19,664 และคุณรู้ว่าคุณ การตอบคำถามเป็น 0 ในอีกสองสัปดาห์ 159 00:07:19,664 --> 00:07:21,580 และเราจะมีการตรวจสอบ การประชุมและทุกอย่าง 160 00:07:21,580 --> 00:07:26,360 ดังนั้นไม่ต้องกังวลเกี่ยวกับ กลัวถูกว่า 161 00:07:26,360 --> 00:07:29,890 คำถามใด ๆ before-- คำถามใด ๆ ในประเด็นที่เกี่ยวกับโลจิสติกทั้งหมด, 162 00:07:29,890 --> 00:07:32,591 การจัดลำดับเวลาทำงานส่วน? 163 00:07:32,591 --> 00:07:33,090 ใช่ 164 00:07:33,090 --> 00:07:35,100 >> ผู้ชม: ดังนั้นคำถามคือ ไปได้ในระหว่างการบรรยาย? 165 00:07:35,100 --> 00:07:35,766 >> ANDI เป็ง: ใช่ 166 00:07:35,766 --> 00:07:39,460 ดังนั้นการตอบคำถามที่ผมคิดว่าเป็น 60 นาทีที่กำหนดในช่วงเวลาที่ 167 00:07:39,460 --> 00:07:42,240 ที่คุณเพิ่งจะใช้เวลา ในห้องโถงบรรยาย 168 00:07:42,240 --> 00:07:44,810 ดังนั้นคุณจึงไม่ต้องมาใน ขึ้นเช่นการสุ่ม 07:00 169 00:07:44,810 --> 00:07:46,140 มันเป็นเรื่องดีทั้งหมด. 170 00:07:46,140 --> 00:07:47,100 ใช่ 171 00:07:47,100 --> 00:07:50,060 เย็น 172 00:07:50,060 --> 00:07:50,840 >> ทั้งหมดขวา 173 00:07:50,840 --> 00:07:54,330 ดังนั้นเรากำลังจะไป นำเสนอแนวคิดให้กับคุณ 174 00:07:54,330 --> 00:08:00,760 ในสัปดาห์นี้ว่าเดวิดชนิดที่มีอยู่แล้ว การสัมผัสกับการบรรยายในสัปดาห์ที่ผ่านมา 175 00:08:00,760 --> 00:08:02,010 มันเรียกว่า GDB 176 00:08:02,010 --> 00:08:05,570 และวิธีการที่หลายท่านในขณะที่ใน หลักสูตรการเขียน psets ของคุณ 177 00:08:05,570 --> 00:08:09,981 ได้สังเกตเห็นปุ่มใหญ่ที่บอกว่า "การแก้ปัญหา" ที่ด้านบนของ IDE ของคุณ? 178 00:08:09,981 --> 00:08:10,480 ตกลง. 179 00:08:10,480 --> 00:08:13,770 ดังนั้นตอนนี้เราจริงจะได้รับการพบ ความลึกลับของสิ่งที่ปุ่มจริง 180 00:08:13,770 --> 00:08:14,270 ทำ. 181 00:08:14,270 --> 00:08:16,790 และผมรับประกันคุณมันเป็น สวยงามสิ่งที่สวยงาม 182 00:08:16,790 --> 00:08:20,740 >> ดังนั้นจนถึงขณะนี้ผมคิดว่า มีการสองสิ่ง 183 00:08:20,740 --> 00:08:23,320 นักเรียนที่ได้รับมักจะ ทำเมื่อการแก้จุดบกพร่อง psets 184 00:08:23,320 --> 00:08:27,635 หนึ่งพวกเขาทั้งสองเพิ่ม printf () - เพื่อให้ทุกไม่กี่บรรทัด, 185 00:08:27,635 --> 00:08:29,760 พวกเขาเพิ่มใน printf () - โอ้สิ่งที่เป็นตัวแปรนี้? 186 00:08:29,760 --> 00:08:32,551 โอ้สิ่งที่เป็นตัวแปรนี้ now-- และคุณจะเห็นชนิดของความก้าวหน้า 187 00:08:32,551 --> 00:08:33,940 ของรหัสของคุณขณะที่มันวิ่ง 188 00:08:33,940 --> 00:08:37,030 หรือเด็กที่วิธีที่สองทำคือ ว่าพวกเขาเพียงแค่เขียนสิ่งที่ทั้ง 189 00:08:37,030 --> 00:08:38,610 และจากนั้นไปเช่นนี้ในตอนท้าย 190 00:08:38,610 --> 00:08:39,970 หวังว่ามันทำงาน 191 00:08:39,970 --> 00:08:44,851 ผมรับประกันคุณ GDB จะดีกว่า กว่าทั้งสองวิธีการเหล่านั้น 192 00:08:44,851 --> 00:08:45,350 ใช่ 193 00:08:45,350 --> 00:08:46,980 ดังนั้นนี้จะเป็นเพื่อนที่ดีที่สุดของคุณใหม่ 194 00:08:46,980 --> 00:08:51,780 เพราะมันเป็นสิ่งที่สวยงาม ที่แสดงทั้งภาพ 195 00:08:51,780 --> 00:08:54,850 สิ่งที่รหัสของคุณจะทำ ที่จุดที่เฉพาะเจาะจง 196 00:08:54,850 --> 00:08:57,486 เช่นเดียวกับสิ่งที่ทุกคนที่คุณ ตัวแปรที่จะแบก, 197 00:08:57,486 --> 00:08:59,610 เหมือนสิ่งที่มีค่าของพวกเขา ที่จุดเฉพาะที่ 198 00:08:59,610 --> 00:09:02,670 และด้วยวิธีนี้คุณสามารถจริงๆ จุดพักตั้งอยู่ในรหัสของคุณ 199 00:09:02,670 --> 00:09:04,350 คุณสามารถเรียกใช้ผ่านทีละบรรทัด 200 00:09:04,350 --> 00:09:07,324 และ GDB ก็จะมี คุณแสดงสำหรับคุณ 201 00:09:07,324 --> 00:09:09,490 สิ่งที่ตัวแปรทั้งหมดของคุณ จะสิ่งที่พวกเขากำลังทำ 202 00:09:09,490 --> 00:09:10,656 สิ่งที่เกิดขึ้นในรหัส 203 00:09:10,656 --> 00:09:13,240 และในลักษณะที่มันเป็น ง่ายมากที่จะเห็น 204 00:09:13,240 --> 00:09:17,120 สิ่งที่เกิดขึ้นแทนการ printf ไอเอ็นจี หรือเขียนลงงบของคุณ 205 00:09:17,120 --> 00:09:19,160 >> ดังนั้นเราจะทำเช่นนี้ในภายหลัง 206 00:09:19,160 --> 00:09:20,660 ดังนั้นนี้ดูเหมือนนามธรรมบิต 207 00:09:20,660 --> 00:09:23,490 ไม่ต้องกังวลเราจะทำตัวอย่าง 208 00:09:23,490 --> 00:09:29,170 และเพื่อให้เป็นหลักทั้งสามที่ใหญ่ที่สุด ฟังก์ชั่นที่ใช้มากที่สุดที่คุณจะต้องใน GDB 209 00:09:29,170 --> 00:09:32,500 อยู่ถัดไปขั้นตอนที่มากกว่า และก้าวเข้าสู่ปุ่ม 210 00:09:32,500 --> 00:09:34,860 ฉันจะตรงไป มีจริงในขณะนี้ 211 00:09:34,860 --> 00:09:40,930 >> ดังนั้นคุณจึงสามารถทุกคนเห็นว่า หรือฉันควรซูมในบิต? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 ในด้านหลังคุณจะเห็นว่า? 214 00:09:44,470 --> 00:09:45,730 ฉันควรจะซูมมีอะไรบ้าง? 215 00:09:45,730 --> 00:09:46,480 นิดหน่อย? 216 00:09:46,480 --> 00:09:49,390 ตกลงเย็น 217 00:09:49,390 --> 00:09:50,280 เราจะไปที่นั่น. 218 00:09:50,280 --> 00:09:50,960 ตกลง. 219 00:09:50,960 --> 00:09:57,000 >> ดังนั้นผมจึงมีที่นี่ของฉัน การดำเนินงานสำหรับโลภ 220 00:09:57,000 --> 00:10:01,430 และในขณะที่จำนวนมากของพวกคุณเขียน โลภในขณะที่วง form-- ว่า 221 00:10:01,430 --> 00:10:04,890 เป็นวิธีที่ดีที่สุดที่ได้รับการยอมรับที่จะทำ it-- วิธีที่จะทำก็คือการอื่น 222 00:10:04,890 --> 00:10:06,280 แบ่งในแบบโมดูโล 223 00:10:06,280 --> 00:10:09,290 แล้วเพราะคุณสามารถมีของคุณ มูลค่าแล้วมีที่เหลือของคุณ 224 00:10:09,290 --> 00:10:11,150 และจากนั้นคุณก็สามารถ เพิ่มไว้ด้วยกัน 225 00:10:11,150 --> 00:10:13,390 ไม่ตรรกะของสิ่งที่ฉันทำ ที่นี่ให้ความรู้สึกกับทุกคน 226 00:10:13,390 --> 00:10:14,117 ก่อนที่เราจะเริ่มต้น? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 ชนิดของ? 229 00:10:17,980 --> 00:10:18,710 เย็น 230 00:10:18,710 --> 00:10:19,210 ที่ดี 231 00:10:19,210 --> 00:10:21,290 มันเป็นชิ้นสวยเซ็กซี่ รหัสผมจะบอกว่า 232 00:10:21,290 --> 00:10:23,502 เช่นฉันกล่าวว่าเดวิดใน บรรยายหลังจากที่ในขณะที่ 233 00:10:23,502 --> 00:10:25,960 ทุกท่านจะเริ่มเห็นรหัส เป็นสิ่งที่สวยงาม 234 00:10:25,960 --> 00:10:29,950 และบางครั้งเมื่อคุณเห็นความสวยงาม รหัสมันเป็นความรู้สึกที่ยอดเยี่ยม 235 00:10:29,950 --> 00:10:35,410 >> ดังนั้นอย่างไรก็ตามในขณะที่รหัสนี้เป็นอย่างมาก ที่สวยงามก็ไม่ได้ทำงานอย่างถูกต้อง 236 00:10:35,410 --> 00:10:37,750 ดังนั้นขอเรียก check50 เกี่ยวกับเรื่องนี้ 237 00:10:37,750 --> 00:10:39,440 ตรวจสอบ 50 20-- OOP 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 เป็น pset2 ที่? 241 00:10:44,990 --> 00:10:46,870 ใช่ 242 00:10:46,870 --> 00:10:47,520 โอ้ pset1 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 ตกลง. 245 00:10:52,890 --> 00:10:53,900 ดังนั้นเราจึงเรียก check50 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> และในขณะที่พวกคุณสามารถดูที่นี่ มันเป็นความล้มเหลวในคู่ของกรณี 248 00:11:07,170 --> 00:11:10,165 และสำหรับบางส่วนของคุณใน หลักสูตรการทำชุดปัญหาของคุณ 249 00:11:10,165 --> 00:11:11,110 คุณต้องการ ah, ทำไมไม่ได้ทำงาน 250 00:11:11,110 --> 00:11:13,318 มันเป็นเหตุผลที่การทำงานบางอย่าง ค่า แต่ไม่ใช่สำหรับคนอื่น ๆ ? 251 00:11:13,318 --> 00:11:17,760 ดี GDB จะช่วยให้รูปคุณ ปัจจัยการผลิตออกว่าทำไมผู้ที่ไม่ได้ทำงาน 252 00:11:17,760 --> 00:11:18,320 >> ตกลง. 253 00:11:18,320 --> 00:11:21,640 ดังนั้นเรามาดูซึ่งเป็นหนึ่งใน การตรวจสอบผมก็ล้มเหลวใน check50 254 00:11:21,640 --> 00:11:24,920 เป็นค่าที่ป้อนข้อมูลของ 0.41 255 00:11:24,920 --> 00:11:27,830 ดังนั้นคำตอบที่ถูกต้องที่ คุณควรจะได้รับเป็น 4 256 00:11:27,830 --> 00:11:33,090 แต่สิ่งที่ผมพิมพ์ออก เป็น 3 n ซึ่งไม่ถูกต้อง 257 00:11:33,090 --> 00:11:36,190 เพื่อให้เพียงทำงานนี้ด้วยตนเองเพียง ตรวจสอบให้แน่ใจ check50 ที่ทำงาน 258 00:11:36,190 --> 00:11:36,940 ขอทำ ./greedy 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 โอ๊ะฉันจะต้องทำโลภ 261 00:11:43,340 --> 00:11:43,840 เราจะไปที่นั่น. 262 00:11:43,840 --> 00:11:44,381 ตอนนี้ ./greedy 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> วิธีที่เป็นหนี้มาก? 265 00:11:47,670 --> 00:11:49,550 ขอทำ 0.41 266 00:11:49,550 --> 00:11:52,590 และครับเราจะเห็นที่นี่ ว่ามันแสดงผล 3 267 00:11:52,590 --> 00:11:55,160 เมื่อคำตอบที่ถูกต้อง ในความเป็นจริงควรจะเป็น 4 268 00:11:55,160 --> 00:12:01,460 ดังนั้นขอใส่ GDB และดูวิธีการที่เรา สามารถไปเกี่ยวกับการแก้ไขปัญหานี้ 269 00:12:01,460 --> 00:12:03,992 >> ดังนั้นขั้นตอนแรกใน มักจะแก้จุดบกพร่องรหัสของคุณ 270 00:12:03,992 --> 00:12:05,950 คือการตั้งจุดพัก, หรือจุดที่คุณ 271 00:12:05,950 --> 00:12:09,079 หรือต้องการให้คอมพิวเตอร์ที่ ดีบักจะเริ่มมองหาที่ 272 00:12:09,079 --> 00:12:11,120 ดังนั้นถ้าคุณไม่ได้จริงๆ รู้ว่าสิ่งที่เป็นปัญหาของคุณคือ 273 00:12:11,120 --> 00:12:14,670 มักจะเป็นสิ่งปกติท​​ี่เราต้องการ ทำคือการตั้งจุดพักของเราที่หลัก 274 00:12:14,670 --> 00:12:18,520 ดังนั้นหากพวกคุณสามารถดูนี้ ปุ่มสีแดงที่นั่น 275 00:12:18,520 --> 00:12:22,860 ครับที่ผมตั้งค่า จุดพักสำหรับฟังก์ชั่นหลัก 276 00:12:22,860 --> 00:12:24,130 ฉันคลิกที่ 277 00:12:24,130 --> 00:12:26,130 >> แล้วผมสามารถไปถึงปุ่ม Debug ของฉัน 278 00:12:26,130 --> 00:12:27,036 ผมกดปุ่มที่ 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 ผมขอขยายกลับว่าฉันสามารถ 281 00:12:36,555 --> 00:12:38,020 เราจะไปที่นั่น. 282 00:12:38,020 --> 00:12:40,730 ดังนั้นเราจึงมีที่นี่แผงด้านขวา 283 00:12:40,730 --> 00:12:43,680 ฉันขอโทษคนที่อยู่ด้านหลังคุณ ไม่สามารถจริงๆดูดีจริงๆ 284 00:12:43,680 --> 00:12:49,090 แต่เป็นหลักทั้งหมด นี้ทางด้านขวาจะทำ 285 00:12:49,090 --> 00:12:53,130 คือการติดตามทั้งเน้น สายซึ่งเป็นบรรทัดของรหัส 286 00:12:53,130 --> 00:12:56,640 ว่าคอมพิวเตอร์ในปัจจุบันคือการทำงาน เช่นเดียวกับตัวแปรทั้งหมดของคุณ 287 00:12:56,640 --> 00:12:57,600 ลงที่นี่ 288 00:12:57,600 --> 00:13:00,487 >> ดังนั้นคุณมีเซ็นต์, เหรียญ, n, ประกาศทั้งหมดเพื่อสิ่งที่แตกต่าง 289 00:13:00,487 --> 00:13:01,070 ณ จุดนี้. 290 00:13:01,070 --> 00:13:04,850 ไม่ต้องกังวลเพราะเรามีไม่จริง พวกเขาเริ่มต้นกับตัวแปรใด ๆ 291 00:13:04,850 --> 00:13:07,200 ดังนั้นในเครื่องคอมพิวเตอร์ของคุณของคุณ คอมพิวเตอร์เป็นเพียงแค่เห็น 292 00:13:07,200 --> 00:13:14,376 โอ้ 32,767 เป็นฟังก์ชั่นใช้ล่าสุด จากการที่พื้นที่หน่วยความจำในคอมพิวเตอร์ของฉัน 293 00:13:14,376 --> 00:13:16,000 และเพื่อให้เป็นที่เซ็นต์อยู่ในขณะนี้ 294 00:13:16,000 --> 00:13:19,360 แต่ไม่ว่าเมื่อคุณเรียกใช้รหัส มันจะกลายเป็นที่เริ่ม 295 00:13:19,360 --> 00:13:24,110 >> ดังนั้นขอให้ผ่านไปโดยสาย บรรทัดสิ่งที่เกิดขึ้นที่นี่ 296 00:13:24,110 --> 00:13:25,350 ตกลง. 297 00:13:25,350 --> 00:13:29,400 ดังนั้นที่นี่เป็นสาม ปุ่มที่ฉันเพียงแค่อธิบาย 298 00:13:29,400 --> 00:13:34,090 คุณต้องเล่นหรือฟังก์ชั่นเรียกใช้ ปุ่มคุณมีขั้นตอนมากกว่าปุ่ม 299 00:13:34,090 --> 00:13:36,600 และคุณยังมีขั้นตอนที่ลงในปุ่ม 300 00:13:36,600 --> 00:13:41,260 และเป็นหลักทั้งสาม พวกเขาเพียงแค่ผ่านรห​​ัสของคุณ 301 00:13:41,260 --> 00:13:42,690 และทำในสิ่งที่แตกต่างกัน 302 00:13:42,690 --> 00:13:45,680 >> ดังนั้นโดยปกติเมื่อคุณกำลังตรวจแก้จุดบกพร่อง เราไม่ต้องการที่จะเพียงแค่กดเล่น 303 00:13:45,680 --> 00:13:47,930 เพราะการเล่นก็จะทำงาน รหัสของคุณไปยังจุดสิ้นสุดของมัน 304 00:13:47,930 --> 00:13:49,070 แล้วคุณจะไม่จริง รู้ว่าสิ่งที่เป็นปัญหาของคุณ 305 00:13:49,070 --> 00:13:51,432 คือถ้าคุณตั้งจุดพักหลาย 306 00:13:51,432 --> 00:13:53,890 ถ้าคุณตั้งจุดพักหลาย มันจะเพียงโดยอัตโนมัติ 307 00:13:53,890 --> 00:13:56,030 วิ่งออกจากจุดพักหนึ่ง, ถัดไปถัดไป 308 00:13:56,030 --> 00:13:58,030 แต่ในกรณีนี้เราได้ เพียงแค่ว่าหนึ่งเพราะเรา 309 00:13:58,030 --> 00:13:59,970 ต้องการที่จะทำงานทางของเรา จากด้านบนลงไปด้านล่าง 310 00:13:59,970 --> 00:14:04,830 ดังนั้นเรากำลังจะไปที่จะไม่สนใจที่ปุ่ม ในขณะนี้สำหรับวัตถุประสงค์ของโปรแกรมนี้ 311 00:14:04,830 --> 00:14:08,230 >> ดังนั้นขั้นตอนที่มากกว่าเพียงแค่ฟังก์ชั่น ขั้นตอนมากกว่าทุกบรรทัดเดียว 312 00:14:08,230 --> 00:14:11,510 และบอกคุณว่า คอมพิวเตอร์จะทำ 313 00:14:11,510 --> 00:14:14,630 ขั้นตอนในการทำงานไป เข้าสู่ฟังก์ชั่นที่เกิดขึ้นจริง 314 00:14:14,630 --> 00:14:16,000 ที่อยู่ในสายของคุณรหัส 315 00:14:16,000 --> 00:14:19,070 ดังนั้นสำหรับตัวอย่างเช่น printf () ที่เป็นฟังก์ชั่นใช่มั้ย? 316 00:14:19,070 --> 00:14:21,980 ถ้าผมต้องการที่จะขั้นตอนทางร่างกาย เข้าสู่ printf () ฟังก์ชั่น 317 00:14:21,980 --> 00:14:25,610 ที่จริงผมจะไปลงในชิ้นส่วนของ รหัสที่ printf () ถูกเขียนและดู 318 00:14:25,610 --> 00:14:26,730 สิ่งที่เกิดขึ้นที่นั่น. 319 00:14:26,730 --> 00:14:29,924 >> แต่โดยทั่วไปแล้วเราคิดว่า รหัสที่เราให้คุณได้งาน 320 00:14:29,924 --> 00:14:31,340 เราคิด printf () ที่จะทำงาน 321 00:14:31,340 --> 00:14:33,170 เราคิดว่า GetInt () จะทำงาน 322 00:14:33,170 --> 00:14:35,170 ดังนั้นจึงมีความจำเป็นที่จะไม่มี ก้าวเข้าสู่ฟังก์ชั่นเหล่านั้น 323 00:14:35,170 --> 00:14:37,170 แต่ถ้ามีฟังก์ชั่น ที่คุณเขียนเอง 324 00:14:37,170 --> 00:14:39,060 ที่คุณต้องการตรวจสอบ สิ่งที่เกิดขึ้น 325 00:14:39,060 --> 00:14:41,200 คุณต้องการที่จะก้าว ในการทำงานที่ 326 00:14:41,200 --> 00:14:43,940 >> ดังนั้นตอนนี้เรากำลังจะ ที่จะก้าวข้ามชิ้นส่วนของรหัสนี้ 327 00:14:43,940 --> 00:14:44,485 ดังนั้นเรามาดู 328 00:14:44,485 --> 00:14:46,547 โอ้พิมพ์ "โอ้ไห่วิธี การเปลี่ยนแปลงมากเป็นหนี้? " 329 00:14:46,547 --> 00:14:47,130 เราไม่ได้ดูแล 330 00:14:47,130 --> 00:14:49,830 เรารู้ว่าการทำงาน, เพื่อให้เราก้าวข้ามมัน 331 00:14:49,830 --> 00:14:53,290 >> ดังนั้น n ซึ่งคือลอยของเราที่ เราได้ initialized-- หรือ declared-- 332 00:14:53,290 --> 00:14:56,810 ขึ้นที่ด้านบนเราในขณะนี้ เท่ากับว่า GetFloat () 333 00:14:56,810 --> 00:14:57,810 ดังนั้นขอให้ก้าวข้ามว่า 334 00:14:57,810 --> 00:14:59,580 และเราจะเห็นที่ ด้านล่างนี่โปรแกรม 335 00:14:59,580 --> 00:15:03,360 จะแจ้งให้ผมใส่ค่า 336 00:15:03,360 --> 00:15:08,580 ดังนั้นขอค่าการป้อนข้อมูลที่เราต้องการ ในการทดสอบที่นี่ซึ่งเป็น 0.41 337 00:15:08,580 --> 00:15:09,160 ที่ดี 338 00:15:09,160 --> 00:15:12,780 >> ดังนั้นตอนนี้ n-- ทำพวกคุณเห็น ที่นี่ที่ bottom-- มัน 339 00:15:12,780 --> 00:15:15,140 stored-- เพราะเรา โค้งมนไม่ได้เลยก็ 340 00:15:15,140 --> 00:15:19,540 เก็บไว้ในนี้เหมือนยักษ์ ลอยที่เป็น 0.4099999996, 341 00:15:19,540 --> 00:15:22,550 ซึ่งอยู่ใกล้พอที่จะของเรา วัตถุประสงค์ในขณะนี้ 0.41 342 00:15:22,550 --> 00:15:26,090 และจากนั้นเราจะได้เห็นต่อไปในขณะที่เรา ยังคงก้าวมากกว่าโปรแกรม 343 00:15:26,090 --> 00:15:29,850 หลังจากที่นี่ได้กลายเป็น n โค้งมนและเซ็นต์ได้กลายเป็น 41 344 00:15:29,850 --> 00:15:30,350 ที่ดี 345 00:15:30,350 --> 00:15:32,230 ดังนั้นเราจึงรู้ว่าการทำงานการปัดเศษของเรา 346 00:15:32,230 --> 00:15:34,700 เรารู้ว่าเรามี จำนวนที่ถูกต้องของเซนต์ 347 00:15:34,700 --> 00:15:36,990 เพื่อให้เรารู้ว่าที่ ไม่ได้จริงๆปัญหา 348 00:15:36,990 --> 00:15:40,050 >> ดังนั้นเรายังคงก้าว ในโปรแกรมนี้ 349 00:15:40,050 --> 00:15:40,900 เราไปที่นี่ 350 00:15:40,900 --> 00:15:46,139 และดังนั้นหลังจากบรรทัดของรหัสนี้เรา ควรทราบว่าหลายไตรมาสที่เรามี 351 00:15:46,139 --> 00:15:46,680 เราก้าวข้าม 352 00:15:46,680 --> 00:15:52,040 และคุณจะเห็นเราในความเป็นจริงมีหนึ่ง ไตรมาสเพราะเราได้หักออก 25 353 00:15:52,040 --> 00:15:53,790 จากค่าเริ่มต้นของ 41 354 00:15:53,790 --> 00:15:55,890 และเรามี 16 ซ้ายเซ็นต์ของเรา 355 00:15:55,890 --> 00:15:58,830 >> ไม่ทุกคนเข้าใจว่า โปรแกรมจะก้าวผ่าน 356 00:15:58,830 --> 00:16:02,980 และเหตุผลที่เซ็นต์ในขณะนี้ได้กลายเป็น 16 และเหตุผลที่ตอนนี้ได้กลายเป็นเหรียญ 1 357 00:16:02,980 --> 00:16:04,610 ต่อไปนี้ทุกคนจะตรรกะที่? 358 00:16:04,610 --> 00:16:05,110 เย็น 359 00:16:05,110 --> 00:16:07,860 ดังนั้น ณ จุดนี้ การทำงานของโปรแกรมใช่ไหม? 360 00:16:07,860 --> 00:16:09,797 เรารู้ว่ามันทำตรง สิ่งที่เราต้องการให้ 361 00:16:09,797 --> 00:16:11,880 และเราไม่ได้จริง ต้องพิมพ์ออกมาโอ้สิ่งที่ 362 00:16:11,880 --> 00:16:14,430 เป็นเซนต์ปิดที่จุดนี้ สิ่งที่เป็นเหรียญที่จุดนี้ 363 00:16:14,430 --> 00:16:17,170 >> เรายังคงต้องผ่านโปรแกรม 364 00:16:17,170 --> 00:16:18,100 ขั้นตอนที่มากกว่า 365 00:16:18,100 --> 00:16:18,620 เย็น 366 00:16:18,620 --> 00:16:19,700 เราไปกว่าสลึง 367 00:16:19,700 --> 00:16:20,200 ที่ดี 368 00:16:20,200 --> 00:16:22,367 เราจะเห็นว่าก็เอา ปิด $ 0.10 สำหรับค่าเล็กน้อย 369 00:16:22,367 --> 00:16:23,450 และตอนนี้เรามีสองเหรียญ 370 00:16:23,450 --> 00:16:25,260 ถูกต้อง. 371 00:16:25,260 --> 00:16:31,555 >> เราไปกว่าเพนนีและเราจะเห็น ที่เราได้มีการเซ็นต์ที่เหลือ 372 00:16:31,555 --> 00:16:32,680 อืมที่แปลก 373 00:16:32,680 --> 00:16:37,540 ขึ้นที่นี่ที่โปรแกรมที่ผมควร จะมีการหักออก pennies ของฉัน 374 00:16:37,540 --> 00:16:39,400 บางทีผมก็ไม่ได้ ทำตอนสาย 375 00:16:39,400 --> 00:16:42,190 และอนิจจาคุณสามารถดู ที่นี่เพราะเรารู้ว่า 376 00:16:42,190 --> 00:16:44,360 ที่เราจะก้าว ผ่านสาย 32 และ 33, 377 00:16:44,360 --> 00:16:50,560 นั่นคือสิ่งที่โปรแกรมของเรา ไม่ถูกต้องมีตัวแปรทำงาน 378 00:16:50,560 --> 00:16:55,136 ดังนั้นเราจึงสามารถมองและดูโอ้ ฉันลบเซ็นต์ที่นี่ 379 00:16:55,136 --> 00:16:57,010 แต่ฉันไม่จริง การเพิ่มค่าเหรียญของฉัน 380 00:16:57,010 --> 00:16:57,860 ผมเพิ่มให้เซ็นต์ 381 00:16:57,860 --> 00:17:00,234 และผมไม่ต้องการที่จะเพิ่ม เซ็นต์ผมต้องการที่จะเพิ่มเหรียญ 382 00:17:00,234 --> 00:17:05,420 ดังนั้นหากเราเปลี่ยนที่เหรียญ เรามีโปรแกรมการทำงาน 383 00:17:05,420 --> 00:17:06,730 ฉันสามารถเรียกใช้ check50 384 00:17:06,730 --> 00:17:11,063 คุณก็สามารถออกจากทางด้านขวา GDB ที่นี่และเรียกใช้ check50 อีกครั้ง 385 00:17:11,063 --> 00:17:11,938 ฉันสามารถทำเช่นนี้ 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 ฉันจะต้องทำโลภ 388 00:17:18,480 --> 00:17:19,940 0.41 389 00:17:19,940 --> 00:17:22,819 และที่นี่ก็พิมพ์ คำตอบที่ถูกต้อง 390 00:17:22,819 --> 00:17:26,569 >> ดังนั้นในขณะที่พวกคุณสามารถดู GDB เป็นเครื่องมือที่มีประสิทธิภาพจริงๆ 391 00:17:26,569 --> 00:17:29,940 เมื่อเรามีรหัสมาก ที่เกิดขึ้นและตัวแปรจำนวนมากดังนั้น 392 00:17:29,940 --> 00:17:32,510 ว่ามันเป็นเรื่องยากสำหรับเราเป็น มนุษย์ที่จะติดตาม 393 00:17:32,510 --> 00:17:35,360 คอมพิวเตอร์ใน GDB ดีบักมีความสามารถใน 394 00:17:35,360 --> 00:17:37,020 ในการติดตามของทุกอย่าง 395 00:17:37,020 --> 00:17:40,480 ฉันรู้ว่าใน Visionaire พวกคุณอาจจะ อาจจะมีบางอย่างผิดพลาดตีการแบ่งส่วน 396 00:17:40,480 --> 00:17:43,150 เพราะคุณกำลังวิ่ง ออกจากขอบเขตของอาร์เรย์ของคุณ 397 00:17:43,150 --> 00:17:46,510 ในตัวอย่างของซีซาร์ที่ สิ่งที่ผมได้ดำเนินการที่นี่ 398 00:17:46,510 --> 00:17:50,060 >> ดังนั้นฉันลืมที่จะตรวจสอบ อะไรจะเกิดขึ้นถ้าฉัน 399 00:17:50,060 --> 00:17:52,510 ไม่ได้มีสองอาร์กิวเมนต์บรรทัดคำสั่ง 400 00:17:52,510 --> 00:17:53,880 ฉันก็ไม่ได้ใส่ในการตรวจสอบว่า 401 00:17:53,880 --> 00:17:57,380 และดังนั้นถ้าผมทำงาน Debug-- ผมตั้ง เบรกพอยต์ของฉันไปที่นั่น 402 00:17:57,380 --> 00:17:58,055 ผมทำงานการแก้ปัญหา 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> ตกลง. 405 00:18:16,550 --> 00:18:17,050 ใช่ 406 00:18:17,050 --> 00:18:20,350 ดังนั้นจริง GDB ควร จะได้บอกมี 407 00:18:20,350 --> 00:18:22,300 เป็นความผิดส่วนที่มี 408 00:18:22,300 --> 00:18:24,883 ผมไม่ทราบว่าสิ่งที่เกิดขึ้น ที่นั่น แต่เมื่อฉันวิ่งมัน 409 00:18:24,883 --> 00:18:25,590 มันก็ทำงาน 410 00:18:25,590 --> 00:18:29,410 เมื่อคุณเรียกใช้บรรทัดของรหัสผ่านและ GDB เพียงพริบอาจจะเลิกกับคุณ 411 00:18:29,410 --> 00:18:31,540 ขึ้นไปและมองสิ่งที่เกิดข้อผิดพลาดสีแดง 412 00:18:31,540 --> 00:18:33,930 มันจะบอกคุณเดี๋ยวก่อนคุณ มีความผิดส่วนหนึ่ง 413 00:18:33,930 --> 00:18:38,550 ซึ่งหมายความว่าคุณพยายามที่จะเข้าถึง พื้นที่ในอาร์เรย์ที่ไม่อยู่ 414 00:18:38,550 --> 00:18:39,050 ใช่ 415 00:18:39,050 --> 00:18:43,280 >> ดังนั้นในปัญหาที่เกิดขึ้นต่อไป การตั้งค่าในสัปดาห์นี้พวกคุณ 416 00:18:43,280 --> 00:18:45,600 อาจจะมีจำนวนมาก ตัวแปรลอยรอบ 417 00:18:45,600 --> 00:18:48,560 คุณจะไม่แน่ใจว่าสิ่งที่ พวกเขาทั้งหมดหมายถึงที่จุดหนึ่ง 418 00:18:48,560 --> 00:18:53,560 ดังนั้น GDB จริงๆจะช่วยคุณในการหา สิ่งที่พวกเขาทั้งหมดเท่ากับ 419 00:18:53,560 --> 00:18:55,940 และความสามารถที่จะเห็นว่าสายตา 420 00:18:55,940 --> 00:19:01,995 เป็นคนสับสนเกี่ยวกับวิธีการ ใด ๆ ที่ได้รับการทำงาน? 421 00:19:01,995 --> 00:19:02,495 เย็น 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 ทั้งหมดขวา 424 00:19:10,620 --> 00:19:14,260 ดังนั้นหลังจากที่เรามี ไปดำน้ำที่เหมาะสม 425 00:19:14,260 --> 00:19:17,562 เข้าไปในสี่ที่แตกต่างกัน ประเภททุกประเภทสำหรับสัปดาห์นี้ 426 00:19:17,562 --> 00:19:19,520 วิธีการหลายท่านแรก ของทั้งหมดก่อนที่เราจะเริ่มต้น 427 00:19:19,520 --> 00:19:23,020 ได้อ่านข้อมูลจำเพาะทั้งหมดสำหรับ pset3? 428 00:19:23,020 --> 00:19:23,824 ตกลง. 429 00:19:23,824 --> 00:19:24,740 ฉันภูมิใจในตัวพวกคุณ 430 00:19:24,740 --> 00:19:29,110 นั่นเป็นเหมือนครึ่งหนึ่งของชั้นเรียนซึ่ง อย่างมีนัยสำคัญมากกว่าครั้งที่แล้ว 431 00:19:29,110 --> 00:19:33,950 >> ดังนั้นที่ดีเพราะเมื่อ เราพูดคุยเกี่ยวกับเนื้อหา 432 00:19:33,950 --> 00:19:36,170 ใน lecture-- หรือขอโทษ ใน section-- ผมชอบ 433 00:19:36,170 --> 00:19:38,210 ที่จะเกี่ยวข้องกับจำนวนมากว่า กลับไปที่สิ่ง pset เป็น 434 00:19:38,210 --> 00:19:40,210 และวิธีที่คุณต้องการ การดำเนินการว่าใน pset ของคุณ 435 00:19:40,210 --> 00:19:42,400 ดังนั้นถ้าคุณมีมา อ่านข้อมูลจำเพาะก็จะ 436 00:19:42,400 --> 00:19:45,510 จะง่ายขึ้นมากสำหรับคุณที่จะเข้าใจ สิ่งที่ผมพูดเกี่ยวกับเมื่อฉันพูดว่า 437 00:19:45,510 --> 00:19:48,720 โอ้เดี๋ยวก่อนนี้อาจจะมีจริงๆ สถานที่ที่ดีในการดำเนินการจัดเรียงนี้ 438 00:19:48,720 --> 00:19:52,870 ดังนั้นบรรดาผู้ที่ได้อ่าน spec รู้ว่าเป็นส่วนหนึ่งของ pset ของคุณ 439 00:19:52,870 --> 00:19:54,900 คุณจะต้อง เขียนประเภทของการจัดเรียง 440 00:19:54,900 --> 00:19:58,670 ดังนั้นนี่อาจจะเป็นประโยชน์มาก สำหรับจำนวนมากของคุณในวันนี้ 441 00:19:58,670 --> 00:20:01,760 >> ดังนั้นเราจะเริ่มต้นด้วย เป็นหลักชนิดที่ง่ายที่สุด 442 00:20:01,760 --> 00:20:04,580 การเรียงลำดับเรียงลำดับการเลือก 443 00:20:04,580 --> 00:20:06,800 ขั้นตอนวิธีการทั่วไปสำหรับ วิธีการที่เราจะไปเกี่ยวกับเรื่องนี้ 444 00:20:06,800 --> 00:20:10,460 is-- เดวิดเดินผ่านเหล่านี้ทั้งหมดใน การบรรยายเพื่อให้ฉันได้อย่างรวดเร็วจะย้ายไปตาม 445 00:20:10,460 --> 00:20:13,900 here-- เป็นหลักคุณ มีอาร์เรย์ของค่านิยม 446 00:20:13,900 --> 00:20:17,170 แล้วคุณจะพบว่า ค่าไม่ได้เรียงลำดับที่เล็กที่สุด 447 00:20:17,170 --> 00:20:20,200 และคุณสลับค่ากับที่ ค่าไม่ได้เรียงลำดับแรก 448 00:20:20,200 --> 00:20:22,700 และแล้วคุณก็เก็บซ้ำ กับส่วนที่เหลือของรายการของคุณ 449 00:20:22,700 --> 00:20:25,740 >> และนี่คือคำอธิบายภาพ ของวิธีการที่จะทำงาน 450 00:20:25,740 --> 00:20:30,460 ดังนั้นตัวอย่างเช่นถ้าเราจะเริ่มต้น กับอาร์เรย์ของห้าองค์ประกอบที่ดัชนี 451 00:20:30,460 --> 00:20:35,910 0-4, 3, 5, 2, 6 และ 4 ค่า วางไว้ใน array-- ดังนั้นในขณะนี้ 452 00:20:35,910 --> 00:20:38,530 เราเพียงแค่จะถือว่า ว่าพวกเขากำลังไม่ได้เรียงลำดับทั้งหมด 453 00:20:38,530 --> 00:20:41,130 เพราะเราไม่ได้ทดสอบอย่างอื่น 454 00:20:41,130 --> 00:20:44,130 >> ดังนั้นวิธีการเรียงลำดับการเลือกจะ การทำงานก็คือว่ามันจะเป็นครั้งแรก 455 00:20:44,130 --> 00:20:46,800 วิ่งผ่านครบถ้วน ของอาเรย์ไม่ได้เรียงลำดับ 456 00:20:46,800 --> 00:20:49,120 มันจะเลือกออกค่าที่เล็กที่สุด 457 00:20:49,120 --> 00:20:51,750 ในกรณีนี้ 3 ขวา ตอนนี้เป็นที่เล็กที่สุด 458 00:20:51,750 --> 00:20:52,680 จะได้รับถึง 5 459 00:20:52,680 --> 00:20:55,620 Nope 5 มิได้เป็นใหญ่ than-- หรือเสียใจไม่น้อย than-- 3 460 00:20:55,620 --> 00:20:57,779 ดังนั้นค่าต่ำสุดยังคงเป็นที่ 3 461 00:20:57,779 --> 00:20:58,695 และจากนั้นคุณจะได้รับ 2 462 00:20:58,695 --> 00:21:00,990 คอมพิวเตอร์เห็นโอ้ 2 น้อยกว่า 3 463 00:21:00,990 --> 00:21:02,750 2 ในขณะนี้จะต้องมีค่าต่ำสุด 464 00:21:02,750 --> 00:21:06,630 และเพื่อแลกเปลี่ยนกับ 2 ที่ค่าแรก 465 00:21:06,630 --> 00:21:10,702 >> ดังนั้นหลังจากที่หนึ่งผ่านเราจะเห็นแน่นอน ที่ 2 และ 3 จะสลับ 466 00:21:10,702 --> 00:21:13,910 และเรากำลังจะทำต่อ นี้อีกครั้งกับส่วนที่เหลือของอาร์เรย์ 467 00:21:13,910 --> 00:21:17,660 ดังนั้นเรากำลังจะไปเพียงแค่วิ่งผ่าน ช่วงสี่ดัชนีของอาร์เรย์ 468 00:21:17,660 --> 00:21:20,670 เราจะเห็นว่า 3 ค่าต่ำสุดต่อไป 469 00:21:20,670 --> 00:21:23,240 ดังนั้นเราจึงกำลังจะสลับที่ 4 470 00:21:23,240 --> 00:21:26,900 และจากนั้นเราก็จะเก็บ วิ่งผ่านจนในที่สุดคุณ 471 00:21:26,900 --> 00:21:33,730 ได้รับเป็นแถวเรียงที่ 2, 3, 4, 5, 6 และทั้งหมดเรียง 472 00:21:33,730 --> 00:21:37,530 ทุกคนไม่เข้าใจตรรกะ ของวิธีการจัดเรียงการเลือกทำงานอย่างไร 473 00:21:37,530 --> 00:21:39,669 >> คุณเพียงแค่มีการจัดเรียงบาง ของค่าต่ำสุด 474 00:21:39,669 --> 00:21:41,210 คุณกำลังติดตามว่ามันคืออะไร 475 00:21:41,210 --> 00:21:45,170 และเมื่อใดก็ตามที่คุณพบว่าคุณสลับ มีค่าครั้งแรกใน array-- 476 00:21:45,170 --> 00:21:48,740 หรือไม่ value-- แรก ค่าต่อไปในอาร์เรย์ 477 00:21:48,740 --> 00:21:50,150 เย็น 478 00:21:50,150 --> 00:21:55,460 >> ดังนั้นในขณะที่พวกคุณชนิดของ เห็นจากเหลือบสั้น ๆ 479 00:21:55,460 --> 00:21:58,450 เรากำลังจะ pseudocode นี้ 480 00:21:58,450 --> 00:22:02,510 ดังนั้นถ้าพวกคุณต้องการในด้านหลังไป รูปแบบกลุ่มทุกคนที่โต๊ะ 481 00:22:02,510 --> 00:22:06,170 สามารถสร้างพันธมิตรที่เล็ก ๆ น้อย ๆ ที่ฉันจะ ที่จะให้พวกคุณเหมือนสามนาที 482 00:22:06,170 --> 00:22:08,190 เพียงแค่พูดคุยผ่าน ตรรกะในภาษาอังกฤษ 483 00:22:08,190 --> 00:22:14,161 วิธีการที่เราอาจจะสามารถที่จะดำเนินการ pseudocode ที่จะเขียนเรียงลำดับการเลือก 484 00:22:14,161 --> 00:22:14,910 และมีขนม 485 00:22:14,910 --> 00:22:16,118 กรุณามาขึ้นและได้รับขนม 486 00:22:16,118 --> 00:22:19,520 ถ้าคุณอยู่ในด้านหลังและคุณต้องการ ลูกอมผมสามารถโยนขนมที่คุณ 487 00:22:19,520 --> 00:22:22,850 ที่จริงทำ you-- เย็น 488 00:22:22,850 --> 00:22:23,552 โอ้ขอโทษ. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 ตกลง. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> ดังนั้นถ้าเราต้องการที่จะเป็น ชั้นเขียน pseudocode 493 00:25:27,140 --> 00:25:30,466 สำหรับวิธีการหนึ่งที่จะเข้าใกล้ ปัญหานี้เพียงแค่รู้สึกฟรี 494 00:25:30,466 --> 00:25:32,340 ฉันเพิ่งจะไปรอบ ๆ และ เพื่อขอให้กลุ่ม 495 00:25:32,340 --> 00:25:35,065 สำหรับสายต่อไปของ สิ่งที่เราควรจะทำ 496 00:25:35,065 --> 00:25:37,840 ดังนั้นถ้าพวกคุณต้องการที่จะเริ่มต้น ออกจากสิ่งที่เป็นสิ่งแรก 497 00:25:37,840 --> 00:25:40,600 จะทำอย่างไรเมื่อคุณกำลังพยายามที่จะ ใช้วิธีที่จะแก้โปรแกรมนี้ 498 00:25:40,600 --> 00:25:43,480 การเลือกเรียงลำดับรายชื่อหรือไม่? 499 00:25:43,480 --> 00:25:46,349 ขอเพียงถือว่าเรา มีอาร์เรย์ขวาทั้งหมดหรือไม่ 500 00:25:46,349 --> 00:25:49,088 >> ผู้ชม: คุณต้องการที่จะสร้างบาง การเรียงลำดับของ [ไม่ได้ยิน] ที่คุณ 501 00:25:49,088 --> 00:25:50,420 วิ่งผ่านแถวของคุณทั้งหมด 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: ขวา 503 00:25:51,128 --> 00:25:54,100 ดังนั้นคุณจะต้องการที่จะย้ำ ผ่านทุกพื้นที่ใช่มั้ย? 504 00:25:54,100 --> 00:26:05,490 ดังนั้นที่ดี 505 00:26:05,490 --> 00:26:08,600 ถ้าพวกคุณต้องการที่จะให้ฉัน ต่อไป line-- ใช่ในด้านหลัง 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> ผู้ชม: ตรวจสอบพวกเขา ทั้งหมดที่เล็กที่สุด 508 00:26:13,290 --> 00:26:14,248 >> ANDI PENG: มีที่เราจะไป 509 00:26:14,248 --> 00:26:17,438 ดังนั้นเราจึงต้องการที่จะไปถึงและตรวจสอบ ดูสิ่งที่ค่าต่ำสุดเป็นใช่มั้ย? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 ฉันจะย่อมาที่ "นาที." 512 00:26:24,840 --> 00:26:27,658 สิ่งที่พวกคุณต้องการที่จะทำหลังจากที่ คุณจะพบว่าค่าต่ำสุด? 513 00:26:27,658 --> 00:26:28,533 >> ผู้ชม: [ไม่ได้ยิน] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI PENG: ดังนั้นคุณจะต้องการที่จะ สลับกับครั้งแรกของอาร์เรย์ที่ 516 00:26:33,150 --> 00:26:33,650 ใช่มั้ย? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 นั่นคือจุดเริ่มต้นที่ผมกำลังจะบอกว่า 519 00:26:46,850 --> 00:26:47,220 ทั้งหมดขวา 520 00:26:47,220 --> 00:26:50,386 ดังนั้นขณะนี้ที่คุณสลับแรก หนึ่งในสิ่งที่คุณต้องการที่จะทำหลังจากที่? 521 00:26:50,386 --> 00:26:54,840 ดังนั้นตอนนี้เรารู้ว่าหนึ่งที่นี่ จะต้องเป็นค่าที่น้อยที่สุดใช่มั้ย? 522 00:26:54,840 --> 00:26:58,310 แล้วคุณจะมีส่วนที่เหลือเพิ่มเติม ของอาร์เรย์ที่บ้านทั่วไป 523 00:26:58,310 --> 00:27:01,569 ดังนั้นสิ่งที่คุณต้องการจะทำที่นี่ถ้าคุณ คนต้องการที่จะให้ฉันบรรทัดต่อไปหรือไม่ 524 00:27:01,569 --> 00:27:04,610 ผู้ชม: ดังนั้นแล้วคุณต้องการที่จะย้ำ ที่เหลือของอาร์เรย์ 525 00:27:04,610 --> 00:27:05,276 ANDI เป็ง: ใช่ 526 00:27:05,276 --> 00:27:09,857 และเพื่อให้สิ่งที่ไม่ผ่านการทำซ้ำ บ่งบอกถึงชนิดของเราอาจจะต้อง? 527 00:27:09,857 --> 00:27:10,440 ชนิดของ-- 528 00:27:10,440 --> 00:27:12,057 >> ผู้ชม: โอ้ตัวแปรเพิ่มเติม? 529 00:27:12,057 --> 00:27:13,890 ANDI PENG: น่าจะเป็น สำหรับวงอีกใช่มั้ย? 530 00:27:13,890 --> 00:27:28,914 ดังนั้นเราอาจจะต้องการ ย้ำ through-- ดี 531 00:27:28,914 --> 00:27:31,830 แล้วคุณกำลังจะกลับไปและ อาจจะตรวจสอบขั้นต่ำอีกครั้ง 532 00:27:31,830 --> 00:27:32,100 ใช่มั้ย? 533 00:27:32,100 --> 00:27:34,975 และคุณกำลังจะเก็บซ้ำ นี้เพราะห่วงแค่ไป 534 00:27:34,975 --> 00:27:36,010 เพื่อให้ทำงานใช่มั้ย? 535 00:27:36,010 --> 00:27:39,190 >> ดังนั้นในขณะที่พวกคุณสามารถดูเรา เพียงแค่มี pseudocode ทั่วไป 536 00:27:39,190 --> 00:27:41,480 วิธีการที่เราต้องการให้โปรแกรมนี้จะมอง 537 00:27:41,480 --> 00:27:46,646 ย้ำที่นี่สิ่งที่เราทำ มักจะต้องเขียนในรหัสของเรา 538 00:27:46,646 --> 00:27:49,270 ถ้าเราต้องการที่จะย้ำผ่าน อาร์เรย์สิ่งที่ประเภทของโครงสร้าง? 539 00:27:49,270 --> 00:27:51,030 ผมคิดว่าคริส แล้วกล่าวนี้มาก่อน 540 00:27:51,030 --> 00:27:51,500 >> ผู้ชม: สำหรับวง 541 00:27:51,500 --> 00:27:52,160 >> ANDI เป็ง: เป็นห่วง? 542 00:27:52,160 --> 00:27:52,770 ที่แน่นอน 543 00:27:52,770 --> 00:27:56,060 ดังนั้นนี้อาจเป็น จะเป็นห่วง 544 00:27:56,060 --> 00:27:59,240 ตรวจสอบที่นี่จะบ่งบอกคืออะไร? 545 00:27:59,240 --> 00:28:02,536 โดยปกติแล้วถ้าคุณต้องการที่จะตรวจสอบ ถ้าสิ่งที่เป็นสิ่งที่ else-- 546 00:28:02,536 --> 00:28:03,270 >> ผู้ชม: ถ้า 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: การถ้าใช่มั้ย? 548 00:28:06,790 --> 00:28:10,790 และแล้วการแลกที่นี่เราจะ ไปกว่าในภายหลังเพราะเดวิด 549 00:28:10,790 --> 00:28:12,770 ที่เดินผ่านในการบรรยายได้เป็นอย่างดี 550 00:28:12,770 --> 00:28:14,580 แล้วย้ำสอง implies-- 551 00:28:14,580 --> 00:28:15,120 >> ผู้ชม: อีกสำหรับวง 552 00:28:15,120 --> 00:28:16,745 >> ANDI PENG: --another ห่วงว่า 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 ดังนั้นหากเรากำลังมองหา ที่นี้อย่างถูกต้องเรา 555 00:28:22,000 --> 00:28:24,680 จะเห็นว่าเราอาจจะ จะต้องมีสำหรับวงที่ซ้อนกัน 556 00:28:24,680 --> 00:28:28,330 ที่มีคำสั่งเงื่อนไขในการมี แล้วชิ้นส่วนที่เกิดขึ้นจริงของรหัสที่เป็น 557 00:28:28,330 --> 00:28:31,360 จะสลับค่า 558 00:28:31,360 --> 00:28:35,980 ดังนั้นผมจึงได้เพียงแค่เขียนทั่วไป รหัส pseudocode ที่นี่ 559 00:28:35,980 --> 00:28:38,910 และจากนั้นเรากำลังจะเป็นจริง ร่างกายเป็นชั้นเรียน 560 00:28:38,910 --> 00:28:40,700 พยายามที่จะใช้ในวันนี้ 561 00:28:40,700 --> 00:28:42,486 ลองกลับไปเป็น IDE นี้ 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> เอ่อโอ้. 564 00:28:50,230 --> 00:28:51,754 ทำไมที่ not-- มีเป็น 565 00:28:51,754 --> 00:28:52,253 ตกลง. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 ขออภัยให้ฉันพยายามที่จะขยายอีกเล็กน้อย 568 00:28:57,500 --> 00:28:59,310 เราจะไปที่นั่น. 569 00:28:59,310 --> 00:29:05,060 ทั้งหมดที่ฉันทำที่นี่คือเราได้สร้าง โปรแกรมที่เรียกว่า "การเลือก / sort.c." 570 00:29:05,060 --> 00:29:10,860 เราได้สร้างอาเรย์ของเก้า ค่า, 4, 8, 2, 1, 6, 9, 7, 5, 3 571 00:29:10,860 --> 00:29:14,370 ขณะนี้เท่าที่คุณสามารถ เห็นพวกเขาจะเรียงลำดับ 572 00:29:14,370 --> 00:29:17,880 n จะเป็นหมายเลขที่ บอกคุณจำนวนของค่า 573 00:29:17,880 --> 00:29:18,920 ที่คุณมีในอาร์เรย์ของคุณ 574 00:29:18,920 --> 00:29:20,670 ในกรณีนี้เรามีเก้าค่า 575 00:29:20,670 --> 00:29:23,760 และฉันได้เพียงแค่มีการห่วงที่นี่ ที่พิมพ์ออกมาไม่ได้เรียงลำดับอาร์เรย์ 576 00:29:23,760 --> 00:29:28,370 >> และในตอนท้ายที่ฉันได้ยังมีสำหรับ วงที่เพิ่งพิมพ์มันออกมาอีกครั้ง 577 00:29:28,370 --> 00:29:32,070 ดังนั้นในทางทฤษฎีถ้าโปรแกรมนี้ ทำงานอย่างถูกต้องในตอนท้าย 578 00:29:32,070 --> 00:29:35,670 คุณจะเห็นพิมพ์สำหรับวง ที่ 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 มีทั้งหมดอย่างถูกต้องในการสั่งซื้อ 580 00:29:39,310 --> 00:29:43,410 >> ดังนั้นเราจึงได้มีรหัสจำลองของเราที่นี่ 581 00:29:43,410 --> 00:29:46,090 ไม่มีใครต้องการ to-- ฉันแค่ จะไปขอ volunteers-- 582 00:29:46,090 --> 00:29:49,540 บอกฉันว่าสิ่งที่พิมพ์ถ้า เราต้องการที่จะเป็นครั้งแรกเพียงย้ำ 583 00:29:49,540 --> 00:29:52,840 ผ่านจุดเริ่มต้นของอาร์เรย์นี้หรือไม่? 584 00:29:52,840 --> 00:29:55,204 อะไรบรรทัดของรหัสฉัน อาจจะต้องอยู่ที่นี่? 585 00:29:55,204 --> 00:29:56,990 >> ผู้ชม: [ไม่ได้ยิน] 586 00:29:56,990 --> 00:29:59,010 >> ANDI เป็ง: ใช่รู้สึก ฟรี to-- ขออภัยคุณ 587 00:29:59,010 --> 00:30:02,318 ไม่ต้องยืน up-- รู้สึก อิสระที่จะยกระดับเสียงของคุณสักหน่อย 588 00:30:02,318 --> 00:30:08,190 >> ผู้ชม: สำหรับฉัน int เท่ากับ 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI เป็ง: ใช่ดี 590 00:30:10,690 --> 00:30:15,220 >> ผู้ชม: ฉันเป็นน้อยกว่าความยาวอาร์เรย์ 591 00:30:15,220 --> 00:30:19,630 >> ANDI PENG: ดังนั้นเก็บไว้ใน ใจที่นี่เพราะเรา 592 00:30:19,630 --> 00:30:23,060 ไม่ได้มีฟังก์ชั่นที่ บอกเราความยาวของอาร์เรย์ 593 00:30:23,060 --> 00:30:25,790 ที่เรามีอยู่แล้ว ค่าที่ร้านค้าที่ 594 00:30:25,790 --> 00:30:27,920 ใช่มั้ย? 595 00:30:27,920 --> 00:30:31,010 อีกสิ่งหนึ่งที่จะทำให้ ใน mind-- ในอาร์เรย์ 596 00:30:31,010 --> 00:30:33,940 เก้าค่าสิ่งที่เป็นดัชนี? 597 00:30:33,940 --> 00:30:38,720 ขอเพียงบอกว่าอาร์เรย์นี้คือ 0-3 598 00:30:38,720 --> 00:30:41,500 คุณจะเห็นว่าที่ผ่านมา ดัชนีเป็นจริง 3 599 00:30:41,500 --> 00:30:45,530 มันไม่ได้ 4 แม้ว่าจะมี สี่ค่าในอาร์เรย์ 600 00:30:45,530 --> 00:30:49,866 >> ดังนั้นในที่นี่เราจะต้องระมัดระวังมาก ของสิ่งที่เงื่อนไขของเราสำหรับความยาว 601 00:30:49,866 --> 00:30:50,490 เป็นไปได้ 602 00:30:50,490 --> 00:30:51,948 >> ผู้ชม: มันจะไม่ลบ 1 n? 603 00:30:51,948 --> 00:30:54,440 ANDI เป็ง: มันเป็นไป n ลบ 1 ตรง 604 00:30:54,440 --> 00:30:57,379 ที่ทำให้รู้สึกว่าทำไม มันเป็น n ลบ 1 ทุกคน? 605 00:30:57,379 --> 00:30:58,920 มันเป็นเพราะอาร์เรย์จะเป็นศูนย์การจัดทำดัชนี 606 00:30:58,920 --> 00:31:02,010 พวกเขาเริ่มต้นที่ 0 และวิ่งขึ้นไป n ลบ 1 607 00:31:02,010 --> 00:31:03,210 ใช่มันเป็นบิตหากิน 608 00:31:03,210 --> 00:31:03,730 ตกลง. 609 00:31:03,730 --> 00:31:05,929 และ then-- 610 00:31:05,929 --> 00:31:08,054 ผู้ชม: Isnt'1 ว่า แล้วดูแลว่า 611 00:31:08,054 --> 00:31:11,400 โดยเพียงแค่ไม่ได้บอกว่า "น้อยกว่าหรือ เท่ากับ "และเพียงแค่พูดว่า" น้อยกว่า " 612 00:31:11,400 --> 00:31:13,108 >> ANDI PENG: นั่นเป็น คำถามที่ดีจริงๆ 613 00:31:13,108 --> 00:31:13,630 ดังนั้นใช่ 614 00:31:13,630 --> 00:31:17,410 แต่ก็ยังมีวิธีการที่เรา การดำเนินการที่ถูกต้องตรวจสอบ 615 00:31:17,410 --> 00:31:19,120 คุณจะต้องเปรียบเทียบสองค่า 616 00:31:19,120 --> 00:31:21,009 ดังนั้นคุณจริงต้องการ ปล่อยให้ "เป็น" ที่ว่างเปล่า 617 00:31:21,009 --> 00:31:23,050 เพราะถ้าคุณเปรียบเทียบ คนนี้คุณจะไม่ 618 00:31:23,050 --> 00:31:25,530 มีอะไรหลังจากที่มัน เปรียบเทียบกับใช่มั้ย? 619 00:31:25,530 --> 00:31:27,460 ใช่ 620 00:31:27,460 --> 00:31:29,297 ดังนั้นฉัน ++ 621 00:31:29,297 --> 00:31:30,380 ให้เพิ่มวงเล็บของเราใน 622 00:31:30,380 --> 00:31:30,880 ขออภัย 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 ที่ดี 625 00:31:34,710 --> 00:31:39,117 ดังนั้นเราจึงมีการเริ่มต้น ของวงรอบนอกของเรา 626 00:31:39,117 --> 00:31:41,450 ดังนั้นตอนนี้เราอาจต้องการ สร้างตัวแปรในการรักษา 627 00:31:41,450 --> 00:31:43,085 ติดตามค่าที่น้อยที่สุดใช่มั้ย? 628 00:31:43,085 --> 00:31:45,751 ไม่มีใครต้องการที่จะให้ฉัน บรรทัดของรหัสที่จะทำเช่นนั้น? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 เราต้องทำอย่างไรถ้าเรากำลังจะ ต้องการที่จะเก็บอะไร? 631 00:31:53,570 --> 00:31:55,047 >> ขวา 632 00:31:55,047 --> 00:31:57,630 อาจจะเป็นชื่อที่ดีกว่าสำหรับการที่ จะ be-- "ชั่วคราว" ทั้งหมด works-- 633 00:31:57,630 --> 00:32:00,655 อาจจะเป็นชื่อเหมาะเจาะมากขึ้นจะเป็น ถ้าเราต้องการ value-- ที่เล็กที่สุด 634 00:32:00,655 --> 00:32:01,624 >> ผู้ชม: มิน 635 00:32:01,624 --> 00:32:02,790 ANDI PENG: ต่ำสุดมีที่เราจะไป 636 00:32:02,790 --> 00:32:05,230 นาทีจะดี 637 00:32:05,230 --> 00:32:08,340 ดังนั้นนี่คือสิ่งที่เราทำ ต้องการที่จะเริ่มต้นไปยัง? 638 00:32:08,340 --> 00:32:09,620 นี้เป็นบิตหากิน 639 00:32:09,620 --> 00:32:13,580 เพราะตอนนี้ที่ จุดเริ่มต้นของอาร์เรย์นี้ 640 00:32:13,580 --> 00:32:15,730 คุณยังไม่ได้ดูที่อะไรใช่มั้ย? 641 00:32:15,730 --> 00:32:19,200 ดังนั้นสิ่งที่โดยอัตโนมัติหาก เราเพียงฉันเท่ากับ 0, 642 00:32:19,200 --> 00:32:22,302 ทำในสิ่งที่เราต้องการที่จะเริ่มต้น ค่าต่ำสุดครั้งแรกของเราที่จะ? 643 00:32:22,302 --> 00:32:22,802 ผู้ชม: ฉัน 644 00:32:22,802 --> 00:32:24,790 ANDI เป็ง: ผมว่า 645 00:32:24,790 --> 00:32:27,040 คริสทำไมเราต้องการ ในการเริ่มต้นมันฉัน? 646 00:32:27,040 --> 00:32:28,510 >> ผู้ชม: เพ​​ราะดี เราเริ่มต้นด้วย 0 647 00:32:28,510 --> 00:32:31,660 ดังนั้นเพราะเรามีอะไรที่จะเปรียบเทียบ มันไปต่ำสุดที่จะจบลงด้วยการ 0 648 00:32:31,660 --> 00:32:32,451 >> ANDI PENG: แน่นอน 649 00:32:32,451 --> 00:32:34,400 ดังนั้นเธอจึงตรงขวา 650 00:32:34,400 --> 00:32:36,780 เพราะเรามีไม่จริง มองไปที่สิ่งที่ยัง 651 00:32:36,780 --> 00:32:38,680 เราไม่ทราบว่าสิ่งที่มีค่าต่ำสุดของเราคือ 652 00:32:38,680 --> 00:32:41,960 เราต้องการเพียงแค่เริ่มต้นมัน ฉันซึ่งปัจจุบันเป็นที่นี่ 653 00:32:41,960 --> 00:32:44,750 และในขณะที่เรายังคง ย้ายลงอาร์เรย์นี้ 654 00:32:44,750 --> 00:32:48,122 เราจะเห็นว่าแต่ละ ผ่านเพิ่มเติมทีละฉัน 655 00:32:48,122 --> 00:32:49,830 และเพื่อที่จุดนั้น ฉันอาจจะ 656 00:32:49,830 --> 00:32:52,329 เพื่อต้องการที่จะเป็นขั้นต่ำ เพราะมันจะเป็นอะไรก็ตาม 657 00:32:52,329 --> 00:32:54,520 เป็นจุดเริ่มต้นของอาร์เรย์บ้านทั่วไป 658 00:32:54,520 --> 00:32:55,270 เย็น 659 00:32:55,270 --> 00:32:58,720 >> ดังนั้นตอนนี้เราต้องการเพิ่ม สำหรับวงที่นี่ 660 00:32:58,720 --> 00:33:03,225 จะย้ำผ่าน ไม่ได้เรียงลำดับหรือส่วนที่เหลือของอาร์เรย์นี้ 661 00:33:03,225 --> 00:33:05,808 ไม่มีใครต้องการที่จะให้ฉัน บรรทัดของรหัสที่จะทำเช่นนั้น? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- สิ่งที่เราจะต้องลงที่นี่? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 สิ่งที่เกิดขึ้นไปในวงนี้ได้? 666 00:33:18,820 --> 00:33:19,465 ใช่ 667 00:33:19,465 --> 00:33:21,590 ผู้ชม: ดังนั้นเราจึงต้องการที่จะ มีจำนวนเต็มที่แตกต่างกัน 668 00:33:21,590 --> 00:33:25,080 เพราะเรากำลังวิ่งผ่านส่วนที่เหลือ ของอาร์เรย์แทนฉันจึงอาจ 669 00:33:25,080 --> 00:33:25,760 เจ 670 00:33:25,760 --> 00:33:27,301 >> ANDI เป็ง: ใช่เจเสียงดีกับฉัน 671 00:33:27,301 --> 00:33:27,850 เท่ากับ? 672 00:33:27,850 --> 00:33:33,930 >> ผู้ชม: ดังนั้นฉันจะบวก 1 เพราะ คุณกำลังเริ่มต้นที่ค่าถัดไป 673 00:33:33,930 --> 00:33:40,395 และจากนั้นไปที่ end-- ดังนั้นอีกครั้งญคือ น้อยกว่า n ลบ 1 และจากนั้นเจ ++ 674 00:33:40,395 --> 00:33:41,103 ANDI PENG: Great 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> และจากนั้นในที่นี่เราจะต้องการ เพื่อตรวจสอบเพื่อดูว่าเงื่อนไขของเราจะได้พบกับ 677 00:33:52,750 --> 00:33:53,250 ใช่มั้ย? 678 00:33:53,250 --> 00:33:55,740 เพราะคุณต้องการ เปลี่ยนค่าต่ำสุด 679 00:33:55,740 --> 00:33:58,700 ถ้าหากมันเป็นจริงสิ่งที่มีขนาดเล็กกว่า คุณกำลังเปรียบเทียบกับใช่มั้ย? 680 00:33:58,700 --> 00:34:01,146 ดังนั้นสิ่งที่เราจะต้องการในที่นี่? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 ตรวจสอบดู 683 00:34:04,897 --> 00:34:06,730 ประเภทของคำสั่ง เราอาจจะ 684 00:34:06,730 --> 00:34:08,389 ทิต้องการที่จะใช้ถ้าเรา ต้องการตรวจสอบว่าอะไร? 685 00:34:08,389 --> 00:34:09,360 >> ผู้ชม: ถ้างบ 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: ถ้างบ 687 00:34:10,485 --> 00:34:13,155 ดังนั้น if-- และสิ่งที่เป็นไปได้ เงื่อนไขที่ว่าเราต้องการภายใน 688 00:34:13,155 --> 00:34:13,988 ของคำสั่งถ้าของเราหรือไม่ 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> ผู้ชม: ถ้าค่าของเจ มีค่าน้อยกว่าค่าของ i-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI PENG: แน่นอน 692 00:34:24,600 --> 00:34:27,480 ดังนั้นเพื่อให้ if-- อาร์เรย์นี้จะเรียกว่า "อาเรย์." 693 00:34:27,480 --> 00:34:27,980 ที่ดี 694 00:34:27,980 --> 00:34:30,465 ดังนั้นหาก array-- สิ่งที่เป็นที่? 695 00:34:30,465 --> 00:34:31,090 บอกได้เลยว่าอีกครั้ง 696 00:34:31,090 --> 00:34:39,590 >> ผู้ชม: ถ้าอาร์เรย์ญน้อยกว่า อาร์เรย์ฉันแล้วเราจะเปลี่ยนนาที 697 00:34:39,590 --> 00:34:41,590 ดังนั้นนาทีจะเป็นเจ 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI PENG: ที่ทำให้รู้สึก? 700 00:34:47,249 --> 00:34:48,670 ตกลง. 701 00:34:48,670 --> 00:34:52,929 และตอนนี้ที่นี่เราจริง ต้องการที่จะใช้แลกเปลี่ยนใช่มั้ย? 702 00:34:52,929 --> 00:34:58,285 ดังนั้นจำในการบรรยายที่ดาวิดเมื่อ เขาพยายามที่จะสลับ the-- สิ่งที่เป็น 703 00:34:58,285 --> 00:34:59,996 น้ำส้ม it-- และ milk-- 704 00:34:59,996 --> 00:35:01,150 >> ผู้ชม: นั่นเป็นขั้นต้น 705 00:35:01,150 --> 00:35:02,816 >> ANDI เป็ง: ใช่ว่าเป็นชนิดขั้นต้นของ 706 00:35:02,816 --> 00:35:05,310 แต่มันก็เป็นสิ่งที่ดีงาม แสดงให้เห็นถึงแนวคิดของเวลา 707 00:35:05,310 --> 00:35:08,430 ดังนั้นคิดว่าค่าของคุณที่นี่ 708 00:35:08,430 --> 00:35:10,794 คุณได้มีอาร์เรย์ ของนาที, อาเรย์ของฉันที่ 709 00:35:10,794 --> 00:35:12,460 หรือสิ่งที่เรากำลังพยายามที่จะสลับที่นี่ 710 00:35:12,460 --> 00:35:15,310 และคุณอาจจะไม่สามารถเทลงในพวกเขา แต่ละอื่น ๆ ในเวลาเดียวกันใช่มั้ย? 711 00:35:15,310 --> 00:35:17,180 ดังนั้นสิ่งที่เราจะไป ที่จะต้องสร้างที่นี่ 712 00:35:17,180 --> 00:35:19,126 เพื่อแลกเปลี่ยนกับค่าที่ถูกต้องหรือไม่ 713 00:35:19,126 --> 00:35:19,820 >> ผู้ชม: ตัวแปรชั่วคราว 714 00:35:19,820 --> 00:35:21,370 >> ANDI PENG: ตัวแปรชั่วคราว 715 00:35:21,370 --> 00:35:22,570 เพื่อขอทำอุณหภูมิ int 716 00:35:22,570 --> 00:35:25,681 ดูนี้จะดีกว่า เวลา to-- โอ้โฮสิ่งที่เป็นที่? 717 00:35:25,681 --> 00:35:26,180 ตกลง. 718 00:35:26,180 --> 00:35:29,800 ดังนั้นนี้จะได้รับที่ดีกว่า เวลาที่จะตั้งชื่อตัวแปร "ชั่วคราว". 719 00:35:29,800 --> 00:35:30,730 เพื่อขอทำอุณหภูมิ int 720 00:35:30,730 --> 00:35:32,563 สิ่งที่เราจะไป ตั้งอุณหภูมิเท่ากับที่นี่? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 ผู้ชม: มิน? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI เป็ง: มันเป็นบิตหากิน 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 มันจริงไม่สำคัญว่าในท้ายที่สุด 727 00:35:44,880 --> 00:35:47,690 มันไม่สำคัญว่าสิ่งที่ เพื่อที่คุณเลือกที่จะสลับใน 728 00:35:47,690 --> 00:35:50,862 ตราบใดที่คุณกำลังทำแน่ใจว่าคุณ ติดตามความเคลื่อนไหวของสิ่งที่คุณกำลังการแลกเปลี่ยน 729 00:35:50,862 --> 00:35:52,250 >> ผู้ชม: มันอาจจะเป็นอาร์เรย์ฉัน 730 00:35:52,250 --> 00:35:53,666 >> ANDI เป็ง: ใช่ขอทำอาร์เรย์ฉัน 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 และแล้วสิ่งที่เป็นบรรทัดถัดไป รหัสที่เราต้องการที่จะมีที่นี่? 733 00:35:59,305 --> 00:36:00,680 ผู้ชม: อาร์เรย์ฉันเท่ากับอาร์เรย์ญ 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI PENG: และสุดท้าย? 736 00:36:08,070 --> 00:36:12,070 ผู้ชม: อาร์เรย์ญเท่ากับอาร์เรย์ฉัน 737 00:36:12,070 --> 00:36:14,525 ผู้ชม: หรืออาร์เรย์ญเท่ากับ อาร์เรย์ temp-- หรือชั่วคราว 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI PENG: OK 740 00:36:19,430 --> 00:36:21,510 ดังนั้นเรามาทำงานนี้และดู ถ้ามันจะไปทำงาน 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 ที่สถานที่ที่เกิดขึ้น? 743 00:36:39,335 --> 00:36:40,210 โอ้ว่าปัญหา 744 00:36:40,210 --> 00:36:44,320 ดูในบรรทัด 40 เรา พยายามที่จะใช้อาร์เรย์ญ? 745 00:36:44,320 --> 00:36:47,022 แต่ที่ไม่เพียงเจอยู่มีอะไรบ้าง? 746 00:36:47,022 --> 00:36:48,402 >> ผู้ชม: ในการห่วง 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: ขวา 748 00:36:49,110 --> 00:36:51,730 ดังนั้นสิ่งที่เราจะต้องทำอย่างไร 749 00:36:51,730 --> 00:36:53,170 >> ผู้ชม: กำหนดมันนอก the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 ผู้ชม: ใช่ผมคิดว่าคุณมี ที่จะใช้คำสั่งอื่นถ้าใช่มั้ย? 752 00:37:00,610 --> 00:37:05,230 ดังนั้นเช่นถ้า minimum-- สิ่งที่ถูกต้องให้ฉันคิดว่า 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI PENG: ผู้ชายลอง ที่จะใช้ให้ดูที่ 755 00:37:09,990 --> 00:37:11,270 เห็นสิ่งที่บางสิ่งบางอย่างที่เราสามารถทำได้ที่นี่? 756 00:37:11,270 --> 00:37:11,811 >> ผู้ชม: ตกลง 757 00:37:11,811 --> 00:37:15,900 ดังนั้นหากขั้นต่ำไม่เท่ากับ j-- ดังนั้นหากขั้นต่ำยังคง i-- 758 00:37:15,900 --> 00:37:17,570 แล้วเราจะไม่ต้องสลับ 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI PENG: ไม่เท่ากับที่ฉัน? 761 00:37:24,712 --> 00:37:25,920 อะไรที่คุณอยากจะบอกว่าที่นี่? 762 00:37:25,920 --> 00:37:30,494 >> ผู้ชม: ใช่หรือถ้า ขั้นต่ำไม่เท่ากับฉันใช่ 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI PENG: OK 765 00:37:40,210 --> 00:37:42,040 ดีที่แก้ชนิดของปัญหาของเรา 766 00:37:42,040 --> 00:37:47,265 แต่ที่ยังไม่ได้แก้ ปัญหาของการเกิดอะไรขึ้นถ้า j-- ตั้งแต่เจ 767 00:37:47,265 --> 00:37:49,890 ไม่ได้อยู่ด้านนอกของมันสิ่งที่ คุณจะทำเราต้องการที่จะทำอะไรกับมันได้หรือไม่ 768 00:37:49,890 --> 00:37:50,698 ประกาศมันนอก? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 ลองทำงานนี้ 771 00:38:02,730 --> 00:38:04,435 เอ่อโอ้. 772 00:38:04,435 --> 00:38:06,200 การจัดเรียงของเราไม่ได้ทำงาน 773 00:38:06,200 --> 00:38:10,060 >> ในขณะที่คุณสามารถดูครั้งแรกของเรา อาร์เรย์มีค่าเหล่านั้น 774 00:38:10,060 --> 00:38:14,800 และหลังจากนั้นมันควรจะมี รับใน 1, 2, 3, 4, 5, 6, 7, 8, 9 775 00:38:14,800 --> 00:38:15,530 มันไม่ได้ทำงาน 776 00:38:15,530 --> 00:38:16,030 อ่า 777 00:38:16,030 --> 00:38:17,184 พวกเราทำอะไร? 778 00:38:17,184 --> 00:38:17,850 ผู้ชม: การแก้ปัญหา 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI PENG: สิทธิทั้งหมดที่เราสามารถพยายามที่ 781 00:38:23,370 --> 00:38:25,030 เราสามารถแก้ปัญหา 782 00:38:25,030 --> 00:38:26,042 ซูมออกเล็กน้อย 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 ลองตั้งจุดพักของเรา 785 00:38:33,656 --> 00:38:37,280 Let 's go ตกลง like-- 786 00:38:37,280 --> 00:38:40,444 >> ดังนั้นเพราะเรารู้อยู่แล้วว่า เส้นเหล่านี้ 15 ผ่าน 22 787 00:38:40,444 --> 00:38:43,610 จะ working-- เพราะทั้งหมดที่ฉันทำอยู่ เพียงแค่ทำซ้ำผ่านและ printing-- 788 00:38:43,610 --> 00:38:45,406 ฉันสามารถไปข้างหน้าและข้าม 789 00:38:45,406 --> 00:38:47,280 ขอเริ่มต้นที่เส้น 25 790 00:38:47,280 --> 00:38:48,712 Oop ให้ฉันได้รับการกำจัดที่ 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> ผู้ชม: ดังนั้นเบรกพอยต์ของ ที่จะเริ่มต้นการแก้จุดบกพร่อง? 793 00:38:54,057 --> 00:38:54,890 ANDI PENG: หรือหยุด 794 00:38:54,890 --> 00:38:55,670 ผู้ชม: หรือหยุด 795 00:38:55,670 --> 00:38:55,930 ANDI เป็ง: ใช่ 796 00:38:55,930 --> 00:38:58,640 คุณสามารถตั้งจุดพักหลายและ มันก็สามารถกระโดดจากที่หนึ่งไปยังอีก 797 00:38:58,640 --> 00:39:01,590 แต่ในกรณีนี้เราไม่ทราบว่า ข้อผิดพลาดที่เกิดขึ้น 798 00:39:01,590 --> 00:39:03,780 ดังนั้นเราเพียงต้องการที่จะ เริ่มต้นจากบนลงล่าง 799 00:39:03,780 --> 00:39:05,020 อือ 800 00:39:05,020 --> 00:39:05,550 ตกลง. 801 00:39:05,550 --> 00:39:08,460 >> ดังนั้นที่นี่บรรทัดนี้เราสามารถก้าวเข้ามา 802 00:39:08,460 --> 00:39:11,499 คุณสามารถดูลงที่นี่ เรามีอาร์เรย์ 803 00:39:11,499 --> 00:39:13,290 ผู้ที่มีค่า ที่อยู่ในอาร์เรย์ 804 00:39:13,290 --> 00:39:16,360 คุณจะเห็นว่าวิธีการที่ดัชนี 0 มัน สอดคล้องกับ value-- โอ้, 805 00:39:16,360 --> 00:39:17,526 ฉันจะพยายามที่จะขยาย 806 00:39:17,526 --> 00:39:20,650 ขออภัยมันยากจริงๆ เพื่อ see-- ที่ดัชนีอาร์เรย์ 0, 807 00:39:20,650 --> 00:39:24,090 เรามีค่าของ 4 และ แล้วอื่น ๆ และอื่น ๆ 808 00:39:24,090 --> 00:39:25,670 เรามีตัวแปรท้องถิ่นของเรา 809 00:39:25,670 --> 00:39:28,570 ตอนนี้ฉันจะมีค่าเท่ากับ 0 ซึ่งเราอยากให้มันเป็น 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> ดังนั้นขอให้ก้าวผ่าน 812 00:39:33,690 --> 00:39:36,850 ขั้นต่ำของเราคือเท่ากับ 0 ซึ่งเรายังต้องการให้เป็น 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 และจากนั้นเราใส่ที่สองของเรา ห่วงถ้าอาร์เรย์ญน้อยกว่าอาร์เรย์ฉัน 815 00:39:45,560 --> 00:39:46,380 ซึ่งมันก็ไม่ได้ 816 00:39:46,380 --> 00:39:48,130 ดังนั้นคุณไม่ได้ดูว่า ที่ข้ามผ่านที่? 817 00:39:48,130 --> 00:39:52,430 >> ผู้ชม: ดังนั้นควรถ้า ขั้นต่ำทุก that-- ไม่ควรที่ 818 00:39:52,430 --> 00:39:55,424 อยู่ภายในครั้งแรกสำหรับวง? 819 00:39:55,424 --> 00:39:57,340 ANDI PENG: ไม่มีเพราะ คุณยังคงต้องการที่จะทดสอบ 820 00:39:57,340 --> 00:40:00,329 คุณต้องการที่จะทำทุกเปรียบเทียบ เวลาแม้หลังจากที่คุณเรียกผ่านมัน 821 00:40:00,329 --> 00:40:02,620 คุณไม่เพียงแค่ต้องการที่จะทำ ในวันแรกผ่าน 822 00:40:02,620 --> 00:40:05,240 คุณต้องการที่จะทำมันด้วย ผ่านแต่ละเพิ่มเติมอีกครั้ง 823 00:40:05,240 --> 00:40:07,198 ดังนั้นคุณจึงต้องการที่จะตรวจสอบ สภาพภายในของคุณ 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 ดังนั้นเราจึงกำลังจะ ให้วิ่งผ่านที่นี่ 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 ฉันจะให้พวกคุณคำใบ้ 828 00:40:18,420 --> 00:40:23,910 มันมีจะทำอย่างไรกับความจริงที่ว่าเมื่อ คุณกำลังตรวจสอบเงื่อนไขของคุณ 829 00:40:23,910 --> 00:40:26,600 คุณไม่ได้ตรวจสอบ สำหรับดัชนีที่ถูกต้อง 830 00:40:26,600 --> 00:40:32,510 ดังนั้นตอนนี้คุณกำลังตรวจสอบ ดัชนีอาร์เรย์ของเจน้อยกว่าอาร์เรย์ 831 00:40:32,510 --> 00:40:33,970 ดัชนีของฉัน 832 00:40:33,970 --> 00:40:36,580 แต่สิ่งที่คุณกำลังทำขึ้นที่ จุดเริ่มต้นของห่วงหรือไม่ 833 00:40:36,580 --> 00:40:38,260 คุณไม่ตั้งค่าญเท่ากับฉัน? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> ใช่เพื่อให้เราสามารถจริง ออกจากบั๊กที่นี่ 836 00:40:45,415 --> 00:40:47,040 ดังนั้นลองมาดูที่ pseudocode ของเรา 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- เรากำลังจะไป เริ่มต้นที่ฉันมีค่าเท่ากับ 0 839 00:40:52,580 --> 00:40:54,760 เรากำลังจะไปถึง n ลบ 1 840 00:40:54,760 --> 00:40:58,040 ขอตรวจสอบไม่เรามีสิทธิที่? 841 00:40:58,040 --> 00:40:59,580 อ้างว่าเป็นสิทธิ 842 00:40:59,580 --> 00:41:02,080 >> ดังนั้นแล้วภายในที่นี่เรากำลัง จะสร้างค่าต่ำสุด 843 00:41:02,080 --> 00:41:03,630 และการตั้งค่าที่เท่ากับผม 844 00:41:03,630 --> 00:41:04,950 เราไม่ทำเช่นนั้น? 845 00:41:04,950 --> 00:41:06,270 ครับไม่ว่า 846 00:41:06,270 --> 00:41:10,430 ตอนนี้ในด้านของเราสำหรับวงเรา จะทำเจเท่ากับ i เพื่อ n ลบ 1 847 00:41:10,430 --> 00:41:11,950 เราไม่ทำเช่นนั้น? 848 00:41:11,950 --> 00:41:15,540 อันที่จริงเราไม่ว่า 849 00:41:15,540 --> 00:41:19,922 >> ดังนั้น แต่สิ่งที่เราเปรียบเทียบที่นี่? 850 00:41:19,922 --> 00:41:20,925 >> ผู้ชม: เจบวก 1 851 00:41:20,925 --> 00:41:21,716 ANDI PENG: แน่นอน 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 แล้วคุณจะต้องการที่จะตั้ง ขั้นต่ำเท่ากับเจบวก 1 เช่นกัน 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 ดังนั้นผมจึงเดินผ่านที่ได้อย่างรวดเร็วจริงๆ 856 00:41:32,640 --> 00:41:36,190 พวกคุณไม่เข้าใจ เหตุผลที่มันเป็นเจบวก 1? 857 00:41:36,190 --> 00:41:36,890 ตกลง. 858 00:41:36,890 --> 00:41:40,700 >> ดังนั้นในอาร์เรย์ของคุณใน ผ่านครั้งแรกของคุณผ่าน 859 00:41:40,700 --> 00:41:44,850 สำหรับวงของคุณสำหรับ int ฉันมีค่าเท่ากับ 0 ให้เพียง 860 00:41:44,850 --> 00:41:46,740 สมมตินี้ไม่ได้รับการเปลี่ยนแปลงเลย 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 เรามีอาร์เรย์ของครบถ้วน เพียงธาตุทั้งสี่ไม่ได้เรียงลำดับใช่มั้ย? 863 00:41:56,760 --> 00:42:00,760 ดังนั้นเราจึงต้องการที่จะเริ่มต้นผมเท่ากับ 0 864 00:42:00,760 --> 00:42:03,650 และฉันจะไปเพียง วิ่งผ่านวงนี้ 865 00:42:03,650 --> 00:42:08,560 และเพื่อให้ในครั้งแรกผ่านที่เรากำลังจะ ที่จะเริ่มต้นตัวแปรที่เรียกว่า "นาที" 866 00:42:08,560 --> 00:42:11,245 ที่ยังเท่ากับฉันเพราะ เราไม่ได้มีค่าต่ำสุด 867 00:42:11,245 --> 00:42:12,870 เพื่อให้เป็นปัจจุบันเท่ากับ 0 เช่นกัน 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 และจากนั้นเรากำลังจะผ่านไป 870 00:42:17,640 --> 00:42:19,270 และเราต้องการที่จะย้ำอีกครั้ง 871 00:42:19,270 --> 00:42:22,900 ตอนนี้เราได้พบสิ่งที่ต่ำสุดของเรา คือเราต้องการที่จะย้ำถึง 872 00:42:22,900 --> 00:42:25,190 อีกครั้งเพื่อดูว่ามันเปรียบเทียบใช่มั้ย? 873 00:42:25,190 --> 00:42:40,440 ดังนั้นเจนี่เป็นไป ฉันจะเท่ากันซึ่งเป็น 0 874 00:42:40,440 --> 00:42:46,320 และแล้วถ้าอาเรย์เจบวกฉันซึ่ง เป็นสิ่งหนึ่งที่ต่อไปมากกว่าที่เป็นน้อย 875 00:42:46,320 --> 00:42:49,270 กว่าสิ่งที่ต่ำสุดในปัจจุบันของคุณ ค่าที่คุณต้องการที่จะแลกเปลี่ยน 876 00:42:49,270 --> 00:42:56,850 >> ถ้าอย่างนั้นเราก็บอกว่าเราได้ ได้เช่น 2, 5, 1, 8 877 00:42:56,850 --> 00:43:01,610 ตอนนี้ฉันจะมีค่าเท่ากับ 0 และเจมีค่าเท่ากับ 0 878 00:43:01,610 --> 00:43:05,210 และนั่นคือค่าต่ำสุดของเรา 879 00:43:05,210 --> 00:43:09,950 ถ้าอาร์เรย์เจบวก i-- ดังนั้นถ้าหนึ่ง นั่นคือหลังจากที่เรากำลังมองหาที่ 880 00:43:09,950 --> 00:43:13,450 มีค่ามากกว่าหนึ่งก่อนที่จะมัน มันจะกลายเป็นขั้นต่ำ 881 00:43:13,450 --> 00:43:18,120 >> ดังนั้นที่นี่เราจะเห็นว่า 5 ไม่น้อยกว่าที่ 882 00:43:18,120 --> 00:43:19,730 ดังนั้นจึงเป็นไปไม่ได้ที่ 5 883 00:43:19,730 --> 00:43:23,580 เราจะเห็นว่า 1 น้อยกว่า 2 ใช่มั้ย? 884 00:43:23,580 --> 00:43:32,970 ดังนั้นตอนนี้เรารู้ว่าขั้นต่ำของเราคือ จะเป็นค่าดัชนีที่ 0, 1, 2 885 00:43:32,970 --> 00:43:34,030 ใช่? 886 00:43:34,030 --> 00:43:39,170 และจากนั้นเมื่อคุณได้รับลงที่นี่ คุณสามารถสลับค่าที่ถูกต้อง 887 00:43:39,170 --> 00:43:42,610 >> ดังนั้นเมื่อพวกคุณเป็นเพียงแค่การมีเจ ก่อนที่คุณไม่ได้มองไปที่หนึ่ง 888 00:43:42,610 --> 00:43:43,260 หลังจากที่มัน 889 00:43:43,260 --> 00:43:44,520 คุณกำลังหาที่ ค่าเดียวกันซึ่ง 890 00:43:44,520 --> 00:43:46,290 คือเหตุผลที่มันก็ไม่ได้ทำอะไร 891 00:43:46,290 --> 00:43:49,721 ไม่ว่าทำให้ความรู้สึกที่ทุกคน เหตุผลที่เราจำเป็นต้องบวก 1 ที่มี? 892 00:43:49,721 --> 00:43:50,220 ตกลง. 893 00:43:50,220 --> 00:43:53,345 ตอนนี้ขอเพียงแค่วิ่งผ่านมันเพื่อให้ แน่ใจว่าส่วนที่เหลือของรหัสที่ถูกต้อง 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 สิ่งที่เกิดขึ้นก็คือว่าทำไม? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 อาจะเป็นนาทีที่นี่ 898 00:44:16,364 --> 00:44:17,780 เราได้เปรียบเทียบค่าที่ไม่ถูกต้อง 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 ไม่นะ. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> อ้อใช่ลงที่นี่เราอยู่ การแลกเปลี่ยนค่าที่ไม่ถูกต้องเช่นกัน 903 00:44:33,482 --> 00:44:34,940 เพราะเรากำลังหาที่ i และ j 904 00:44:34,940 --> 00:44:36,440 เหล่านี้คือคนที่เรากำลังตรวจสอบ 905 00:44:36,440 --> 00:44:39,160 เราจริงต้องการที่จะสลับ ขั้นต่ำขั้นต่ำในปัจจุบัน 906 00:44:39,160 --> 00:44:40,550 กับสิ่งที่หนึ่งนอก 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 และเป็นคนที่คุณสามารถมองเห็นลดลง ที่นี่เรามีอาร์เรย์ที่เรียงลำดับ 909 00:45:05,402 --> 00:45:07,110 มันก็จะทำอย่างไรกับ ความจริงที่ว่าเมื่อ 910 00:45:07,110 --> 00:45:09,350 เราได้รับการตรวจสอบ ค่าที่เรากำลังเปรียบเทียบ 911 00:45:09,350 --> 00:45:11,226 เราไม่ได้มองไปที่ค่าที่เหมาะสม 912 00:45:11,226 --> 00:45:13,850 เรากำลังมองหาที่หนึ่งเดียวกัน ที่นี่ไม่จริงมันแลกเปลี่ยน 913 00:45:13,850 --> 00:45:17,135 คุณต้องมองไปที่หนึ่งต่อไป มันและจากนั้นคุณสามารถสลับ 914 00:45:17,135 --> 00:45:19,260 ดังนั้นสิ่งที่เป็นชนิดของ bugging รหัสของเราก่อน 915 00:45:19,260 --> 00:45:22,460 และสิ่งที่ผมทำที่นี่คือทุกอย่าง ดีบักจะได้ทำเพื่อคุณ 916 00:45:22,460 --> 00:45:23,810 ผมแค่ทำมันใน คณะกรรมการเพราะมันง่ายขึ้น 917 00:45:23,810 --> 00:45:26,320 เพื่อดูมากกว่าการพยายาม เพื่อขยายการดีบัก 918 00:45:26,320 --> 00:45:29,391 ไม่ว่าทำให้ความรู้สึกที่ทุกคน? 919 00:45:29,391 --> 00:45:29,890 เย็น 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> ทั้งหมดขวา 922 00:45:35,410 --> 00:45:41,070 เราสามารถย้ายไปพูดคุยเกี่ยวกับ สัญกรณ์ asymptotic ซึ่ง 923 00:45:41,070 --> 00:45:44,580 เป็นเพียงวิธีที่จินตนาการของคำกล่าวที่ว่า runtimes ทั้งหมดของแปลก ๆ เหล่านี้ 924 00:45:44,580 --> 00:45:47,650 ดังนั้นผมจึงรู้ว่าเดวิดในการบรรยาย สัมผัส runtimes 925 00:45:47,650 --> 00:45:52,124 และเขาก็ผ่านสูตรทั้งหมด ของวิธีการคำนวณ runtimes 926 00:45:52,124 --> 00:45:53,040 ไม่ต้องกังวลเกี่ยวกับการที่ 927 00:45:53,040 --> 00:45:54,660 ถ้าคุณอยากรู้จริงๆ เกี่ยวกับวิธีการที่ทำงาน 928 00:45:54,660 --> 00:45:55,810 อย่าลังเลที่จะพูดคุยกับผมหลังจากที่ส่วน 929 00:45:55,810 --> 00:45:57,560 เราสามารถเดินผ่าน สูตรด้วยกัน 930 00:45:57,560 --> 00:46:00,689 แต่ทั้งหมดที่พวกคุณต้องจริงๆ ทราบว่าเป็นที่ n 2 ยกกำลังสอง 931 00:46:00,689 --> 00:46:01,980 เป็นสิ่งเดียวกับสอง n 932 00:46:01,980 --> 00:46:04,710 เพราะจำนวนที่ใหญ่ที่สุด ตัวแทนที่เติบโตมากที่สุด 933 00:46:04,710 --> 00:46:06,590 และเพื่อให้วัตถุประสงค์ของเรา ทั้งหมดที่เราดูแลเกี่ยวกับ 934 00:46:06,590 --> 00:46:09,470 คือจำนวนยักษ์ที่เติบโต 935 00:46:09,470 --> 00:46:13,340 >> ดังนั้นสิ่งที่เป็นกรณีที่ดีที่สุด รันไทม์ของการจัดเรียงการเลือก? 936 00:46:13,340 --> 00:46:15,830 หากคุณกำลังจะมี ย้ำผ่านรายการ 937 00:46:15,830 --> 00:46:18,712 แล้วย้ำผ่าน ส่วนที่เหลือของรายการที่ 938 00:46:18,712 --> 00:46:20,420 กี่ครั้งที่มี คุณกำลังจะไปอาจจะ 939 00:46:20,420 --> 00:46:24,612 ใน case-- เลวร้ายที่สุดใน ที่ดีที่สุดกรณี sorry-- วิ่งผ่าน? 940 00:46:24,612 --> 00:46:27,070 บางทีคำถามที่ดีกว่าคือ ที่จะขอให้สิ่งที่เป็นกรณีที่เลวร้ายที่สุด 941 00:46:27,070 --> 00:46:28,153 รันไทม์ของการจัดเรียงการเลือก 942 00:46:28,153 --> 00:46:29,366 ผู้ชม: n กำลังสอง 943 00:46:29,366 --> 00:46:30,740 ANDI เป็ง: มัน n ยืดขวา 944 00:46:30,740 --> 00:46:36,986 ดังนั้นวิธีที่ง่ายที่จะคิดว่านี้เป็นเหมือน เวลาที่คุณมีสองซ้อนกันสำหรับลูปใด ๆ 945 00:46:36,986 --> 00:46:38,110 ก็จะได้รับการยกกำลังสอง n 946 00:46:38,110 --> 00:46:40,386 เพราะไม่เพียง แต่ที่คุณ วิ่งผ่านอีกครั้ง 947 00:46:40,386 --> 00:46:42,260 คุณต้องกลับไป ไปรอบ ๆ และวิ่งผ่านมัน 948 00:46:42,260 --> 00:46:44,980 อีกครั้งภายในสำหรับค่าทุก 949 00:46:44,980 --> 00:46:48,640 ดังนั้นในกรณีที่คุณกำลังทำงาน n ครั้ง n สี่เหลี่ยมซึ่ง is-- ขออภัย 950 00:46:48,640 --> 00:46:50,505 n n ครั้งซึ่งเท่ากับกำลังสอง n 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> และนอกจากนี้ยังมีการจัดเรียงบิต ที่ไม่ซ้ำกันในความรู้สึก 953 00:46:56,360 --> 00:46:59,774 ว่ามันไม่สำคัญว่าถ้าเหล่านี้ ค่าที่มีอยู่แล้วในการสั่งซื้อ 954 00:46:59,774 --> 00:47:01,440 มันยังจะวิ่งผ่านนะ 955 00:47:01,440 --> 00:47:03,872 ขอเพียงบอกว่านี้คือ 1, 2, 3, 4 956 00:47:03,872 --> 00:47:07,080 โดยไม่คำนึงถึงหรือไม่ก็อยู่ใน การสั่งซื้อก็ยังจะได้วิ่งผ่าน 957 00:47:07,080 --> 00:47:08,620 และยังคงมีการตรวจสอบค่าต่ำสุด 958 00:47:08,620 --> 00:47:10,100 มันจะได้ทำ หมายเลขเดียวกันของการตรวจสอบ 959 00:47:10,100 --> 00:47:12,780 ทุกครั้งเดียวถึงแม้ว่ามันจะ ไม่ได้จริงสัมผัสอะไร 960 00:47:12,780 --> 00:47:16,940 >> ดังนั้นในกรณีดังกล่าวที่ดีที่สุดและเลวร้ายที่สุด runtimes เป็นจริงเทียบเท่า 961 00:47:16,940 --> 00:47:19,160 ดังนั้นคาดว่าการใช้งานจริง ของการจัดเรียงการเลือก 962 00:47:19,160 --> 00:47:23,790 ซึ่งเรากำหนดโดยสัญลักษณ์ ของทีทีในกรณีนี้ 963 00:47:23,790 --> 00:47:24,790 นอกจากนี้ยังจะได้รับการยกกำลังสอง n 964 00:47:24,790 --> 00:47:26,480 ทั้งสามเหล่านี้จะได้รับการยกกำลังสอง n 965 00:47:26,480 --> 00:47:29,653 คือทุกคนที่ชัดเจนว่าทำไม รันไทม์เป็นสี่เหลี่ยม n? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> ทั้งหมดขวา 968 00:47:33,980 --> 00:47:39,120 ดังนั้นฉันก็จะทำงานได้อย่างรวดเร็ว ผ่านส่วนที่เหลือของแปลกที่ 969 00:47:39,120 --> 00:47:41,137 อัลกอริทึมสำหรับ ฟอง sort-- จำ 970 00:47:41,137 --> 00:47:43,220 นี่เป็นครั้งแรกหนึ่ง ดาวิดก็ข้ามในการบรรยาย 971 00:47:43,220 --> 00:47:46,000 โดยพื้นฐานแล้วคุณก้าว ผ่านรายการทั้งหมด 972 00:47:46,000 --> 00:47:48,950 และคุณ swap-- คุณเพียงแค่ เปรียบเทียบสองในเวลา 973 00:47:48,950 --> 00:47:51,350 และหากเป็นมากขึ้น กว่าที่คุณเพียงแค่สลับพวกเขา 974 00:47:51,350 --> 00:47:53,590 ดังนั้นหากเหล่านี้มีมากขึ้นคุณจะสลับ 975 00:47:53,590 --> 00:47:56,180 ฉันมีอย่างเป็นทางการที่นี่ 976 00:47:56,180 --> 00:47:59,100 >> เพื่อให้เพียงว่าคุณมี 8, 6, 4, 2 977 00:47:59,100 --> 00:48:00,571 คุณต้องการเปรียบเทียบ 8 และ 6 978 00:48:00,571 --> 00:48:01,570 คุณจะต้องสลับพวกเขา 979 00:48:01,570 --> 00:48:02,610 คุณจะเปรียบเทียบ 8 และ 4 980 00:48:02,610 --> 00:48:03,609 คุณจะต้องสลับพวกเขา 981 00:48:03,609 --> 00:48:07,000 หากคุณมีการสลับ 8 และ 2, เปลี่ยนพวกเขาเช่นกัน 982 00:48:07,000 --> 00:48:10,760 ดังนั้นในความรู้สึกเช่นนี้คุณสามารถดู เล่นออกมาเป็นระยะเวลานานของเวลา 983 00:48:10,760 --> 00:48:13,730 วิธีการที่ค่าชนิดของฟอง ปลายซึ่งเป็นเหตุผลที่เราเรียกว่า 984 00:48:13,730 --> 00:48:15,320 การจัดเรียงฟอง 985 00:48:15,320 --> 00:48:19,950 >> เราก็จะวิ่งผ่านอีกครั้งบน ผ่านที่สองของเราและผ่านที่สามของเรา 986 00:48:19,950 --> 00:48:21,150 และผ่านสี่ของเรา 987 00:48:21,150 --> 00:48:25,820 โดยพื้นฐานแล้วการจัดเรียงฟองเพียงแค่ทำงาน จนกว่าคุณจะไม่ได้ทำสัญญาแลกเปลี่ยนใด ๆ เพิ่มเติม 988 00:48:25,820 --> 00:48:31,109 ดังนั้นในแง่ที่ว่านี้เป็นเพียง pseudocode ทั่วไปของมัน 989 00:48:31,109 --> 00:48:32,650 ไม่ต้องกังวลเหล่านี้ทั้งหมดจะออนไลน์ 990 00:48:32,650 --> 00:48:34,990 เราไม่ได้มีจริงไปกว่านี้ 991 00:48:34,990 --> 00:48:38,134 >> เราเพียงแค่เริ่มต้นเคาน์เตอร์ ตัวแปรที่เริ่มต้นที่ 0 992 00:48:38,134 --> 00:48:39,800 และเราย้ำผ่านอาร์เรย์ทั้งหมด 993 00:48:39,800 --> 00:48:43,420 และหากค่า is-- ว่านี้ ค่ามากกว่าค่าที่ 994 00:48:43,420 --> 00:48:44,610 คุณกำลังจะแลกเปลี่ยนพวกเขา 995 00:48:44,610 --> 00:48:46,860 และจากนั้นคุณเพียงแค่ จะให้ไป 996 00:48:46,860 --> 00:48:47,970 และคุณกำลังจะนับ 997 00:48:47,970 --> 00:48:50,845 และคุณกำลังจะให้ทำ ขณะนี้นับเป็นมากขึ้น 998 00:48:50,845 --> 00:48:53,345 กว่า 0 ซึ่งหมายความว่า เวลาที่คุณต้องสลับทุก 999 00:48:53,345 --> 00:48:55,220 คุณรู้ว่าคุณต้องการที่จะไป กลับมาและตรวจสอบอีกครั้ง 1000 00:48:55,220 --> 00:48:59,510 คุณต้องการที่จะให้การตรวจสอบจนกว่าคุณจะรู้ ที่คุณไม่ต้องสลับอีกต่อไป 1001 00:48:59,510 --> 00:49:05,570 >> ดังนั้นสิ่งที่ดีที่สุดและเลวร้ายที่สุด กรณี runtimes สำหรับการจัดเรียงฟอง? 1002 00:49:05,570 --> 00:49:09,300 และ hint-- นี้เป็นจริงที่แตกต่างกัน จากการเรียงลำดับการเลือกในความรู้สึก 1003 00:49:09,300 --> 00:49:11,810 ว่าทั้งสองคำตอบที่ไม่เหมือนกัน 1004 00:49:11,810 --> 00:49:14,709 คิดเกี่ยวกับสิ่งที่จะเกิดขึ้นใน กรณีหากมีการเรียงแล้ว 1005 00:49:14,709 --> 00:49:16,500 และคิดเกี่ยวกับสิ่ง ที่จะเกิดขึ้นถ้ามันเป็น 1006 00:49:16,500 --> 00:49:18,372 ในกรณีที่มันไม่ได้เรียง 1007 00:49:18,372 --> 00:49:20,580 และชนิดของคุณสามารถทำงานได้ ผ่านเหตุผลที่เกิดขึ้น 1008 00:49:20,580 --> 00:49:22,954 ฉันจะให้พวกคุณเหมือน 30 วินาทีที่จะคิดเกี่ยวกับเรื่องนั้น 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> ตกลง. 1011 00:49:53,540 --> 00:49:57,462 ทุกคนมีการคาดเดาในสิ่งที่เป็น รันไทม์กรณีที่เลวร้ายของการจัดเรียงฟองคืออะไร? 1012 00:49:57,462 --> 00:49:57,962 ใช่ 1013 00:49:57,962 --> 00:50:07,810 >> ผู้ชม: มันจะเป็นเช่น n ครั้ง n ลบ 1 หรือสิ่งที่ต้องการนั้น 1014 00:50:07,810 --> 00:50:10,650 เช่นเดียวกับทุกครั้งที่มันวิ่ง มันเป็นเพียงเช่นหนึ่งแลกเปลี่ยนน้อย 1015 00:50:10,650 --> 00:50:10,960 ว่าสิ่งที่มันเป็น 1016 00:50:10,960 --> 00:50:12,668 >> ANDI เป็ง: ใช่ดังนั้น คุณขวาทั้งหมด 1017 00:50:12,668 --> 00:50:15,940 และนี่คือกรณีที่ของคุณ คำตอบที่เป็นจริงที่ซับซ้อนมากขึ้น 1018 00:50:15,940 --> 00:50:17,240 มากกว่าหนึ่งที่เราต้องการที่จะให้ 1019 00:50:17,240 --> 00:50:19,772 ดังนั้นมันจะ run-- ฉัน จะลบทั้งหมดนี้ที่นี่ 1020 00:50:19,772 --> 00:50:20,480 ทุกคนที่ดีคืออะไร? 1021 00:50:20,480 --> 00:50:21,869 ฉันสามารถลบนี้หรือไม่? 1022 00:50:21,869 --> 00:50:22,368 ตกลง. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 คุณกำลังจะวิ่งผ่าน n ครั้งนี้เป็นครั้งแรกใช่มั้ย? 1025 00:50:30,320 --> 00:50:33,200 และพวกเขากำลังจะวิ่งผ่าน n ลบ 1 ครั้งที่สองใช่มั้ย? 1026 00:50:33,200 --> 00:50:37,130 แล้วคุณกำลังจะเก็บ ไป n เหมือง 2 ฯลฯ 1027 00:50:37,130 --> 00:50:40,210 เดวิดทำอย่างนี้ในการบรรยายที่ไหน ถ้าคุณเพิ่มค่าเหล่านั้นทั้งหมด 1028 00:50:40,210 --> 00:50:48,080 คุณจะได้รับสิ่งที่ like-- yeah-- มากกว่า 2 ซึ่งหลักเพียงช่วยลด 1029 00:50:48,080 --> 00:50:49,784 ลงไป n ยืด 1030 00:50:49,784 --> 00:50:51,700 คุณจะได้รับ ส่วนที่แปลกในการมี 1031 00:50:51,700 --> 00:50:53,892 และอื่น ๆ เพิ่งรู้ว่า n ที่สองเสมอ 1032 00:50:53,892 --> 00:50:55,350 จะเหนือกว่าส่วน 1033 00:50:55,350 --> 00:50:58,450 และในกรณีนี้ที่เลวร้ายที่สุด รันไทม์จะได้รับการยกกำลังสอง n 1034 00:50:58,450 --> 00:51:00,210 ถ้ามันมากไปน้อย เพื่อคิดคุณ 1035 00:51:00,210 --> 00:51:02,530 ต้องให้แลกทุกครั้งเดียว 1036 00:51:02,530 --> 00:51:05,170 >> สิ่งที่จะเป็นไปได้ที่อาจเกิดขึ้น รันไทม์กรณีที่ดีที่สุด? 1037 00:51:05,170 --> 00:51:08,580 ขอเพียงบอกว่าถ้ารายการที่มีอยู่แล้ว ในการสั่งซื้อสิ่งที่รันไทม์จะเป็นอย่างไร 1038 00:51:08,580 --> 00:51:09,565 >> ผู้ชม: n 1039 00:51:09,565 --> 00:51:10,690 ANDI เป็ง: มันเป็น n ตรง 1040 00:51:10,690 --> 00:51:11,600 และทำไมมัน n? 1041 00:51:11,600 --> 00:51:13,850 ผู้ชม: เพ​​ราะคุณเพียงแค่ มีการตรวจสอบในแต่ละครั้งเดียว 1042 00:51:13,850 --> 00:51:14,770 ANDI PENG: แน่นอน 1043 00:51:14,770 --> 00:51:17,150 ดังนั้นในการทำงานที่ดีที่สุด, ถ้ารายการนี​​้อยู่แล้ว 1044 00:51:17,150 --> 00:51:20,270 sorted-- สมมติว่า 1, 2, 3, 4-- คุณ ก็จะผ่านไปคุณจะตรวจสอบ 1045 00:51:20,270 --> 00:51:21,720 คุณจะเห็นโอ้พวกเขาทั้งหมดเลื่อนออกไป 1046 00:51:21,720 --> 00:51:22,636 ฉันไม่ได้มีการแลกเปลี่ยน 1047 00:51:22,636 --> 00:51:23,370 ฉันทำ 1048 00:51:23,370 --> 00:51:26,500 ดังนั้นในกรณีที่มันเป็นเพียงแค่ n หรือจำนวนของขั้นตอนที่คุณเพียง 1049 00:51:26,500 --> 00:51:29,870 มีการตรวจสอบในรายการแรก 1050 00:51:29,870 --> 00:51:33,990 >> และหลังจากที่ตอนนี้เราตี จัดเรียงแทรกที่ 1051 00:51:33,990 --> 00:51:39,260 อัลกอริทึมที่เป็นหลักในการแบ่ง มันกลายเป็นส่วนหนึ่งและไม่ได้เรียงลำดับเรียงลำดับ 1052 00:51:39,260 --> 00:51:42,810 และจากนั้นหนึ่งโดยหนึ่ง ค่าไม่ได้เรียงลำดับเป็น 1053 00:51:42,810 --> 00:51:46,880 แทรกอยู่ในที่เหมาะสมของพวกเขา ตำแหน่งในจุดเริ่มต้นของรายการ 1054 00:51:46,880 --> 00:51:52,120 >> ดังนั้นสำหรับตัวอย่างเช่นเรามี รายชื่อของ 3, 5, 2, 6, 4 อีกครั้ง 1055 00:51:52,120 --> 00:51:54,750 เรารู้ว่ามันเป็นอยู่ในปัจจุบัน เพราะเราไม่ได้เรียงลำดับได้เพียงแค่ 1056 00:51:54,750 --> 00:51:57,030 เริ่มมองไปที่มัน 1057 00:51:57,030 --> 00:52:00,610 เรามาดูและเรารู้ว่า ค่าแรกจะถูกจัดเรียงใช่มั้ย? 1058 00:52:00,610 --> 00:52:04,190 หากคุณกำลังมองหาที่เพียงอาร์เรย์ของ ขนาดหนึ่งคุณรู้ว่ามันเรียง 1059 00:52:04,190 --> 00:52:08,230 >> ดังนั้นแล้วเรารู้ว่า อีกสี่คนอยู่ไม่ได้เรียงลำดับ 1060 00:52:08,230 --> 00:52:10,980 เราผ่านไปและเราจะเห็นค่าที่ 1061 00:52:10,980 --> 00:52:11,730 กลับกันเถอะ. 1062 00:52:11,730 --> 00:52:13,130 เห็นคุณค่าของ 5 ที่? 1063 00:52:13,130 --> 00:52:14,110 เราจะดูที่มัน 1064 00:52:14,110 --> 00:52:15,204 เราเปรียบเทียบกับ 3 1065 00:52:15,204 --> 00:52:17,870 เรารู้ว่ามันเป็นมากกว่า 3 ดังนั้นเราจึงรู้ว่าที่เรียง 1066 00:52:17,870 --> 00:52:22,940 ดังนั้นตอนนี้เรารู้ว่าสองคนแรก เรียงลำดับและในช่วงสามไม่ได้ 1067 00:52:22,940 --> 00:52:24,270 >> เราจะดูที่ 2 1068 00:52:24,270 --> 00:52:25,720 ครั้งแรกที่เราตรวจสอบ 5 1069 00:52:25,720 --> 00:52:26,700 มันมีค่าน้อยกว่า 5? 1070 00:52:26,700 --> 00:52:27,240 มันไม่ได้เป็น. 1071 00:52:27,240 --> 00:52:29,510 ดังนั้นเราจึงมีเพื่อให้มองลงมา 1072 00:52:29,510 --> 00:52:30,940 จากนั้นให้คุณตรวจสอบออก 2 3 1073 00:52:30,940 --> 00:52:31,850 มันมีค่าน้อยกว่า? 1074 00:52:31,850 --> 00:52:32,350 เลขที่ 1075 00:52:32,350 --> 00:52:35,430 เพื่อให้คุณทราบ 2 จะต้องมีการแทรก เข้าด้านหน้าและ 3 และ 5 1076 00:52:35,430 --> 00:52:38,200 ทั้งจะต้องมีการผลักดันออก 1077 00:52:38,200 --> 00:52:42,190 ทำเช่นนี้อีกครั้งกับ 6 และ 4 1078 00:52:42,190 --> 00:52:48,962 และเราก็ให้ตรวจสอบเป็นหลัก ที่เราเพียงแค่ตรวจสอบตรวจสอบตรวจสอบ 1079 00:52:48,962 --> 00:52:51,170 และจนกว่ามันอยู่ในที่ที่เหมาะสม ตำแหน่งเราเพียงแค่ชนิดของ 1080 00:52:51,170 --> 00:52:54,890 ใส่ลงในตำแหน่งที่เหมาะสม ซึ่งเป็นที่ที่ชื่อของมันมาจาก 1081 00:52:54,890 --> 00:52:59,830 >> ดังนั้นนี่เป็นเพียงขั้นตอนวิธี pseudocode ต่อชนิดของ 1082 00:52:59,830 --> 00:53:04,990 ในวิธีที่เราจะใช้ การจัดเรียงแทรก 1083 00:53:04,990 --> 00:53:05,954 pseudocode อยู่ที่นี่ 1084 00:53:05,954 --> 00:53:06,620 มันเป็นออนไลน์ทั้งหมด 1085 00:53:06,620 --> 00:53:10,720 ไม่ต้องกังวลถ้าพวกคุณมี พยายามที่จะคัดลอกลง 1086 00:53:10,720 --> 00:53:14,500 ดังนั้นอีกครั้งคำถามของสิ่งเดียวกัน จะเป็นที่ดีที่สุดและเลวร้ายที่สุด runtimes 1087 00:53:14,500 --> 00:53:16,120 สำหรับการจัดเรียงแทรก? 1088 00:53:16,120 --> 00:53:17,750 มันคล้ายกันมากกับคำถามที่ผ่านมา 1089 00:53:17,750 --> 00:53:20,479 ฉันจะให้พวกคุณเหมือน 30 วินาทีที่จะคิดเกี่ยวกับเรื่องนี้เป็นอย่างดี 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> ตกลงไม่มีใครต้องการ ให้ฉันรันไทม์ที่เลวร้ายที่สุด? 1092 00:53:50,071 --> 00:53:50,570 ใช่ 1093 00:53:50,570 --> 00:53:51,490 >> ผู้ชม: n กำลังสอง 1094 00:53:51,490 --> 00:53:52,573 >> ANDI เป็ง: มันยกกำลัง n 1095 00:53:52,573 --> 00:53:53,730 และทำไมมันยืด n? 1096 00:53:53,730 --> 00:53:57,562 >> ผู้ชม: เพ​​ราะใน เพื่อกลับคุณมี 1097 00:53:57,562 --> 00:54:02,619 ที่จะไปผ่านช่วงเวลาที่ n n ซึ่ง is-- 1098 00:54:02,619 --> 00:54:03,660 ANDI เป็ง: ใช่ว่า 1099 00:54:03,660 --> 00:54:06,610 สิ่งเดียวกันดังนั้นในขณะที่ในการเรียงลำดับฟอง 1100 00:54:06,610 --> 00:54:08,720 ถ้ารายการนี​​้อยู่ใน ลำดับถัดลงมาคุณ 1101 00:54:08,720 --> 00:54:11,240 จะมีการตรวจสอบครั้งแรกครั้งเดียว 1102 00:54:11,240 --> 00:54:13,470 และแล้วทุก มูลค่าเพิ่มคุณ 1103 00:54:13,470 --> 00:54:16,390 จะมีการตรวจสอบกับ ทุกค่าเดียวใช่มั้ย? 1104 00:54:16,390 --> 00:54:20,290 และอื่น ๆ ทั้งหมดที่คุณกำลังจะทำ ครั้งผ่านอีก n n ผ่านซึ่ง 1105 00:54:20,290 --> 00:54:21,750 มีการยกกำลังสอง n 1106 00:54:21,750 --> 00:54:22,860 สิ่งที่เกี่ยวกับกรณีที่ดีที่สุด? 1107 00:54:22,860 --> 00:54:24,360 ใช่ 1108 00:54:24,360 --> 00:54:28,840 >> ผู้ชม: n ลบ 1 เพราะ คนแรกที่ยกกำลังสองแล้ว 1109 00:54:28,840 --> 00:54:30,270 >> ANDI PENG: ดังนั้นใกล้ 1110 00:54:30,270 --> 00:54:31,850 คำตอบคือจริง n 1111 00:54:31,850 --> 00:54:37,189 เพราะในขณะที่คนแรกคือ เรียงมันอาจจะไม่ actually-- มัน 1112 00:54:37,189 --> 00:54:38,980 เราก็โชคดีใน ตัวอย่างที่ 2 1113 00:54:38,980 --> 00:54:40,930 เกิดขึ้นจะเป็นจำนวนที่น้อยที่สุด 1114 00:54:40,930 --> 00:54:43,680 แต่ที่จะไม่ได้เป็นกรณีที่ 1115 00:54:43,680 --> 00:54:48,040 ถ้า 2 จะถูกจัดเรียงอยู่แล้วในการเริ่มต้น แต่คุณมองและมี 1 ที่นี่ 1116 00:54:48,040 --> 00:54:49,144 1 เป็นไปชนมัน 1117 00:54:49,144 --> 00:54:51,060 และมันก็จะจบ ถูกชนนะ 1118 00:54:51,060 --> 00:54:56,250 >> ดังนั้นในกรณีที่ดีที่สุด มันจริงเพียงจะเป็น n 1119 00:54:56,250 --> 00:54:59,090 หากคุณมี 1, 2, 3, 4, 5, 6, 7, 8, คุณ 1120 00:54:59,090 --> 00:55:00,940 จะวิ่งผ่าน ว่ารายการทั้งหมดในครั้งเดียว 1121 00:55:00,940 --> 00:55:03,430 เพื่อตรวจสอบเพื่อดูว่าดีทุกอย่าง 1122 00:55:03,430 --> 00:55:07,390 คือทุกคนที่ชัดเจนเกี่ยวกับการทำงาน ครั้งของการเลือกเช่นกัน? 1123 00:55:07,390 --> 00:55:09,960 ฉันรู้ว่าฉันจะผ่าน เหล่านี้ได้อย่างรวดเร็วจริงๆ 1124 00:55:09,960 --> 00:55:13,330 เพียง แต่รู้ว่าถ้าคุณรู้ว่า แนวความคิดโดยทั่วไปแล้วคุณควรจะดี 1125 00:55:13,330 --> 00:55:16,070 ตกลง. 1126 00:55:16,070 --> 00:55:19,790 ดังนั้นฉันจะให้พวกคุณอาจจะชอบ นาทีที่จะพูดคุยกับเพื่อนบ้านของคุณ 1127 00:55:19,790 --> 00:55:21,890 ในสิ่งที่เป็นเพียงบางส่วน ความแตกต่างหลัก 1128 00:55:21,890 --> 00:55:23,540 ระหว่างเหล่านี้ประเภทของทุกประเภท 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 เราจะไปกว่าว่าเร็ว ๆ นี้ 1131 00:56:25,570 --> 00:56:26,444 ผู้ชม: โอ้, OK 1132 00:56:26,444 --> 00:56:27,320 ANDI เป็ง: ใช่ 1133 00:56:27,320 --> 00:56:28,380 ตกลง. 1134 00:56:28,380 --> 00:56:33,420 เย็นขอ reconvene เป็นชั้น 1135 00:56:33,420 --> 00:56:34,330 ตกลง. 1136 00:56:34,330 --> 00:56:37,579 ดังนั้นนี้คือชนิดของ คำถามปลายเปิดในความรู้สึก 1137 00:56:37,579 --> 00:56:39,120 ที่มีจำนวนมากของคำตอบให้กับพวกเขา 1138 00:56:39,120 --> 00:56:40,746 และเราจะไปกว่าบางส่วนของพวกเขาในเวลาสั้น ๆ 1139 00:56:40,746 --> 00:56:43,411 ฉันแค่อยากที่จะได้รับพวกคุณ คิดเกี่ยวกับสิ่งที่แตกต่าง 1140 00:56:43,411 --> 00:56:44,530 ทั้งสามประเภทของแปลก 1141 00:56:44,530 --> 00:56:47,440 และข้าพเจ้าได้ยินยังดี คำถามของสิ่งที่จะผสานการเรียงลำดับทำอย่างไร 1142 00:56:47,440 --> 00:56:50,110 คำถามที่ดีเนื่องจากว่าเป็น สิ่งที่เรากำลังครอบคลุมต่อไป 1143 00:56:50,110 --> 00:56:52,850 >> ดังนั้นผสานการจัดเรียงเป็น หนึ่งประเภทที่ฟังก์ชั่น 1144 00:56:52,850 --> 00:56:56,100 แตกต่างกันมากจากประเภทอื่น ๆ 1145 00:56:56,100 --> 00:56:58,180 ในฐานะที่เป็นคนที่คุณสามารถ see-- ไม่เดวิดทำสาธิตว่า 1146 00:56:58,180 --> 00:57:01,130 ซึ่งเขาได้ทุกเย็น เสียงเห็นวิธีการผสาน 1147 00:57:01,130 --> 00:57:04,010 จัดเรียงวิ่งเช่นเพียบ ได้เร็วขึ้นกว่าที่อื่น ๆ สองประเภท? 1148 00:57:04,010 --> 00:57:04,510 ตกลง. 1149 00:57:04,510 --> 00:57:07,580 เพื่อที่ว่าเป็นเพราะผสาน การเรียงลำดับการดำเนินการแบ่งว่า 1150 00:57:07,580 --> 00:57:11,020 และพิชิตแนวคิดที่เราได้ พูดคุยเกี่ยวกับจำนวนมากในการบรรยาย 1151 00:57:11,020 --> 00:57:14,550 ในแง่ที่ว่าเราชอบที่จะทำงานที่ อย่างชาญฉลาดไม่ยากเมื่อคุณแบ่ง 1152 00:57:14,550 --> 00:57:18,120 และพิชิตปัญหาและทำลายพวกเขา ลงแล้วใส่ไว้ด้วยกัน 1153 00:57:18,120 --> 00:57:19,930 สิ่งที่ดีที่เคยเกิดขึ้น 1154 00:57:19,930 --> 00:57:21,960 >> ดังนั้นวิธีการที่ผสาน การเรียงลำดับการทำงานเป็นหลัก 1155 00:57:21,960 --> 00:57:24,660 คือว่ามันแบ่ง อาเรย์ไม่ได้เรียงลำดับในช่วงครึ่งปี 1156 00:57:24,660 --> 00:57:26,500 และแล้วก็มีสองส่วนของอาร์เรย์ 1157 00:57:26,500 --> 00:57:28,220 และมันก็แปลก ๆ ทั้งสองแบ่งเท่า ๆ กัน 1158 00:57:28,220 --> 00:57:31,750 มันก็ช่วยให้การหารในช่วงครึ่งปีใน ครึ่งหนึ่งในช่วงครึ่งปีจนกว่าทุกอย่างจะถูกจัดเรียง 1159 00:57:31,750 --> 00:57:33,680 แล้วซ้ำ ทำให้มันทั้งหมดเข้าด้วยกัน 1160 00:57:33,680 --> 00:57:36,550 >> เพื่อให้เป็นนามธรรมจริงๆ 1161 00:57:36,550 --> 00:57:38,750 ดังนั้นนี้เป็นเพียงเล็กน้อยของรหัสจำลอง 1162 00:57:38,750 --> 00:57:41,040 ที่ทำให้ความรู้สึกในการ วิธีที่จะทำงานหรือไม่ 1163 00:57:41,040 --> 00:57:43,870 ดังนั้นขอเพียงบอกว่าคุณมี อาร์เรย์ขององค์ประกอบ n ใช่มั้ย? 1164 00:57:43,870 --> 00:57:45,450 ถ้า n เป็นน้อยกว่า 2 คุณสามารถกลับ 1165 00:57:45,450 --> 00:57:49,040 เพราะคุณรู้ว่าถ้ามี เพียงสิ่งเดียวที่จะต้องมีการเรียง 1166 00:57:49,040 --> 00:57:52,600 อื่นคุณเรียงลำดับครึ่งซ้าย และจากนั้นคุณเรียงลำดับครึ่งขวา 1167 00:57:52,600 --> 00:57:54,140 แล้วคุณผสาน 1168 00:57:54,140 --> 00:57:56,979 >> ดังนั้นในขณะที่มีลักษณะง่ายจริงๆ ในความเป็นจริงความคิดเกี่ยวกับมัน 1169 00:57:56,979 --> 00:58:00,270 ชนิดของยาก เพราะคุณชอบ ดีที่ชนิดของการทำงานกับตัวเอง 1170 00:58:00,270 --> 00:58:00,769 ใช่มั้ย? 1171 00:58:00,769 --> 00:58:02,430 มันทำงานอยู่ในตัวของมันเอง 1172 00:58:02,430 --> 00:58:05,479 ดังนั้นในแง่ที่ว่าเดวิดสัมผัส เมื่อเรียกซ้ำในชั้นเรียน 1173 00:58:05,479 --> 00:58:07,270 และนั่นคือแนวคิด เราจะพูดถึงมากขึ้น 1174 00:58:07,270 --> 00:58:11,430 มันเป็นเรื่องที่นี้ทั้งสองสาย ที่นี่จริงเป็นเพียงโปรแกรม 1175 00:58:11,430 --> 00:58:13,860 บอกให้เรียกตัวเอง ด้วยการป้อนข้อมูลที่แตกต่างกัน 1176 00:58:13,860 --> 00:58:17,230 ดังนั้นแทนที่จะเรียกตัวเองด้วย ความสมบูรณ์ขององค์ประกอบ n ที่ 1177 00:58:17,230 --> 00:58:20,530 คุณสามารถทำลายมันลงไป ซีกซ้ายและอีกครึ่งหนึ่งที่เหมาะสม 1178 00:58:20,530 --> 00:58:22,680 แล้วเรียกใช้อีกครั้ง 1179 00:58:22,680 --> 00:58:26,050 >> และจากนั้นเราจะดูที่มันสายตา เพราะผมเป็นผู้เรียนมองเห็น 1180 00:58:26,050 --> 00:58:27,270 มันทำงานได้ดีสำหรับฉัน 1181 00:58:27,270 --> 00:58:29,890 ดังนั้นเราจะดูตัวอย่างภาพที่นี่ 1182 00:58:29,890 --> 00:58:36,237 >> สมมติว่าเรามีอาร์เรย์หก องค์ประกอบ, 3, 5, 2, 6, 4, 1, ไม่เรียง 1183 00:58:36,237 --> 00:58:37,820 สิทธิทั้งหมดมีจำนวนมากในหน้านี้ 1184 00:58:37,820 --> 00:58:43,179 ดังนั้นหากพวกคุณสามารถดู ขั้นตอนแรกที่นี่, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 คุณสามารถแบ่งครึ่ง 1186 00:58:44,220 --> 00:58:45,976 คุณมี 3, 5, 2, 6, 4, 1 1187 00:58:45,976 --> 00:58:48,850 คุณจะรู้ว่าสิ่งเหล่านี้ aren't-- คุณ ไม่ทราบว่าพวกเขากำลังเรียงหรือไม่ 1188 00:58:48,850 --> 00:58:52,517 เพื่อให้คุณให้ทำลายพวกเขาลงในช่วงครึ่งปี ในช่วงครึ่งปีในช่วงครึ่งปีจนในที่สุด 1189 00:58:52,517 --> 00:58:53,600 คุณมีเพียงองค์ประกอบหนึ่ง 1190 00:58:53,600 --> 00:58:56,790 และเป็นหนึ่งในองค์ประกอบที่จะถูกจัดเรียงเสมอใช่มั้ย? 1191 00:58:56,790 --> 00:59:01,560 >> ดังนั้นเราจึงรู้ว่า 3, 5, 2, 4, 6, 1, ด้วยตัวเองจะถูกจัดเรียง 1192 00:59:01,560 --> 00:59:05,870 และตอนนี้เราสามารถนำพวกเขากลับมารวมกัน 1193 00:59:05,870 --> 00:59:07,510 ดังนั้นเราจึงรู้ว่า 3, 5 1194 00:59:07,510 --> 00:59:08,510 เราใส่ร่วมกัน 1195 00:59:08,510 --> 00:59:09,617 เรารู้ว่าที่เรียง 1196 00:59:09,617 --> 00:59:10,450 2 ยังคงมี 1197 00:59:10,450 --> 00:59:11,830 เราสามารถใส่ 4 และ 6 ร่วมกัน 1198 00:59:11,830 --> 00:59:13,996 เรารู้ว่าที่เรียงลำดับ ดังนั้นเราจึงนำที่ร่วมกัน 1199 00:59:13,996 --> 00:59:14,940 และจะมี 1 1200 00:59:14,940 --> 00:59:18,720 >> และจากนั้นคุณเพียงแค่มอง ทั้งสองแบ่งเท่า ๆ กันที่นี่ 1201 00:59:18,720 --> 00:59:21,300 คุณมี 3, 5, 2, 2, 3, 5 1202 00:59:21,300 --> 00:59:23,465 คุณก็สามารถเปรียบเทียบ จุดเริ่มต้นของทุกสิ่ง 1203 00:59:23,465 --> 00:59:26,340 เพราะคุณรู้ว่านี้จะถูกจัดเรียง และคุณรู้ว่าที่เรียง 1204 00:59:26,340 --> 00:59:29,360 ดังนั้นแล้วคุณไม่ได้มีการ เปรียบเทียบ 5 คุณเพียงแค่เปรียบเทียบ 3 1205 00:59:29,360 --> 00:59:32,070 และ 2 น้อยกว่า 3 ดังนั้น คุณรู้ว่า 2 จะต้องไปในที่สุด 1206 00:59:32,070 --> 00:59:33,120 >> สิ่งเดียวที่นั่น 1207 00:59:33,120 --> 00:59:34,740 1 ต้องไปที่นี่ 1208 00:59:34,740 --> 00:59:37,330 และจากนั้นเมื่อคุณไปใส่ ทั้งสองค่าด้วยกัน 1209 00:59:37,330 --> 00:59:39,950 คุณรู้ไหมว่านี้จะเรียงลำดับและ คุณรู้ไหมว่าที่เรียง 1210 00:59:39,950 --> 00:59:43,240 ดังนั้นแล้ว 1 และ 2, 1 น้อยกว่า 2 1211 00:59:43,240 --> 00:59:45,570 ที่จะบอกคุณว่า 1 ควรจะไปในส่วนนี้ 1212 00:59:45,570 --> 00:59:47,480 โดยไม่ได้มองไปที่ 3 หรือ 5 1213 00:59:47,480 --> 00:59:50,100 และแล้ว 4 คุณสามารถเพียงแค่ ตรวจสอบที่ถูกต้องมันจะไปที่นี่ 1214 00:59:50,100 --> 00:59:51,480 คุณไม่ต้องไปดูที่ 5 1215 00:59:51,480 --> 00:59:52,570 สิ่งเดียวกันกับ 6 1216 00:59:52,570 --> 00:59:55,860 คุณรู้ไหมว่ามันก็ 6-- ไม่จำเป็นที่จะมอง 1217 00:59:55,860 --> 00:59:57,870 >> ดังนั้นในทางที่คุณ เพียงประหยัดด้วยตัวคุณเอง 1218 00:59:57,870 --> 00:59:59,526 จำนวนมากของขั้นตอนเมื่อคุณกำลังเปรียบเทียบ 1219 00:59:59,526 --> 01:00:02,150 คุณไม่ต้องเปรียบเทียบทุก องค์ประกอบกับองค์ประกอบอื่น ๆ 1220 01:00:02,150 --> 01:00:05,230 คุณเพียงแค่เปรียบเทียบกับคนที่ ที่คุณจะต้องเปรียบเทียบมันกับ 1221 01:00:05,230 --> 01:00:06,870 เพื่อให้เป็นชนิดของแนวคิดนามธรรม 1222 01:00:06,870 --> 01:00:10,540 ไม่ต้องกังวลหากยังไม่ได้ ค่อนข้างตีคุณยังเหมาะสม 1223 01:00:10,540 --> 01:00:14,740 แต่โดยทั่วไปนี้ วิธีการจัดเรียงผสานการทำงาน 1224 01:00:14,740 --> 01:00:17,750 คำถามคำถามอย่างรวดเร็ว ก่อนที่ผมจะย้ายไป? 1225 01:00:17,750 --> 01:00:18,550 ใช่ 1226 01:00:18,550 --> 01:00:22,230 >> ผู้ชม: คุณบอกว่าคุณจะใช้ 1 แล้ว 4 และ 6 1227 01:00:22,230 --> 01:00:23,860 และใส่ไว้ใน 1228 01:00:23,860 --> 01:00:26,800 ดังนั้นไม่ those-- ไม่ได้ คุณกำลังมองไปที่พวกเขา 1229 01:00:26,800 --> 01:00:28,544 เป็นองค์ประกอบที่แยกจากกันไม่ได้โดยรวมหรือไม่ 1230 01:00:28,544 --> 01:00:29,210 ANDI เป็ง: ใช่ 1231 01:00:29,210 --> 01:00:32,020 ดังนั้นสิ่งที่เกิดขึ้น คือการที่คุณพื้น 1232 01:00:32,020 --> 01:00:33,650 กำลังสร้างแบรนด์แถวใหม่ 1233 01:00:33,650 --> 01:00:36,690 เพื่อให้คุณรู้ว่าที่นี่ผมมี สองอาร์เรย์ขนาด 3 ใช่มั้ย? 1234 01:00:36,690 --> 01:00:39,600 เพื่อให้คุณรู้ว่าอาร์เรย์ที่เรียงลำดับของฉัน ต้องมีหกองค์ประกอบ 1235 01:00:39,600 --> 01:00:42,270 ดังนั้นคุณเพียงแค่สร้าง จำนวนเงินใหม่ของหน่วยความจำ 1236 01:00:42,270 --> 01:00:44,270 ดังนั้นคุณชนิดเช่น เป็นสิ้นเปลืองหน่วยความจำ 1237 01:00:44,270 --> 01:00:46,186 แต่ที่ไม่ได้เรื่อง เพราะมันมีขนาดเล็ก 1238 01:00:46,186 --> 01:00:48,590 ดังนั้นคุณจึงมองไปที่ 1 และคุณมองไปที่ 2 1239 01:00:48,590 --> 01:00:50,770 และคุณรู้ว่า 1 น้อยกว่า 2 1240 01:00:50,770 --> 01:00:53,840 เพื่อให้คุณรู้ว่า 1 ควรจะไปใน จุดเริ่มต้นของทุกคน 1241 01:00:53,840 --> 01:00:55,850 >> คุณไม่จำเป็นที่จะต้อง มองไปที่ 3 และ 5 1242 01:00:55,850 --> 01:00:57,400 เพื่อให้คุณทราบ 1 ไปที่นั่น 1243 01:00:57,400 --> 01:00:59,300 โดยทั่วไปแล้วคุณตัด 1 1244 01:00:59,300 --> 01:01:00,370 มันเหมือนตายแล้วให้เรา 1245 01:01:00,370 --> 01:01:03,690 จากนั้นเราก็มี 2 3, 5, และจากนั้น 4 และ 6 1246 01:01:03,690 --> 01:01:06,270 และคุณรู้ว่าคุณ เปรียบเทียบ 4 และ 2 1247 01:01:06,270 --> 01:01:07,560 โอ้ 2 ควรจะไปอยู่ในนั้น 1248 01:01:07,560 --> 01:01:09,685 ดังนั้นคุณป๋อม 2 ลงคุณสับมันออก 1249 01:01:09,685 --> 01:01:12,060 ดังนั้นแล้วคุณก็ต้อง 3 และ 5 ใน 4 และ 6 1250 01:01:12,060 --> 01:01:14,650 และคุณก็ให้ตัดออก จนกว่าคุณจะใส่ไว้ในอาร์เรย์ 1251 01:01:14,650 --> 01:01:17,110 >> ผู้ชม: ดังนั้นคุณเพียงแค่เสมอ เปรียบเทียบ [ไม่ได้ยิน] 1252 01:01:17,110 --> 01:01:17,710 >> ANDI PENG: แน่นอน 1253 01:01:17,710 --> 01:01:19,590 ดังนั้นในแง่ที่ว่าคุณ เพียงแค่การเปรียบเทียบเป็นหลัก 1254 01:01:19,590 --> 01:01:21,240 จำนวนหนึ่งกับจำนวนอื่น ๆ 1255 01:01:21,240 --> 01:01:22,990 และเพราะคุณรู้ว่า ว่ามันเรียงคุณ 1256 01:01:22,990 --> 01:01:24,350 ไม่ต้องมองผ่าน ทั้งหมดของตัวเลข 1257 01:01:24,350 --> 01:01:25,870 คุณเพียงแค่ต้องมองไปที่คนแรก 1258 01:01:25,870 --> 01:01:27,582 และจากนั้นคุณก็สามารถป๋อม พวกเขาลงเพราะคุณรู้ว่า 1259 01:01:27,582 --> 01:01:29,640 พวกเขาอยู่ที่พวกเขาต้องการจะเป็น 1260 01:01:29,640 --> 01:01:31,030 ใช่ 1261 01:01:31,030 --> 01:01:32,920 คำถามที่ดี. 1262 01:01:32,920 --> 01:01:35,290 >> และแล้วถ้าใด ๆ ของคุณ เป็นบิตทะเยอทะยาน, 1263 01:01:35,290 --> 01:01:38,660 อย่าลังเลที่จะมองไปที่รหัสนี้ 1264 01:01:38,660 --> 01:01:40,680 นี้เป็นจริง การดำเนินการทางกายภาพ 1265 01:01:40,680 --> 01:01:42,150 วิธีการที่เราจะเขียนเรียงผสาน 1266 01:01:42,150 --> 01:01:44,070 และคุณสามารถเห็นมันสั้นมาก 1267 01:01:44,070 --> 01:01:46,310 แต่ความคิดที่อยู่เบื้องหลัง มันจะสวยซับซ้อน 1268 01:01:46,310 --> 01:01:50,865 ดังนั้นถ้าคุณรู้สึกว่าการวาดภาพนี้ออกมา ในคืนนี้บ้านของคุณรู้สึกอิสระที่จะ 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> ตกลง. 1271 01:01:54,740 --> 01:01:58,070 ดาวิดจึงยังไปกว่านี้ในการบรรยาย 1272 01:01:58,070 --> 01:02:00,660 อะไรคือกรณีที่ดีที่สุด runtimes ที่เลวร้ายที่สุด runtimes กรณี 1273 01:02:00,660 --> 01:02:05,680 และ runtimes คาดว่าการจัดเรียงผสาน? 1274 01:02:05,680 --> 01:02:07,260 สองสามวินาทีที่จะคิดว่า 1275 01:02:07,260 --> 01:02:11,198 นี้จะสวยยาก แต่ชนิดของ ที่ใช้งานง่ายถ้าคุณคิดเกี่ยวกับมัน 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 ทั้งหมดขวา 1278 01:02:23,054 --> 01:02:25,269 >> ผู้ชม: เป็นกรณีที่เลวร้าย n ล็อก n? 1279 01:02:25,269 --> 01:02:26,060 ANDI PENG: แน่นอน 1280 01:02:26,060 --> 01:02:29,380 และทำไมมัน log n n 1281 01:02:29,380 --> 01:02:32,230 >> ผู้ชม: มันไม่ได้เป็นเพราะ กลายเป็นชี้แจงได้เร็วขึ้น 1282 01:02:32,230 --> 01:02:35,390 ดังนั้นมันก็เหมือนการทำงานของว่า แทนที่จะเป็นเพียงแค่การเป็น n 1283 01:02:35,390 --> 01:02:37,529 สองหรืออะไร? 1284 01:02:37,529 --> 01:02:38,320 ANDI PENG: แน่นอน 1285 01:02:38,320 --> 01:02:40,750 ดังนั้นเหตุผลที่ว่าทำไม runtime ในนี้เข้าสู่ระบบ n 1286 01:02:40,750 --> 01:02:44,310 n คือ because-- สิ่งที่เป็นคุณ ทำในทุกขั้นตอนเหล่านี้หรือไม่ 1287 01:02:44,310 --> 01:02:46,190 คุณเพียงแค่สับมันในช่วงครึ่งปีใช่มั้ย? 1288 01:02:46,190 --> 01:02:48,750 ดังนั้นเมื่อเรากำลังทำ เข้าสู่ระบบทั้งหมดที่มันทำ 1289 01:02:48,750 --> 01:02:53,150 จะแบ่งปัญหาในช่วงครึ่งปี ในช่วงครึ่งปีในช่วงครึ่งปีในส่วนอื่น ๆ 1290 01:02:53,150 --> 01:02:56,430 และในแง่ที่ว่าคุณชนิดสามารถ การขจัดรูปแบบเชิงเส้น 1291 01:02:56,430 --> 01:02:57,510 ที่เราได้ใช้ 1292 01:02:57,510 --> 01:03:00,254 เพราะเมื่อคุณสับ สิ่งที่อยู่ในช่วงครึ่งปีก็เข้าสู่ระบบ 1293 01:03:00,254 --> 01:03:02,420 นั่นเป็นเพียงทางคณิตศาสตร์ วิธีการที่เป็นตัวแทนของมัน 1294 01:03:02,420 --> 01:03:06,310 >> และแล้วในที่สุดในตอนท้ายคุณ เพียงแค่การทำหนึ่งผ่านที่ผ่านมาผ่าน 1295 01:03:06,310 --> 01:03:07,930 ที่จะนำทั้งหมดของพวกเขาในการสั่งซื้อใช่มั้ย? 1296 01:03:07,930 --> 01:03:10,330 และดังนั้นหากคุณเพียงแค่ต้อง ตรวจสอบสิ่งหนึ่งที่ n 1297 01:03:10,330 --> 01:03:13,420 และเพื่อให้คุณชนิดของ คูณทั้งสองร่วมกัน 1298 01:03:13,420 --> 01:03:17,660 ดังนั้นมันก็เหมือนคุณได้มีที่สุดท้าย ตรวจสอบ n ลงที่นี่ด้วยการเข้าสู่ระบบของ n 1299 01:03:17,660 --> 01:03:18,390 ที่นี่ 1300 01:03:18,390 --> 01:03:21,060 และถ้าคุณคูณ พวกเขาที่ log n n 1301 01:03:21,060 --> 01:03:26,100 >> ดังนั้นกรณีที่ดีที่สุดและเลวร้ายที่สุด และกรณีที่คาดว่ามีทั้งหมด n log n 1302 01:03:26,100 --> 01:03:27,943 นอกจากนี้ยังมีอีกเช่นการจัดเรียง 1303 01:03:27,943 --> 01:03:30,090 มันก็เหมือนกับการเลือกการจัดเรียง ในแง่ที่ว่ามัน 1304 01:03:30,090 --> 01:03:32,131 ไม่สำคัญว่าคุณ รายการคือมันเพิ่งจะ 1305 01:03:32,131 --> 01:03:34,801 ที่จะทำในสิ่งเดียวกันทุกครั้งเดียว 1306 01:03:34,801 --> 01:03:35,300 ตกลง. 1307 01:03:35,300 --> 01:03:39,950 ดังนั้นในขณะที่พวกคุณจะได้เห็นถึงแม้ว่า ทุกประเภทที่เราได้ไป through-- n 1308 01:03:39,950 --> 01:03:41,660 ยกกำลังสองก็ไม่ได้มีประสิทธิภาพมาก 1309 01:03:41,660 --> 01:03:47,060 และแม้กระทั่ง n ล็อก n นี้ ไม่ได้มีประสิทธิภาพมากที่สุด 1310 01:03:47,060 --> 01:03:49,720 ถ้าพวกคุณมีความอยากรู้อยากเห็น มีกลไกการจัดเรียง 1311 01:03:49,720 --> 01:03:54,310 ที่มีเพื่อให้มีประสิทธิภาพที่พวกเขากำลัง เกือบเป็นหลักแบนในรันไทม์ 1312 01:03:54,310 --> 01:03:55,420 >> คุณได้มีบางส่วนเข้าสู่ระบบของ n 1313 01:03:55,420 --> 01:03:58,190 คุณได้เข้าสู่ระบบเข้าสู่ระบบบางอย่างของ n 1314 01:03:58,190 --> 01:04:00,330 เราไม่ได้สัมผัสกับพวกเขา ในชั้นนี้ได้ในขณะนี้ 1315 01:04:00,330 --> 01:04:02,663 แต่ถ้าพวกคุณมีความอยากรู้อยากเห็น อย่าลังเลที่จะ google สิ่งที่ 1316 01:04:02,663 --> 01:04:04,392 กลไกการเรียงลำดับมีประสิทธิภาพมากที่สุด 1317 01:04:04,392 --> 01:04:06,350 ผมไม่ทราบว่ามี บางคนที่ตลกจริงๆ 1318 01:04:06,350 --> 01:04:09,860 like-- มีจริงๆบาง คนที่ตลกที่ทำให้คน 1319 01:04:09,860 --> 01:04:12,210 และคุณสงสัยว่าพวกเขา เคยคิดว่า 1320 01:04:12,210 --> 01:04:15,730 ดังนั้น google ถ้าคุณมีอะไหล่บาง เวลาอยู่กับสิ่งที่เป็นวิธีการบางอย่างที่ตลก 1321 01:04:15,730 --> 01:04:17,730 ที่ people-- เช่นเดียวกับ คน ways-- ที่มีประสิทธิภาพ 1322 01:04:17,730 --> 01:04:20,371 ได้รับสามารถที่จะดำเนินการทุกประเภท 1323 01:04:20,371 --> 01:04:20,870 ตกลง. 1324 01:04:20,870 --> 01:04:22,880 และนี่เป็นเพียงแผนภูมิที่มีประโยชน์น้อย 1325 01:04:22,880 --> 01:04:26,850 ฉันรู้ว่าทุกท่านก่อนที่จะตอบคำถามที่ 0, จะอยู่ในห้องของคุณอาจจะพยายาม 1326 01:04:26,850 --> 01:04:27,960 ที่จะจดจำว่า 1327 01:04:27,960 --> 01:04:30,940 เพื่อให้มีความสุขในการมีสำหรับคุณผู้ชาย 1328 01:04:30,940 --> 01:04:37,120 ก็อย่าลืมตรรกะที่ made-- ทำไมตัวเลขเหล่านั้นกำลังเกิดขึ้น 1329 01:04:37,120 --> 01:04:39,870 หากคุณกำลังสูญเสียเสมอเพียงให้ แน่ใจว่าคุณรู้ว่าสิ่งที่ทุกประเภทที่มี 1330 01:04:39,870 --> 01:04:40,820 และคุณสามารถวิ่งผ่าน พวกเขาในใจของคุณ 1331 01:04:40,820 --> 01:04:42,903 ที่จะคิดออกว่าทำไมคนเหล่านั้น คำตอบคำตอบเหล่านั้น 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> ทั้งหมดขวา 1334 01:04:47,600 --> 01:04:49,680 ดังนั้นเรากำลังจะย้าย ในที่สุดที่จะค้นหา 1335 01:04:49,680 --> 01:04:51,638 เพราะเป็นที่ของคุณ ที่ได้อ่าน pset ที่ 1336 01:04:51,638 --> 01:04:55,175 การค้นหายังเป็นส่วนหนึ่งของ ปัญหาที่เกิดขึ้นในสัปดาห์นี้ชุด 1337 01:04:55,175 --> 01:04:57,300 คุณจะถูกถามในการดำเนินการ สองประเภทของการค้นหา 1338 01:04:57,300 --> 01:05:00,070 หนึ่งคือการค้นหาเชิงเส้นและ หนึ่งคือการค้นหาแบบไบนารี 1339 01:05:00,070 --> 01:05:01,760 >> ดังนั้นการค้นหาเชิงเส้นค่อนข้างง่าย 1340 01:05:01,760 --> 01:05:04,070 คุณเพียงแค่ต้องการค้นหาองค์ประกอบ ของรายการเพื่อดูว่าคุณได้รับมัน 1341 01:05:04,070 --> 01:05:05,444 คุณเพียงแค่ต้องย้ำผ่าน 1342 01:05:05,444 --> 01:05:08,170 และถ้ามันเท่ากับบางสิ่งบางอย่าง คุณก็สามารถส่งคืนได้ใช่มั้ย? 1343 01:05:08,170 --> 01:05:10,890 แต่สิ่งหนึ่งที่เรามากที่สุด ความสนใจในการพูดคุยเกี่ยวกับ 1344 01:05:10,890 --> 01:05:14,550 คือการค้นหาแบบไบนารีขวาซึ่งเป็น กลไกการแบ่งและพิชิตที่ 1345 01:05:14,550 --> 01:05:18,190 ดาวิดได้แสดงให้เห็นในการบรรยาย 1346 01:05:18,190 --> 01:05:20,810 >> โปรดจำไว้ตัวอย่างเช่นสมุดโทรศัพท์ ว่าเขาช่วยนำขึ้น, 1347 01:05:20,810 --> 01:05:23,960 หนึ่งที่เขาชนิดของการต่อสู้ บิตบนปีที่ผ่านมานี้ 1348 01:05:23,960 --> 01:05:27,530 ที่คุณแบ่งปัญหาที่เกิดขึ้นในช่วงครึ่งปี ในช่วงครึ่งปีในช่วงครึ่งปีอีกครั้งและอีกครั้ง 1349 01:05:27,530 --> 01:05:30,730 จนกว่าคุณจะพบสิ่งที่คุณกำลังมองหา? 1350 01:05:30,730 --> 01:05:33,727 และคุณได้มี รันไทม์ของที่ดี 1351 01:05:33,727 --> 01:05:35,810 และคุณสามารถเห็นมัน อย่างมีนัยสำคัญมีประสิทธิภาพมากขึ้น 1352 01:05:35,810 --> 01:05:39,080 กว่าชนิดอื่น ๆ ของการค้นหา 1353 01:05:39,080 --> 01:05:41,880 >> ดังนั้นวิธีการที่เราจะไปเกี่ยวกับ การดำเนินการค้นหาแบบทวิภาค 1354 01:05:41,880 --> 01:05:46,510 คือถ้าเรามีอาร์เรย์ ดัชนี 0-6 เจ็ดองค์ประกอบ 1355 01:05:46,510 --> 01:05:49,790 เราสามารถมองอยู่ตรงกลาง right-- ขออภัยหากคำถามของเรา first-- 1356 01:05:49,790 --> 01:05:53,840 ถ้าเราต้องการที่จะถามคำถามของไม่ อาร์เรย์มีองค์ประกอบ 7, 1357 01:05:53,840 --> 01:05:56,840 เห็นได้ชัดว่าเป็นมนุษย์และมี เช่นอาร์เรย์ขนาดเล็กมันเป็นเรื่องง่ายสำหรับเรา 1358 01:05:56,840 --> 01:05:58,210 จะบอกว่าใช่ 1359 01:05:58,210 --> 01:06:05,750 แต่วิธีการที่จะใช้ไบนารี การค้นหาจะมองที่อยู่ตรงกลาง 1360 01:06:05,750 --> 01:06:08,020 >> เรารู้ว่า 3 ดัชนี ตรงกลางเพราะเรา 1361 01:06:08,020 --> 01:06:09,270 รู้ว่ามีเจ็ดองค์ประกอบ 1362 01:06:09,270 --> 01:06:10,670 7 สิ่งที่หารด้วย 2 หรือไม่? 1363 01:06:10,670 --> 01:06:12,850 คุณสามารถตัดที่เพิ่ม 1 1364 01:06:12,850 --> 01:06:14,850 คุณได้มี 3 ที่อยู่ตรงกลาง 1365 01:06:14,850 --> 01:06:17,590 ดังนั้นอาร์เรย์ของ 3 เท่ากับ 7? 1366 01:06:17,590 --> 01:06:18,900 มันไม่ได้ใช่มั้ย? 1367 01:06:18,900 --> 01:06:21,050 แต่เราสามารถทำสองของการตรวจสอบ 1368 01:06:21,050 --> 01:06:25,380 เป็นอาร์เรย์ของ 3 น้อยกว่า 7 หรือ เป็นอาร์เรย์ของ 3 มากกว่า 7? 1369 01:06:25,380 --> 01:06:27,240 >> และเรารู้ว่ามันเป็นน้อยกว่า 7 1370 01:06:27,240 --> 01:06:30,259 ดังนั้นเราจึงรู้ว่าโอ้ก็ต้อง ไม่อยู่ในครึ่งซ้าย 1371 01:06:30,259 --> 01:06:32,300 เรารู้ว่ามันจะต้องเป็น ในช่วงครึ่งปีที่ถูกต้องใช่มั้ย? 1372 01:06:32,300 --> 01:06:34,662 ดังนั้นเราก็สามารถตัดครึ่งอาร์เรย์ 1373 01:06:34,662 --> 01:06:36,370 เราไม่ได้มีการ ดูมันอีกต่อไป 1374 01:06:36,370 --> 01:06:38,711 เพราะเรารู้ว่า ครึ่งหนึ่งของ problem-- ของเรา 1375 01:06:38,711 --> 01:06:41,210 เรารู้ว่าคำตอบคือใน ครึ่งขวาของปัญหาของเรา 1376 01:06:41,210 --> 01:06:42,580 ดังนั้นเราเพียง แต่มองว่าตอนนี้ 1377 01:06:42,580 --> 01:06:44,860 >> ดังนั้นตอนนี้เรามองไปที่ ตรงกลางของสิ่งที่เหลือ 1378 01:06:44,860 --> 01:06:46,880 ดัชนีที่ 5 1379 01:06:46,880 --> 01:06:50,200 เราจะตรวจสอบอีกครั้ง และเราจะเห็นว่ามันเป็นขนาดเล็ก 1380 01:06:50,200 --> 01:06:52,050 ดังนั้นเราจึงมองไปทางด้านซ้ายของว่า 1381 01:06:52,050 --> 01:06:53,430 และจากนั้นเราจะเห็นว่าการตรวจสอบ 1382 01:06:53,430 --> 01:06:57,600 ค่าอาร์เรย์ที่ ดัชนี 4 เท่ากับ 7? 1383 01:06:57,600 --> 01:06:58,260 มันคือ. 1384 01:06:58,260 --> 01:07:03,580 ดังนั้นเราจึงสามารถกลับมาจริงเพราะ เราพบว่าค่าในรายการของเรา 1385 01:07:03,580 --> 01:07:06,738 ไม่วิธีที่ฉันเดินผ่าน ที่ทำให้รู้สึกกับทุกคน? 1386 01:07:06,738 --> 01:07:08,760 ตกลง. 1387 01:07:08,760 --> 01:07:11,670 ฉันจะให้พวกคุณอาจจะชอบ สามสี่นาทีที่จะคิดออก 1388 01:07:11,670 --> 01:07:13,270 วิธีการ pseudocode นี้ 1389 01:07:13,270 --> 01:07:18,070 >> ดังนั้นผมคิดขอให้คุณเขียน ฟังก์ชั่นการค้นหาที่เรียกว่า () ที่กลับมา 1390 01:07:18,070 --> 01:07:20,640 ค่าค่าบูลีน, ว่าเป็นความจริงหรือ false-- ชอบ 1391 01:07:20,640 --> 01:07:22,970 ความจริงถ้าคุณคิดว่า ค่าที่เป็นเท็จถ้าคุณไม่ได้ 1392 01:07:22,970 --> 01:07:25,230 แล้วคุณได้ ส่งผ่านไปในค่าที่คุณ 1393 01:07:25,230 --> 01:07:28,410 เขากำลังมองหาเข้าไปในค่านิยมที่ เป็น array-- โอ้ฉันใส่แน่นอน 1394 01:07:28,410 --> 01:07:29,410 ที่อยู่ในสถานที่ที่ไม่ถูกต้อง 1395 01:07:29,410 --> 01:07:29,580 ตกลง. 1396 01:07:29,580 --> 01:07:31,829 Anyways ที่ควรจะมี รับไปทางขวาของค่า 1397 01:07:31,829 --> 01:07:36,280 และแล้ว int n เป็นจำนวน ขององค์ประกอบในอาร์เรย์ที่ 1398 01:07:36,280 --> 01:07:39,430 วิธีที่คุณจะไปเกี่ยวกับการพยายาม เพื่อ pseudocode ปัญหาในการที่? 1399 01:07:39,430 --> 01:07:41,630 ฉันจะให้พวกที่ชอบ สามนาทีที่จะทำ 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 ไม่ฉันคิดว่ามีเท่านั้นหากต้องการดู ใช่มีหนึ่งขวาขึ้นที่นี่ 1402 01:08:02,595 --> 01:08:03,261 ผู้ชม: ฉันสามารถ? 1403 01:08:03,261 --> 01:08:04,388 ANDI PENG: ใช่ฉันมีคุณ 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 คือการทำงานที่? 1406 01:08:11,050 --> 01:08:12,290 ตกลงเย็น 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> ตกลง. 1409 01:10:44,720 --> 01:10:47,630 พวกขวาทั้งหมดเรา จะบังเหียนใน 1410 01:10:47,630 --> 01:10:49,730 ตกลง. 1411 01:10:49,730 --> 01:10:54,020 ดังนั้นถือว่าเราได้มีที่น่ารักนี้ อาร์เรย์เล็ก ๆ น้อย ๆ ที่มีค่า n ที่อยู่ในนั้น 1412 01:10:54,020 --> 01:10:55,170 ผมไม่ได้วาดเส้น 1413 01:10:55,170 --> 01:10:58,649 แต่วิธีการที่เราจะไปเกี่ยวกับ พยายามที่จะเขียนนี้หรือไม่? 1414 01:10:58,649 --> 01:11:00,440 ไม่มีใครต้องการ ให้ฉันบรรทัดแรก? 1415 01:11:00,440 --> 01:11:02,814 ถ้าคุณต้องการให้ฉัน บรรทัดแรกของรหัสจำลองนี้ 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> ผู้ชม: [ไม่ได้ยิน] 1418 01:11:08,430 --> 01:11:10,138 ผู้ชม: คุณต้องการ ย้ำ through-- 1419 01:11:10,138 --> 01:11:11,094 ผู้ชม: เพ​​ียงแค่อีกวง? 1420 01:11:11,094 --> 01:11:11,760 ผู้ชม: --for 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI PENG: ดังนั้นนี้เป็นบิตหากิน 1423 01:11:17,780 --> 01:11:23,130 คิด about-- คุณต้องการ เพื่อให้ทำงานวงนี้ 1424 01:11:23,130 --> 01:11:27,950 ซ้ำแล้วซ้ำอีกจนเมื่อ? 1425 01:11:27,950 --> 01:11:30,819 >> ผู้ชม: จนกระทั่ง [ไม่ได้ยิน] ค่าเท่ากับค่าที่ 1426 01:11:30,819 --> 01:11:31,610 ANDI PENG: แน่นอน 1427 01:11:31,610 --> 01:11:33,900 เพื่อให้คุณสามารถจริงเพียง write-- เรายังสามารถลดความซับซ้อนมากขึ้น 1428 01:11:33,900 --> 01:11:35,630 เราก็สามารถทำวงในขณะที่ใช่มั้ย? 1429 01:11:35,630 --> 01:11:39,380 ดังนั้นคุณก็สามารถมี loop-- เรารู้ว่ามันเป็นในขณะที่ 1430 01:11:39,380 --> 01:11:42,850 แต่สำหรับตอนนี้ผมกำลังจะ จะพูดว่า "ห่วง" - ผ่านอะไร? 1431 01:11:42,850 --> 01:11:46,640 ห่วง until-- สิ่งที่เป็น สภาพสิ้นสุดของเราหรือไม่ 1432 01:11:46,640 --> 01:11:47,510 ฉันคิดว่าฉันได้ยินมัน 1433 01:11:47,510 --> 01:11:48,530 ผมได้ยินคนพูดว่า 1434 01:11:48,530 --> 01:11:51,255 >> ผู้ชม: ค่าเท่ากับกลาง 1435 01:11:51,255 --> 01:11:52,255 ANDI PENG: Say มันอีกครั้ง 1436 01:11:52,255 --> 01:11:54,470 ผู้ชม: หรือจน ค่าที่คุณกำลังค้นหา 1437 01:11:54,470 --> 01:11:58,470 สำหรับเท่ากับค่ากลาง 1438 01:11:58,470 --> 01:12:00,280 >> ANDI PENG: อะไรถ้ามันไม่ได้อยู่ในที่นั่น? 1439 01:12:00,280 --> 01:12:03,113 เกิดอะไรขึ้นถ้าค่าที่คุณกำลังค้นหา หาไม่ได้จริงในอาร์เรย์นี้หรือไม่? 1440 01:12:03,113 --> 01:12:05,890 ผู้ชม: คุณกลับ 1 1441 01:12:05,890 --> 01:12:08,850 >> ANDI PENG: แต่ทำในสิ่งที่เราต้องการ ห่วงจนถ้าเรามีเงื่อนไขหรือไม่? 1442 01:12:08,850 --> 01:12:09,350 ใช่ 1443 01:12:09,350 --> 01:12:11,239 >> ผู้ชม: จนกว่าจะมีเพียงหนึ่งค่า? 1444 01:12:11,239 --> 01:12:13,530 ANDI PENG: คุณสามารถห่วง until-- เพื่อให้คุณรู้ว่าคุณ 1445 01:12:13,530 --> 01:12:15,714 จะมีค่าสูงสุดใช่มั้ย? 1446 01:12:15,714 --> 01:12:18,130 และคุณรู้ว่าคุณจะ ที่จะมีค่าต่ำสุดใช่มั้ย? 1447 01:12:18,130 --> 01:12:20,379 เพราะยังว่าบางสิ่งบางอย่าง ฉันลืมที่จะพูดก่อน 1448 01:12:20,379 --> 01:12:22,640 บางสิ่งบางอย่างที่ว่า ที่สำคัญเกี่ยวกับการค้นหาแบบไบนารี 1449 01:12:22,640 --> 01:12:24,182 คืออาร์เรย์ของคุณจะถูกจัดเรียงอยู่แล้ว 1450 01:12:24,182 --> 01:12:26,973 เพราะมีวิธีการทำไม่ นี้ถ้าพวกเขากำลังค่าสุ่มเพียง 1451 01:12:26,973 --> 01:12:29,190 คุณไม่ทราบว่าเป็นอย่างใดอย่างหนึ่ง ที่มีขนาดใหญ่กว่าที่อื่น ๆ ใช่มั้ย? 1452 01:12:29,190 --> 01:12:32,720 >> เพื่อให้คุณรู้ว่าสูงสุดของคุณและ นาทีที่คุณอยู่ที่นี่ใช่มั้ย? 1453 01:12:32,720 --> 01:12:35,590 หากคุณกำลังจะได้รับการปรับ สูงสุดของคุณในนาทีและ mid-- ของคุณ 1454 01:12:35,590 --> 01:12:38,470 ให้เพียงสมมติของคุณ ค่ากลางที่เหมาะสม here-- 1455 01:12:38,470 --> 01:12:43,910 คุณกำลังจะเป็นพื้น ห่วงจนต่ำสุดคือ 1456 01:12:43,910 --> 01:12:47,510 เรื่องเดียวกันกับที่สูงสุดของคุณใช่หรือ ถ้าสูงสุดของคุณไม่ได้เป็นเช่นเดียวกับนาทีของคุณ 1457 01:12:47,510 --> 01:12:48,040 ใช่มั้ย? 1458 01:12:48,040 --> 01:12:51,340 เพราะที่เกิดขึ้นเมื่อคุณรู้ว่า คุณได้ตีในที่สุดค่าเดียวกัน 1459 01:12:51,340 --> 01:12:59,135 ดังนั้นคุณจึงต้องการที่จะห่วงจนนาทีของคุณ มีค่าน้อยกว่าหรือเท่ากับ to-- โอ๊ะ 1460 01:12:59,135 --> 01:13:01,510 ไม่น้อยกว่าหรือเท่ากับ วิธีอื่น ๆ around-- สูงสุด 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> ไม่ว่าทำให้รู้สึก? 1463 01:13:16,160 --> 01:13:18,810 ผมเอาไม่กี่พยายามที่จะได้รับสิทธิที่ 1464 01:13:18,810 --> 01:13:21,869 แต่ห่วงจนค่าสูงสุดของคุณ เป็นหลักเกือบน้อย 1465 01:13:21,869 --> 01:13:23,410 กว่าหรือเท่ากับขั้นต่ำของคุณใช่มั้ย? 1466 01:13:23,410 --> 01:13:25,201 นั่นคือเมื่อคุณรู้ว่า ที่คุณได้แปรสภาพ 1467 01:13:25,201 --> 01:13:29,290 ผู้ชม: เมื่อจะสูงสุดของคุณ ค่าต่ำกว่าขั้นต่ำหรือไม่ 1468 01:13:29,290 --> 01:13:31,040 ANDI PENG: ถ้าคุณเก็บ ปรับมันซึ่ง 1469 01:13:31,040 --> 01:13:32,380 คือสิ่งที่เราจะไป จะทำในเรื่องนี้ 1470 01:13:32,380 --> 01:13:33,460 ที่ทำให้รู้สึก? 1471 01:13:33,460 --> 01:13:35,750 ต่ำสุดและสูงสุดเป็นเพียง เลขที่เราอาจจะ 1472 01:13:35,750 --> 01:13:39,260 จะต้องการที่จะสร้างเพื่อให้ ติดตามการที่เรากำลังมองหา 1473 01:13:39,260 --> 01:13:41,790 เพราะอาร์เรย์มีอยู่ โดยไม่คำนึงถึงสิ่งที่เรากำลังทำ 1474 01:13:41,790 --> 01:13:45,030 เหมือนเราไม่ได้จริงร่างกาย ตัดออกอาร์เรย์ใช่มั้ย? 1475 01:13:45,030 --> 01:13:47,261 เราเพียงแค่ปรับ ที่เรากำลังมองหา 1476 01:13:47,261 --> 01:13:48,136 ที่ทำให้รู้สึก? 1477 01:13:48,136 --> 01:13:48,472 >> ผู้ชม: ใช่ 1478 01:13:48,472 --> 01:13:49,110 >> ANDI PENG: OK 1479 01:13:49,110 --> 01:13:57,090 ดังนั้นถ้าเป็นเงื่อนไขสำหรับวงของเรา ทำในสิ่งที่เราต้องการภายในของวงนี้หรือไม่? 1480 01:13:57,090 --> 01:13:58,700 สิ่งที่เรากำลังจะได้รับการต้องการที่จะทำอย่างไร 1481 01:13:58,700 --> 01:14:02,390 ดังนั้นตอนนี้เราได้มี สูงสุดและต่ำสุดขวา 1482 01:14:02,390 --> 01:14:04,962 อาจจะสร้างขึ้นที่นี่ที่ไหนสักแห่ง 1483 01:14:04,962 --> 01:14:07,170 เรากำลังจะไปอาจต้องการ ที่จะหาตรงกลางขวาหรือไม่? 1484 01:14:07,170 --> 01:14:08,450 พวกเราจะไปได้ สามารถที่จะหาตรงกลาง? 1485 01:14:08,450 --> 01:14:09,491 อะไร mathematical-- 1486 01:14:09,491 --> 01:14:11,079 ผู้ชม: แม็กซ์บวกนาทีโดยแบ่งออกเป็น 2 1487 01:14:11,079 --> 01:14:11,870 ANDI PENG: แน่นอน 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 ที่ทำให้รู้สึก? 1490 01:14:21,620 --> 01:14:25,780 และพวกคุณเห็นว่าทำไมเรา ไม่ได้เพียงแค่ use-- เหตุผลที่เราทำอย่างนี้ 1491 01:14:25,780 --> 01:14:27,850 แทนการทำเพียงแค่แบ่ง n 2? 1492 01:14:27,850 --> 01:14:30,310 ก็เพราะ n เป็นค่า ที่จะยังคงเหมือนเดิม 1493 01:14:30,310 --> 01:14:30,979 ใช่มั้ย? 1494 01:14:30,979 --> 01:14:34,020 แต่ที่เราปรับขั้นต่ำของเราและ ค่าสูงสุดที่พวกเขากำลังจะมีการเปลี่ยนแปลง 1495 01:14:34,020 --> 01:14:36,040 และเป็นผลกลางของเรา จะเปลี่ยนมากเกินไป 1496 01:14:36,040 --> 01:14:37,873 เพื่อที่ว่าทำไมเราต้องการ จะทำที่นี่ 1497 01:14:37,873 --> 01:14:38,510 ตกลง. 1498 01:14:38,510 --> 01:14:41,600 >> และแล้วในขณะนี้ว่า เราพบ our-- ใช่ 1499 01:14:41,600 --> 01:14:44,270 >> ผู้ชม: เพ​​ียงคำถามของอย่างรวดเร็ว เมื่อคุณพูดนาทีและสูงสุด 1500 01:14:44,270 --> 01:14:46,410 เราสมมติว่า มันเรียงอยู่แล้ว? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI เป็ง: ใช่ว่าเป็นจริง สิ่งที่จำเป็นสำหรับการค้นหาไบนารี 1502 01:14:48,400 --> 01:14:49,816 ที่คุณต้องรู้ว่ามันเรียง 1503 01:14:49,816 --> 01:14:53,660 ซึ่งเป็นเหตุผลที่เรียงลำดับที่คุณเขียนในของคุณ ปัญหาที่เกิดขึ้นก่อนที่จะตั้งค่าการค้นหาแบบไบนารีของคุณ 1504 01:14:53,660 --> 01:14:55,910 ตกลง. 1505 01:14:55,910 --> 01:14:58,876 ดังนั้นขณะนี้ที่เรารู้ว่าจุดกึ่งกลางของเรา จะทำในสิ่งที่คุณต้องการจะทำที่นี่? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> ผู้ชม: เราต้องการที่จะเปรียบเทียบ ที่ไปยังอีกคนหนึ่ง 1508 01:15:04,319 --> 01:15:05,110 ANDI PENG: แน่นอน 1509 01:15:05,110 --> 01:15:12,280 ดังนั้นคุณจะไปเปรียบเทียบ ช่วงกลางถึงค่าใช่มั้ย? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 และสิ่งที่ไม่บอก เราเมื่อเราเปรียบเทียบ? 1512 01:15:18,670 --> 01:15:22,226 เราต้องการอะไรที่จะทำหลังจากนั้น? 1513 01:15:22,226 --> 01:15:25,389 >> ผู้ชม: ถ้าค่ามีขนาดใหญ่ กว่าช่วงกลางเราต้องการที่จะตัดมันออก 1514 01:15:25,389 --> 01:15:26,180 ANDI PENG: แน่นอน 1515 01:15:26,180 --> 01:15:33,940 ดังนั้นถ้าค่ามีขนาดใหญ่ กว่าช่วงกลางเรา 1516 01:15:33,940 --> 01:15:36,550 จะต้องการการเปลี่ยนแปลงเหล่านี้ ต่ำสุดและ maxes ใช่มั้ย? 1517 01:15:36,550 --> 01:15:38,980 เราทำอะไรต้องการเปลี่ยน? 1518 01:15:38,980 --> 01:15:42,145 ดังนั้นหากเรารู้ว่ามีค่าเป็นที่ไหนสักแห่ง ในที่นี่สิ่งที่คุณเราจะเปลี่ยน? 1519 01:15:42,145 --> 01:15:44,758 เราต้องการที่จะเปลี่ยนของเรา ขั้นต่ำที่จะเป็นช่วงกลางใช่มั้ย? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 และแล้วอื่นถ้ามันอยู่ในนี้ ครึ่งหนึ่งของสิ่งที่เราต้องการที่จะเปลี่ยน? 1522 01:15:54,292 --> 01:15:55,306 >> ผู้ชม: สูงสุดของคุณ 1523 01:15:55,306 --> 01:15:55,972 ANDI เป็ง: ใช่ 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 แล้วคุณกำลังจะ เพื่อให้การวนลูปใช่มั้ย? 1526 01:16:04,680 --> 01:16:08,920 เพราะตอนนี้หลังจากที่หนึ่งซ้ำ ผ่านที่คุณได้สูงสุดที่นี่ 1527 01:16:08,920 --> 01:16:10,760 และจากนั้นคุณสามารถคำนวณกลาง 1528 01:16:10,760 --> 01:16:11,990 และจากนั้นคุณสามารถเปรียบเทียบ 1529 01:16:11,990 --> 01:16:14,766 และคุณกำลังจะให้ไป จนกระทั่งนาทีและ maxes 1530 01:16:14,766 --> 01:16:15,890 ได้แปรสภาพเป็นหลัก 1531 01:16:15,890 --> 01:16:17,890 และที่ว่าเมื่อคุณรู้ว่า คุณได้ตีปลายของมัน 1532 01:16:17,890 --> 01:16:20,280 และทั้งที่คุณได้พบมัน หรือคุณไม่ได้ที่จุดนั้น 1533 01:16:20,280 --> 01:16:23,170 >> นี้ไม่ได้ทำให้ความรู้สึกที่ทุกคน? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 ตกลง. 1536 01:16:26,770 --> 01:16:27,900 นี้เป็นสิ่งสำคัญสวย เพราะคุณจะมี 1537 01:16:27,900 --> 01:16:29,760 ที่จะเขียนนี้ในรหัสของคุณคืนนี้ 1538 01:16:29,760 --> 01:16:32,660 แต่พวกคุณมีที่ดีงาม ความรู้สึกของสิ่งที่คุณควรจะทำ 1539 01:16:32,660 --> 01:16:34,051 สิ่งไหนดี. 1540 01:16:34,051 --> 01:16:34,550 ตกลง. 1541 01:16:34,550 --> 01:16:38,840 ดังนั้นเราจึงได้มีประมาณเจ็ด นาทีส่วนที่เหลือ 1542 01:16:38,840 --> 01:16:43,170 ดังนั้นเรากำลังจะพูดคุยเกี่ยวกับ pset ที่เราจะทำ 1543 01:16:43,170 --> 01:16:46,410 ดังนั้น pset จะแบ่งออกเป็นสองส่วน 1544 01:16:46,410 --> 01:16:50,230 ในช่วงครึ่งแรกที่เกี่ยวข้องกับ การดำเนินการค้นหา 1545 01:16:50,230 --> 01:16:54,210 ในที่ที่คุณเขียนค้นหาเชิงเส้นเป็น การค้นหาแบบไบนารีและการเรียงลำดับขั้นตอนวิธีการ 1546 01:16:54,210 --> 01:16:56,690 >> ดังนั้นนี้เป็นครั้งแรก เวลาอยู่ใน pset ที่ 1547 01:16:56,690 --> 01:17:00,050 เราจะให้พวกคุณสิ่งที่เรียกว่า รหัสการจัดจำหน่ายซึ่งเป็นรหัส 1548 01:17:00,050 --> 01:17:02,740 ที่เราได้ล่วงหน้าเป็นลายลักษณ์อักษร แต่เหลือเพียงบางชิ้นออก 1549 01:17:02,740 --> 01:17:04,635 สำหรับคุณที่จะเสร็จสิ้นการเขียน 1550 01:17:04,635 --> 01:17:07,510 ดังนั้นพวกคุณเมื่อคุณดูที่นี้ รหัสคุณอาจได้รับกลัวจริงๆ 1551 01:17:07,510 --> 01:17:08,630 หากคุณเพียงแค่ต้องการอ่าผม ไม่ทราบว่าสิ่งที่ทำ 1552 01:17:08,630 --> 01:17:11,670 ผมไม่ทราบเหมือนที่ดูเหมือนว่า ซับซ้อนดังนั้นอ่าผ่อนคลาย 1553 01:17:11,670 --> 01:17:12,170 ไม่เป็นไร. 1554 01:17:12,170 --> 01:17:12,930 อ่านข้อมูลจำเพาะ 1555 01:17:12,930 --> 01:17:16,920 ข้อมูลจำเพาะจะอธิบายให้คุณว่า สิ่งทั้งหมดของโปรแกรมเหล่านี้จะทำ 1556 01:17:16,920 --> 01:17:20,560 >> ยกตัวอย่างเช่น generate.c เป็นโปรแกรมที่ ที่จะมาพร้อมกับ pset ของคุณ 1557 01:17:20,560 --> 01:17:24,060 คุณไม่จริงต้องสัมผัสมัน แต่ คุณควรจะเข้าใจในสิ่งที่มันทำ 1558 01:17:24,060 --> 01:17:28,550 และ generate.c ทั้งหมดที่มันทำคือ ทั้งการสร้างตัวเลขสุ่ม 1559 01:17:28,550 --> 01:17:32,400 หรือคุณสามารถให้เมล็ดเช่น จำนวนจัดแจงไว้ก่อนว่าจะใช้เวลา, 1560 01:17:32,400 --> 01:17:34,140 และสร้างจำนวนมากขึ้น 1561 01:17:34,140 --> 01:17:37,170 ดังนั้นมีวิธีที่เฉพาะเจาะจงในการ ใช้ generate.c ที่ 1562 01:17:37,170 --> 01:17:42,760 คุณก็สามารถทำให้พวงของตัวเลข สำหรับคุณที่จะทดสอบวิธีการอื่น ๆ ของคุณใน 1563 01:17:42,760 --> 01:17:45,900 >> ดังนั้นหากคุณต้องการที่จะสำหรับ ตัวอย่างเช่นการทดสอบพบของคุณ 1564 01:17:45,900 --> 01:17:48,970 คุณต้องการที่จะเรียกใช้ generate.c, สร้างพวงของตัวเลข 1565 01:17:48,970 --> 01:17:50,880 และเรียกใช้ฟังก์ชั่นช่วยเหลือของคุณ 1566 01:17:50,880 --> 01:17:53,930 ฟังก์ชั่นช่วยเหลือของคุณเป็นที่ที่คุณอยู่ จริงเขียนโค้ดร่างกาย 1567 01:17:53,930 --> 01:17:59,330 และคิดว่าผู้ช่วยเหลือเป็นไฟล์ห้องสมุด คุณเขียนว่าจะโทรห​​า 1568 01:17:59,330 --> 01:18:02,950 และอื่น ๆ ที่อยู่ใน helpers.c คุณจะ ทำค้นหาและการเรียงลำดับ 1569 01:18:02,950 --> 01:18:06,500 >> แล้วคุณจะเป็นหลัก เพียงแค่ใส่พวกเขาทั้งหมดเข้าด้วยกัน 1570 01:18:06,500 --> 01:18:10,350 สเปคจะบอกวิธีการ ใส่ที่ในบรรทัดคำสั่ง 1571 01:18:10,350 --> 01:18:14,880 และคุณจะสามารถที่จะทดสอบหรือ ไม่ได้เรียงลำดับและการค้นหาของคุณกำลังทำงาน 1572 01:18:14,880 --> 01:18:15,870 เย็น 1573 01:18:15,870 --> 01:18:18,720 มีใครเริ่มต้นแล้วและ ปัญหาที่พบหรือข้อสงสัย 1574 01:18:18,720 --> 01:18:20,520 พวกเขามีตอนนี้กับเรื่องนี้? 1575 01:18:20,520 --> 01:18:21,020 ตกลง. 1576 01:18:21,020 --> 01:18:21,476 >> ผู้ชม: รอ 1577 01:18:21,476 --> 01:18:21,932 ฉันมีคำถาม. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI เป็ง: ใช่ 1579 01:18:22,844 --> 01:18:28,390 >> ผู้ชม: ดังนั้นผมจึงเริ่มทำ การค้นหาเชิงเส้นใน helpers.c 1580 01:18:28,390 --> 01:18:29,670 และมันก็ไม่ได้จริงๆทำงาน 1581 01:18:29,670 --> 01:18:34,590 แต่แล้วต่อมาผมพบว่าเราเพียงแค่ ต้องลบมันและทำค้นหาแบบทวิภาค 1582 01:18:34,590 --> 01:18:36,991 ดังนั้นมันไม่สำคัญว่าถ้ามันไม่ทำงาน? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI PENG: คำตอบสั้นไม่ 1585 01:18:41,510 --> 01:18:42,642 แต่เนื่องจากเรา not-- 1586 01:18:42,642 --> 01:18:44,350 ผู้ชม: แต่ไม่มีใคร จริงการตรวจสอบ 1587 01:18:44,350 --> 01:18:46,058 ANDI เป็ง: เราไม่เคย จะเห็นได้ว่า 1588 01:18:46,058 --> 01:18:49,590 แต่คุณอาจต้องการที่จะทำให้ แน่ใจว่าการค้นหาของคุณทำงาน 1589 01:18:49,590 --> 01:18:51,700 เพราะถ้าคุณเชิงเส้น การค้นหาไม่ทำงาน 1590 01:18:51,700 --> 01:18:54,410 แล้วมีโอกาสไบนารีของคุณ ค้นหาจะไม่ได้ไปทำงานได้เป็นอย่างดี 1591 01:18:54,410 --> 01:18:56,646 เพราะคุณมีที่คล้ายกัน ตรรกะทั้งในส่วนของพวกเขา 1592 01:18:56,646 --> 01:18:58,020 และไม่มันไม่ได้เรื่องจริงๆ 1593 01:18:58,020 --> 01:19:01,300 ดังนั้นคนที่เดียวที่คุณจะเปิด ในการเรียงลำดับและมีการค้นหาแบบไบนารี 1594 01:19:01,300 --> 01:19:02,490 ใช่ 1595 01:19:02,490 --> 01:19:06,610 >> และยังมากของเด็กได้ พยายามรวบรวม helpers.c 1596 01:19:06,610 --> 01:19:09,550 คุณไม่ได้รับอนุญาตจริง จะทำอย่างนั้นเพราะ helpers.c 1597 01:19:09,550 --> 01:19:11,200 ไม่ได้มีหน้าที่หลัก 1598 01:19:11,200 --> 01:19:13,550 และเพื่อให้คุณควรเท่านั้น จะรวบรวมจริง 1599 01:19:13,550 --> 01:19:18,670 สร้างและหาเพราะหาสาย helpers.c และการทำงานที่อยู่ภายใน 1600 01:19:18,670 --> 01:19:20,790 เพื่อที่จะทำให้การแก้จุดบกพร่อง ความเจ็บปวดในก้น 1601 01:19:20,790 --> 01:19:22,422 แต่นั่นคือสิ่งที่เราต้องทำ 1602 01:19:22,422 --> 01:19:23,880 ผู้ชม: คุณเพียงแค่ทำให้ทุกใช่มั้ย? 1603 01:19:23,880 --> 01:19:27,290 ANDI PENG: คุณสามารถเพียง ทำให้ทุกเช่นกันใช่ 1604 01:19:27,290 --> 01:19:28,060 ตกลง. 1605 01:19:28,060 --> 01:19:32,570 เพื่อให้เป็นในแง่ของสิ่งที่ pset จะขอคุณทุกคนที่จะทำ 1606 01:19:32,570 --> 01:19:35,160 หากคุณมีคำถามใด ๆ โปรด ลังเลที่จะถามฉันหลังจากที่ส่วน 1607 01:19:35,160 --> 01:19:37,580 ฉันจะอยู่ที่นี่เช่น 20 นาที 1608 01:19:37,580 --> 01:19:40,500 >> และใช่ pset ของ มันไม่เลวร้าย 1609 01:19:40,500 --> 01:19:41,680 พวกคุณควรจะตกลง 1610 01:19:41,680 --> 01:19:43,250 เหล่านี้เพียงทำตามคำแนะนำ 1611 01:19:43,250 --> 01:19:47,840 ชนิดของการมีความรู้สึกของการมีเหตุผลอะไร ควรจะเกิดขึ้นและคุณจะได้รับการปรับ 1612 01:19:47,840 --> 01:19:48,690 ไม่ต้องกลัวเกินไป 1613 01:19:48,690 --> 01:19:50,220 มีจำนวนมากของรหัสเป็น เขียนแล้วมี 1614 01:19:50,220 --> 01:19:53,011 ไม่ต้องกลัวเกินไปถ้าคุณทำไม่ได้ เข้าใจในสิ่งที่ทุกคนนั่นหมายความว่า 1615 01:19:53,011 --> 01:19:54,749 ถ้าเป็นมากก็ปรับทั้งหมด 1616 01:19:54,749 --> 01:19:55,790 และมาเวลาทำการ 1617 01:19:55,790 --> 01:19:57,520 เราจะช่วยให้คุณใช้เวลาดู 1618 01:19:57,520 --> 01:20:00,810 >> ผู้ชม: ด้วยพิเศษ ฟังก์ชั่นไม่เรามองเหล่านั้นขึ้น? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI เป็ง: ใช่ผู้ที่อยู่ในรหัส 1620 01:20:03,417 --> 01:20:05,750 ในเกมที่ 15 ครึ่งหนึ่งของ มันเขียนแล้วสำหรับคุณ 1621 01:20:05,750 --> 01:20:09,310 ดังนั้นผู้ที่มีฟังก์ชั่น แล้วในรหัส 1622 01:20:09,310 --> 01:20:12,020 อือ 1623 01:20:12,020 --> 01:20:12,520 ทั้งหมดขวา 1624 01:20:12,520 --> 01:20:14,000 ดีโชคดีที่สุด 1625 01:20:14,000 --> 01:20:15,180 มันเป็นวันที่น่าขยะแขยง 1626 01:20:15,180 --> 01:20:19,370 เพื่อหวังว่าพวกคุณจะไม่รู้สึกมากเกินไป ไม่ดีเกี่ยวกับการเข้าพักภายในและการเข้ารหัส 1627 01:20:19,370 --> 01:20:22,133