1 00:00:00,000 --> 00:00:02,570 [Powered by Google Translate] [Розділ 3 - більш комфортною] 2 00:00:02,570 --> 00:00:05,070 [Rob Боуден - Гарвардський університет] 3 00:00:05,070 --> 00:00:07,310 >> [Це CS50. - CS50.TV] 4 00:00:07,310 --> 00:00:12,700 >> Отже, перше питання сформульовано дивно. 5 00:00:12,700 --> 00:00:17,480 GDB дозволяє вам "налагодження" програми, але, більш конкретно, що це дозволить вам робити? 6 00:00:17,480 --> 00:00:22,590 Я відповім, що один, і я не знаю, що саме очікував, 7 00:00:22,590 --> 00:00:27,910 таким чином, я припускаю, що це щось подібне вона дозволяє крок за кроком 8 00:00:27,910 --> 00:00:31,540 йти через програми, взаємодіяти з ним, змінювати перемінні, робити всі ці речі - 9 00:00:31,540 --> 00:00:34,270 в основному повністю контролювати виконання програми 10 00:00:34,270 --> 00:00:38,410 і перевіряти будь-якій частині виконання програми. 11 00:00:38,410 --> 00:00:43,030 Таким чином, ці функції дозволяють відлагоджувати речі. 12 00:00:43,030 --> 00:00:44,830 Добре. 13 00:00:44,830 --> 00:00:50,520 Чому бінарний пошук вимагає, щоб масив буде відсортований? 14 00:00:50,520 --> 00:00:53,360 Хто хоче відповісти? 15 00:00:56,120 --> 00:01:00,070 [Студент] Тому що він не працює, якщо він не сортуються. >> Да. [Сміх] 16 00:01:00,070 --> 00:01:04,910 Якщо це не відсортований, то неможливо розділити його навпіл 17 00:01:04,910 --> 00:01:07,850 і знаю, що все, що лівіше менше і все, що правіше 18 00:01:07,850 --> 00:01:10,490 більше середнього значення. 19 00:01:10,490 --> 00:01:12,790 Таким чином, він повинен бути відсортований. 20 00:01:12,790 --> 00:01:14,170 Добре. 21 00:01:14,170 --> 00:01:17,570 Чому бульбашкового сортування в O п квадратів? 22 00:01:17,570 --> 00:01:23,230 Хто-небудь спочатку хочу дати дуже швидкий високому рівні огляд того, що міхур сортування? 23 00:01:25,950 --> 00:01:33,020 [Студент] Ви в основному йдуть через кожен елемент, і ви перевірити декілька перших елементів. 24 00:01:33,020 --> 00:01:37,150 Якщо вони з того, де ви поміняти їх місцями, то перевірте наступні кілька елементів і так далі. 25 00:01:37,150 --> 00:01:40,770 Коли ви дійдете до кінця, то ви знаєте, що найбільший елемент міститься в кінці, 26 00:01:40,770 --> 00:01:42,750 так що ви ігноруєте, що один, то ви продовжуйте йти до кінця, 27 00:01:42,750 --> 00:01:48,490 і кожного разу ви повинні перевірити один елемент менше, поки ви не вносити ніяких змін. >> Да. 28 00:01:48,490 --> 00:01:58,470 Це називається бульбашкового сортування, тому що якщо перевернути масив на бік, так це вгору і вниз по вертикалі, 29 00:01:58,470 --> 00:02:03,100 Потім великих значеннях буде опускатися на дно і малих значень буде пузиритися до самого верху. 30 00:02:03,100 --> 00:02:05,210 Ось як він отримав свою назву. 31 00:02:05,210 --> 00:02:08,220 І так, ви просто проходите. 32 00:02:08,220 --> 00:02:11,190 Ви продовжуєте через масив, помінявши більшого значення 33 00:02:11,190 --> 00:02:14,040 Для отримання найбільших значень на дно. 34 00:02:14,040 --> 00:02:17,500 >> Чому це O п квадратів? 35 00:02:18,690 --> 00:02:24,620 По-перше, хто-небудь хочу сказати, чому це O п квадратів? 36 00:02:24,620 --> 00:02:28,760 [Студент] Тому що для кожного прогону він йде п раз. 37 00:02:28,760 --> 00:02:32,100 Ви можете бути впевнені, що Ви зробили найважливіший елемент весь шлях вниз, 38 00:02:32,100 --> 00:02:35,230 Потім вам доведеться повторити, що для, як багато елементів. >> Да. 39 00:02:35,230 --> 00:02:41,800 Так що майте на увазі, що велика O означає і те, що великі кошти Omega. 40 00:02:41,800 --> 00:02:50,560 The Big O, як верхня межа про те, як повільно він може реально працювати. 41 00:02:50,560 --> 00:02:58,990 Так, кажучи, що це O п квадрат, це не про п інакше вона була б в змозі управляти 42 00:02:58,990 --> 00:03:02,640 У лінійному часу, але це O п кубі 43 00:03:02,640 --> 00:03:06,390 тому що вона обмежена O п куб. 44 00:03:06,390 --> 00:03:12,300 Якщо це обмежена O п квадрат, то це обмежена також на п куб. 45 00:03:12,300 --> 00:03:20,280 Так що п в квадраті, а в абсолютній гіршому випадку він не може робити краще, ніж N в квадраті, 46 00:03:20,280 --> 00:03:22,830 Саме тому це O п квадрат. 47 00:03:22,830 --> 00:03:31,200 Таким чином, щоб побачити невелике математиці, як вона виходить, щоб бути вказаний в квадраті, 48 00:03:31,200 --> 00:03:40,530 якщо у нас є п'ять речей в нашому списку, в перший раз, скільки свопів ми могли б потенційно потрібно зробити 49 00:03:40,530 --> 00:03:47,170 для того, щоб отримати? Давайте насправді просто - 50 00:03:47,170 --> 00:03:52,040 Скільки свопи ми будемо мати, щоб зробити в першому запуску бульбашкового сортування в масиві? 51 00:03:52,040 --> 00:03:53,540 [Студент] п - 1. >> Да. 52 00:03:53,540 --> 00:03:58,340 >> Якщо є 5 елементів, ми збираємося потрібно зробити п - 1. 53 00:03:58,340 --> 00:04:01,100 Тоді на другому скільки свопів ми будемо мати, щоб зробити? 54 00:04:01,100 --> 00:04:03,440 [Студент] п - 2. >> Да. 55 00:04:03,440 --> 00:04:11,640 І третій буде п - 3, а потім для зручності я буду писати в останні два 56 00:04:11,640 --> 00:04:15,270 як і тоді, ми збираємося потрібно зробити 2 перестановок і 1 підкачки. 57 00:04:15,270 --> 00:04:19,899 Я припускаю, що остання може або не може фактично повинні відбутися. 58 00:04:19,899 --> 00:04:22,820 Це своп? Я не знаю. 59 00:04:22,820 --> 00:04:26,490 Так що це загальна сума свопів або принаймні порівнянь ви повинні зробити. 60 00:04:26,490 --> 00:04:29,910 Навіть якщо ви не поміняти, вам все ще потрібно порівняти значення. 61 00:04:29,910 --> 00:04:33,910 Таким чином, існує п - 1 порівнянь в перші проходять через масив. 62 00:04:33,910 --> 00:04:42,050 Якщо переставити ці речі, давайте насправді зробити це шість речей, так що все складається добре, 63 00:04:42,050 --> 00:04:44,790 і тоді я зроблю 3, 2, 1. 64 00:04:44,790 --> 00:04:49,910 Так що просто переставляючи ці суми, ми хочемо, щоб бачити, як багато порівнянь ми робимо 65 00:04:49,910 --> 00:04:52,700 у всьому алгоритмом. 66 00:04:52,700 --> 00:04:56,550 Таким чином, якщо ми принесемо ці хлопці тут, 67 00:04:56,550 --> 00:05:07,470 Потім ми ще раз підбиваючи проте багато порівнянь було. 68 00:05:07,470 --> 00:05:13,280 Але якщо ми підсумовуємо ці та підсумувати ці та підсумувати ці, 69 00:05:13,280 --> 00:05:18,130 вона як і раніше така ж проблема. Ми просто підвести тих конкретних груп. 70 00:05:18,130 --> 00:05:22,400 >> Отже, тепер ми підбиваючи N 3 в. Це не тільки 3 N. 71 00:05:22,400 --> 00:05:27,650 Це завжди буде п / 2 N. 72 00:05:27,650 --> 00:05:29,430 І ось ми, трапляється, є 6. 73 00:05:29,430 --> 00:05:34,830 Якби ми мали 10 речей, то ми могли б зробити це угруповання на 5 різних пар речі 74 00:05:34,830 --> 00:05:37,180 і в кінцевому підсумку з N + N + N + N + N. 75 00:05:37,180 --> 00:05:45,840 Таким чином, ви завжди будете отримувати п / 2 п, і так це ми будемо записувати його на п квадрат / 2. 76 00:05:45,840 --> 00:05:48,890 І хоча це фактор половини, які, трапляється, приходять в 77 00:05:48,890 --> 00:05:54,190 у зв'язку з тим, що через кожну ітерацію по масиву ми порівняємо 1 менше 78 00:05:54,190 --> 00:05:58,040 так що, як ми отримаємо понад 2, але він як і раніше п квадрат. 79 00:05:58,040 --> 00:06:01,650 Ми не турбуємося про постійне факторі половини. 80 00:06:01,650 --> 00:06:07,760 Так багато великих речей O, як це годиться тільки на вигляд робити такого роду математика, 81 00:06:07,760 --> 00:06:12,260 арифметичних сум і геометричні матеріал серії, 82 00:06:12,260 --> 00:06:17,750 але більшість з них в цьому курсі досить проста. 83 00:06:17,750 --> 00:06:19,290 Добре. 84 00:06:19,290 --> 00:06:24,430 Чому сортування вставкою в Omega п? Що омега значить? 85 00:06:24,430 --> 00:06:27,730 [Двох студентів говорити відразу - нерозбірливо] >> Да. 86 00:06:27,730 --> 00:06:30,630 Omega ви можете думати про якість нижньої межі. 87 00:06:30,630 --> 00:06:36,550 >> Тому незалежно від того, наскільки ефективно ваша вставки Алгоритм сортування, 88 00:06:36,550 --> 00:06:41,810 незалежно від того, список, який передається, він завжди має порівняти принаймні п речей 89 00:06:41,810 --> 00:06:44,620 або воно має для перебору п речей. 90 00:06:44,620 --> 00:06:47,280 Чому це відбувається? 91 00:06:47,280 --> 00:06:51,190 [Студент] Тому що, якщо список вже відсортований, то через першу ітерацію 92 00:06:51,190 --> 00:06:54,080 Ви можете гарантувати, що найперший елемент є принаймні, 93 00:06:54,080 --> 00:06:56,490 і другої ітерації можна гарантувати тільки перші два 94 00:06:56,490 --> 00:07:00,010 тому що ви не знаєте, що решті список відсортований. >> Да. 95 00:07:00,010 --> 00:07:08,910 Якщо ви передаєте в повністю відсортований список, принаймні, ви повинні йти по всіх елементах 96 00:07:08,910 --> 00:07:12,180 бачити, що нічого не потрібно переміщати. 97 00:07:12,180 --> 00:07:14,720 Таким чином, що проходять за списком і говорять про, це вже відсортовані, 98 00:07:14,720 --> 00:07:18,240 це неможливо, щоб ви знали, що це впорядковані, поки ви перевірити кожен елемент 99 00:07:18,240 --> 00:07:20,660 , Щоб побачити, що вони в певному порядку. 100 00:07:20,660 --> 00:07:25,290 Таким чином, нижня межа вставки сортування Omega н. 101 00:07:25,290 --> 00:07:28,210 Те, що в гіршому випадку час роботи сортування злиттям, 102 00:07:28,210 --> 00:07:31,390 гіршому випадку бути великим O знову? 103 00:07:31,390 --> 00:07:37,660 Таким чином, в гіршому випадку, як же сортування злиттям бігти? 104 00:07:42,170 --> 00:07:43,690 [Студент] N журнал п. >> Да. 105 00:07:43,690 --> 00:07:49,990 Найшвидший загальні алгоритми сортування є п § п. Ви не можете зробити краще. 106 00:07:51,930 --> 00:07:55,130 >> Існують особливі випадки, і якщо у нас є час сьогодні, - але ми, ймовірно won't - 107 00:07:55,130 --> 00:07:59,330 ми могли бачити той, який робить краще, ніж п § п. 108 00:07:59,330 --> 00:08:04,050 Але в загальному випадку, ви не можете зробити краще, ніж п § п. 109 00:08:04,050 --> 00:08:09,680 І сортування злиттям, трапляється, яку ви повинні знати, для цього, звичайно, що п § п. 110 00:08:09,680 --> 00:08:13,260 І тому ми фактично здійсненні цього сьогодні. 111 00:08:13,260 --> 00:08:18,070 І, нарешті, не більше ніж у трьох реченнях, як працює вибору роду? 112 00:08:18,070 --> 00:08:20,370 Хіба хтось хоче, щоб відповісти, і я буду вважати ваші пропозиції 113 00:08:20,370 --> 00:08:22,390 тому що якщо ви йдете в протягом 3 - 114 00:08:25,530 --> 00:08:28,330 Хтось пам'ятає вибір роду? 115 00:08:31,280 --> 00:08:37,809 Вибір роду, як правило, досить легко запам'ятати, просто з назви. 116 00:08:37,809 --> 00:08:45,350 Ви просто перебір масиву, знайти те, що найбільше значення є чи маленький - 117 00:08:45,350 --> 00:08:47,290 незалежно від того, ви сортування дюйма 118 00:08:47,290 --> 00:08:50,750 Так скажемо ми сортування від меншого до більшого. 119 00:08:50,750 --> 00:08:55,250 Ви ітерації по масиву, дивлячись на все, що мінімальний елемент, 120 00:08:55,250 --> 00:08:59,750 , Виділіть її, а потім просто замінити його те, що на перше місце. 121 00:08:59,750 --> 00:09:04,090 І тоді на другому проході по масиву, зверніть увагу на мінімальний елемент знову, 122 00:09:04,090 --> 00:09:07,490 , Виділіть її, а потім поміняти його з тим, що на другій позиції. 123 00:09:07,490 --> 00:09:10,650 Так що ми просто вибираючи, мінімальні значення 124 00:09:10,650 --> 00:09:16,050 і вставляючи їх в передній частині масиву, поки не буде відсортований. 125 00:09:19,210 --> 00:09:21,560 Питань з цього приводу? 126 00:09:21,560 --> 00:09:25,710 >> Це неминуче з'являються у формах ви повинні заповнити, коли ви відправляєте PSET. 127 00:09:29,010 --> 00:09:32,360 Це в основному відповіді на них. 128 00:09:32,360 --> 00:09:34,230 Отже, тепер проблеми з кодуванням. 129 00:09:34,230 --> 00:09:40,140 Я вже розіслав по електронній пошті - Хто-небудь не отримаєте цей лист? Добре. 130 00:09:40,140 --> 00:09:46,630 Я вже розіслав по електронній пошті простір, який ми збираємося використовувати, 131 00:09:46,630 --> 00:09:52,120 і якщо ви клацніть на моє ім'я, - так що я думаю, що я збираюся бути на дні 132 00:09:52,120 --> 00:09:57,170 через назад г - але якщо ви натиснете на моє ім'я, ви побачите 2 ревізії. 133 00:09:57,170 --> 00:10:02,650 1-а редакція збирається бути я вже скопіювали і вставили код в просторах 134 00:10:02,650 --> 00:10:06,900 для пошуку, що вам доведеться виконувати. 135 00:10:06,900 --> 00:10:10,540 І Перегляд 2 буде сортувати речі, які ми реалізуємо після цього. 136 00:10:10,540 --> 00:10:15,770 Таким чином, ви можете натиснути на мій Перегляд 1 і працювати там. 137 00:10:17,350 --> 00:10:22,060 А тепер ми хочемо реалізувати бінарний пошук. 138 00:10:22,060 --> 00:10:26,470 >> Хто-небудь хоче, щоб просто дати псевдокод високого рівня пояснення 139 00:10:26,470 --> 00:10:31,440 про те, що ми збираємося потрібно зробити для пошуку? Так. 140 00:10:31,440 --> 00:10:36,170 [Студент] Ви просто берете середині масиву і подивитися, якщо те, що ви шукаєте 141 00:10:36,170 --> 00:10:38,650 менше, ніж або більше. 142 00:10:38,650 --> 00:10:41,080 І якщо це менше, ви йдете в половину, що це менше, 143 00:10:41,080 --> 00:10:44,750 а якщо більше, ви йдете в половину більше, і ви повторити, що, поки ви не просто отримаєте одну річ. 144 00:10:44,750 --> 00:10:46,570 [Боуден] Так. 145 00:10:46,570 --> 00:10:51,320 Зверніть увагу, що наші номери масив вже відсортований, 146 00:10:51,320 --> 00:10:57,190 і так це означає, що ми можемо скористатися тим, що і ми могли б спочатку перевірити, 147 00:10:57,190 --> 00:11:00,390 Добре, я шукаю номер 50. 148 00:11:00,390 --> 00:11:03,720 Таким чином, я можу піти в середину. 149 00:11:03,720 --> 00:11:07,380 Близький важко визначити, коли це парне число речей, 150 00:11:07,380 --> 00:11:10,820 але давайте просто сказати, що ми завжди будемо обрізати до середини. 151 00:11:10,820 --> 00:11:14,420 Так що тут у нас є 8 речей, так що середня буде 16. 152 00:11:14,420 --> 00:11:17,330 Я шукаю 50, так 50 це більше, ніж 16. 153 00:11:17,330 --> 00:11:21,310 Так що тепер я в принципі може ставитися до моїх масив цих елементів. 154 00:11:21,310 --> 00:11:23,450 Я можу викинути все з 16 більш. 155 00:11:23,450 --> 00:11:27,440 Тепер мій масив саме ці 4 елементи, і я повторю. 156 00:11:27,440 --> 00:11:31,910 Так от я хочу знайти середину знову, що буде 42. 157 00:11:31,910 --> 00:11:34,730 42 менше 50, так що я можу викинути ці два елементи. 158 00:11:34,730 --> 00:11:36,890 Це моя залишилася масиву. 159 00:11:36,890 --> 00:11:38,430 Я збираюся знайти середину знову. 160 00:11:38,430 --> 00:11:42,100 Я думаю, 50 був поганий приклад, тому що я завжди викидати речі вліво, 161 00:11:42,100 --> 00:11:48,280 але по тій же мірою, якщо я шукав щось 162 00:11:48,280 --> 00:11:52,100 і це менше, ніж елемент В даний час я дивлюся, 163 00:11:52,100 --> 00:11:55,080 Потім я збираюся викинути все, що правіше. 164 00:11:55,080 --> 00:11:58,150 Отже, тепер ми повинні реалізувати це. 165 00:11:58,150 --> 00:12:02,310 Зверніть увагу, що ми повинні передати в розмірах. 166 00:12:02,310 --> 00:12:06,730 Ми можемо також не потрібно жорстко розмір коду. 167 00:12:06,730 --> 00:12:11,640 Тому, якщо ми позбудемося # визначити - 168 00:12:19,630 --> 00:12:21,430 Добре. 169 00:12:21,430 --> 00:12:27,180 Як я можу добре зрозуміти, що розмір масиву номерів у даний час? 170 00:12:27,180 --> 00:12:30,950 >> Скільки елементів у масиві чисел? 171 00:12:30,950 --> 00:12:33,630 [Студент] Цифри, кронштейни,. Довжина? 172 00:12:33,630 --> 00:12:36,600 [Боуден], якого не існує в C. 173 00:12:36,600 --> 00:12:38,580 Вам потрібно. Довжини. 174 00:12:38,580 --> 00:12:42,010 Масиви не мають властивості, тому немає Довжина властивість масивів 175 00:12:42,010 --> 00:12:45,650 що буде просто дати вам як би довго воно відбудеться, буде. 176 00:12:48,180 --> 00:12:51,620 [Студент] Див, скільки пам'яті вона має і розділити на скільки - >> Да. 177 00:12:51,620 --> 00:12:55,810 Так як ми можемо подивитися, скільки пам'яті вона має? >> [Студент] Sizeof. >> Да, SizeOf. 178 00:12:55,810 --> 00:13:01,680 Sizeof є оператором, який збирається повернути розмір масиву чисел. 179 00:13:01,680 --> 00:13:10,060 І це буде, однак багато цілі Є моменти, розмір цілого 180 00:13:10,060 --> 00:13:14,050 так це те, скільки пам'яті вона насправді займають. 181 00:13:14,050 --> 00:13:17,630 Так що, якщо я хочу, щоб кількість речей в масиві, 182 00:13:17,630 --> 00:13:20,560 Потім я збираюся хочуть розділити на розмір цілого числа. 183 00:13:22,820 --> 00:13:26,010 Добре. Так, що дозволяє мені пройти в розмірі тут. 184 00:13:26,010 --> 00:13:29,430 Чому я повинен пройти в розмірі взагалі? 185 00:13:29,430 --> 00:13:38,570 Чому я не можу просто зробити тут Int розмір = SizeOf (копиці сіна) / SizeOf (INT)? 186 00:13:38,570 --> 00:13:41,490 Чому це не працює? 187 00:13:41,490 --> 00:13:44,470 [Студент] Це не глобальна змінна. 188 00:13:44,470 --> 00:13:51,540 [Боуден] Haystack існує, і ми передаємо в цифрах, як копиця сіна, 189 00:13:51,540 --> 00:13:54,700 і це начебто ознаку того, що має прийти. Так. 190 00:13:54,700 --> 00:14:00,170 [Студент] Haystack це тільки посилання на нього, так що він повернеться, наскільки великий, що посилання. 191 00:14:00,170 --> 00:14:02,150 Так. 192 00:14:02,150 --> 00:14:09,000 Я сумніваюся, що в лекції, що ви бачили в стек ще насправді, чи не так? 193 00:14:09,000 --> 00:14:11,270 Ми тільки що говорили про це. 194 00:14:11,270 --> 00:14:16,090 Таким чином, стек, де всі ваші змінні будуть збережені. 195 00:14:16,090 --> 00:14:19,960 >> Будь пам'ять яка виділяється для локальних змінних йде в стек, 196 00:14:19,960 --> 00:14:24,790 і кожна функція отримує свій власний простір в стеку, його власний кадр стека, як це називається. 197 00:14:24,790 --> 00:14:31,590 Таким чином, основна має свій стек, а всередині нього буде існувати цей номер масиву, 198 00:14:31,590 --> 00:14:34,270 і вона буде розміром SizeOf (номера). 199 00:14:34,270 --> 00:14:38,180 Це буде мати розмір чисел, розділених за розміром елементів, 200 00:14:38,180 --> 00:14:42,010 але, що все живе в кадрі стека основного автора. 201 00:14:42,010 --> 00:14:45,190 Коли ми викликаємо пошук, пошук отримує власний фрейм стеку, 202 00:14:45,190 --> 00:14:48,840 свій власний простір для зберігання всіх своїх локальних змінних. 203 00:14:48,840 --> 00:14:56,420 Але ці аргументи - так стозі сіна не є копією цього весь масив. 204 00:14:56,420 --> 00:15:00,990 Ми не передаємо у всьому масиві у вигляді копії в пошуку. 205 00:15:00,990 --> 00:15:04,030 Він просто передає посилання на цей масив. 206 00:15:04,030 --> 00:15:11,470 Таким чином, пошук може отримати доступ до ці цифри через це посилання. 207 00:15:11,470 --> 00:15:17,100 Він як і раніше доступ до речах, які живуть усередині стека основного автора, 208 00:15:17,100 --> 00:15:22,990 але в основному, коли ми доберемося до покажчиків, які повинні бути найближчим часом, 209 00:15:22,990 --> 00:15:24,980 це те, що покажчики. 210 00:15:24,980 --> 00:15:29,400 Покажчики є просто посиланнями на речі, і ви можете використовувати покажчики для доступу до речі 211 00:15:29,400 --> 00:15:32,030 , Які в рамках інших речей »стека. 212 00:15:32,030 --> 00:15:37,660 Тому, навіть якщо номер є локальним для основного, ми все ще можемо отримати до нього доступ через цей покажчик. 213 00:15:37,660 --> 00:15:41,770 Але так як це просто покажчик, і це просто посилання, 214 00:15:41,770 --> 00:15:45,040 SizeOf (копиці сіна) просто повертає розмір самої посилання. 215 00:15:45,040 --> 00:15:47,950 Він не повертає розмір річ, це вказує. 216 00:15:47,950 --> 00:15:51,110 Він не повертає реальний розмір номерів. 217 00:15:51,110 --> 00:15:55,660 І таким чином, це не буде працювати, як ми хочемо. 218 00:15:55,660 --> 00:15:57,320 >> Питань з цього приводу? 219 00:15:57,320 --> 00:16:03,250 Покажчики вже не буде в значно більш докладно в гори тижні. 220 00:16:06,750 --> 00:16:13,740 І саме тому багато речей, які ви бачите, більшість речей, пошуку і сортування речей, 221 00:16:13,740 --> 00:16:16,990 вони майже всі будете потребувати, щоб прийняти реальний розмір масиву, 222 00:16:16,990 --> 00:16:20,440 тому що в C, ми поняття не маємо, що розмір масиву. 223 00:16:20,440 --> 00:16:22,720 Вам потрібно вручну передати його дюйма 224 00:16:22,720 --> 00:16:27,190 І ви не можете вручну передати у всьому масиві, тому що ви просто проходили у заслання 225 00:16:27,190 --> 00:16:30,390 і він не може отримати розмір із заслання. 226 00:16:30,390 --> 00:16:32,300 Добре. 227 00:16:32,300 --> 00:16:38,160 Отже, тепер ми хочемо, щоб здійснити те, що було пояснено раніше. 228 00:16:38,160 --> 00:16:41,530 Ви можете працювати на ньому протягом хвилини, 229 00:16:41,530 --> 00:16:45,250 і вам не доведеться турбуватися про те, щоб всі прекрасно 100% робочий. 230 00:16:45,250 --> 00:16:51,410 Просто напишіть до половини псевдокод, як ви думаєте, вона повинна працювати. 231 00:16:52,000 --> 00:16:53,630 Добре. 232 00:16:53,630 --> 00:16:56,350 Не потрібно бути повністю зробити з цим поки немає. 233 00:16:56,350 --> 00:17:02,380 Але хто-небудь відчувати себе комфортно з тим, що вони до цих пір, 234 00:17:02,380 --> 00:17:05,599 як те, що ми можемо працювати з разом? 235 00:17:05,599 --> 00:17:09,690 Хто-небудь хоче стати волонтером? Або я випадково вибрати. 236 00:17:12,680 --> 00:17:18,599 Це не повинно бути право на будь-які заходи, але дещо ми можемо змінити в робочому стані. 237 00:17:18,599 --> 00:17:20,720 [Студент] Звичайно. >> Добре. 238 00:17:20,720 --> 00:17:27,220 Таким чином, ви можете заощадити перегляду, натиснувши на маленьку іконку Зберегти. 239 00:17:27,220 --> 00:17:29,950 Ти Ramya, вірно? >> [Студент] Так. >> [Боуден] Добре. 240 00:17:29,950 --> 00:17:35,140 Так що тепер я можу переглядати перегляду і кожен може потягнути перегляду. 241 00:17:35,140 --> 00:17:38,600 І тут ми маємо - Добре. 242 00:17:38,600 --> 00:17:43,160 Так Ramya пішов з рекурсивне рішення, яке, безумовно, правильне рішення. 243 00:17:43,160 --> 00:17:44,970 Є два шляхи ви можете зробити з цією проблемою. 244 00:17:44,970 --> 00:17:48,060 Ви можете зробити це итеративно або рекурсивно. 245 00:17:48,060 --> 00:17:53,860 Більшість проблем, ви виявите, що можна зробити рекурсивно також може бути зроблено итеративно. 246 00:17:53,860 --> 00:17:58,510 Так от ми зробили це рекурсивно. 247 00:17:58,510 --> 00:18:03,730 >> У кого-небудь хочу, щоб визначити, що означає зробити функцію рекурсивної? 248 00:18:07,210 --> 00:18:08,920 [Студент] Якщо у вас є функція викликає сама себе 249 00:18:08,920 --> 00:18:13,470 , А потім називати себе, поки він вийде з істинним та вірним. >> Да. 250 00:18:13,470 --> 00:18:17,680 Рекурсивна функція це просто функція, яка називає себе. 251 00:18:17,680 --> 00:18:24,140 Є три великих речей, які рекурсивна функція повинна бути. 252 00:18:24,140 --> 00:18:27,310 По-перше, очевидно, це викликає сама себе. 253 00:18:27,310 --> 00:18:29,650 Другий базовий варіант. 254 00:18:29,650 --> 00:18:33,390 Так що в якийсь момент функція повинна припинити називати себе, 255 00:18:33,390 --> 00:18:35,610 і це те, що базовий варіант призначений для. 256 00:18:35,610 --> 00:18:43,860 Отже, ми знаємо, що ми повинні зупинитися, ми повинні відмовитися від нашої пошуку 257 00:18:43,860 --> 00:18:48,150 при запуску дорівнює кінця - і ми підемо по тому, що це значить. 258 00:18:48,150 --> 00:18:52,130 Але, нарешті, остання річ, яка важлива для рекурсивних функцій: 259 00:18:52,130 --> 00:18:59,250 Функції повинні якось наблизитися до базовим сценарієм. 260 00:18:59,250 --> 00:19:04,140 Подібно до цього, якщо ви насправді не всі оновлення, коли ви робити другий рекурсивний виклик, 261 00:19:04,140 --> 00:19:07,880 якщо ви буквально тільки викликом функції знову з тими ж аргументами 262 00:19:07,880 --> 00:19:10,130 і ніяких глобальних змінних були змінені або нічого, 263 00:19:10,130 --> 00:19:14,430 ви ніколи не досягнете базовий варіант, в цьому випадку, що це погано. 264 00:19:14,430 --> 00:19:17,950 Це буде нескінченна рекурсія і переповнення стека. 265 00:19:17,950 --> 00:19:24,330 Але тут ми бачимо, що оновлення відбувається, оскільки ми оновлюємо початок кінця + / 2, 266 00:19:24,330 --> 00:19:28,180 ми оновлюємо кінці аргументом тут, ми оновлюємо початку аргументом тут. 267 00:19:28,180 --> 00:19:32,860 Отже, у всіх рекурсивних викликів ми оновлюємо щось. Добре. 268 00:19:32,860 --> 00:19:38,110 Ви хочете йти з нами через ваше рішення? >> Звичайно. 269 00:19:38,110 --> 00:19:44,270 Я використовую SearchHelp так, що кожен раз, коли я роблю виклик цієї функції 270 00:19:44,270 --> 00:19:47,910 У мене є початок, де я шукаю в масиві і в кінці 271 00:19:47,910 --> 00:19:49,380 , Де я шукаю масиву. 272 00:19:49,380 --> 00:19:55,330 >> На кожному кроці, де він говорить, що це середній елемент, який є початком кінця + / 2, 273 00:19:55,330 --> 00:19:58,850 , Що дорівнює тому, що ми шукаємо? 274 00:19:58,850 --> 00:20:04,650 І якщо це так, то ми його знайшли, і я думаю, що передається до рівня рекурсії. 275 00:20:04,650 --> 00:20:12,540 І якщо це не так, то ми перевіряємо, що середнє значення масиву занадто великий, 276 00:20:12,540 --> 00:20:19,320 У цьому випадку ми дивимося на лівій половині масиву, йдучи від початку і до середини індексу. 277 00:20:19,320 --> 00:20:22,710 А в іншому випадку ми робимо в кінці тайму. 278 00:20:22,710 --> 00:20:24,740 [Боуден] Добре. 279 00:20:24,740 --> 00:20:27,730 Звучить непогано. 280 00:20:27,730 --> 00:20:36,640 Отже, пару речей, а насправді, це дуже високому рівні річ 281 00:20:36,640 --> 00:20:41,270 що ви ніколи не повинні знати, для цього, звичайно, але це правда. 282 00:20:41,270 --> 00:20:46,080 Рекурсивні функції, ви завжди чуєте, що вони погано справу 283 00:20:46,080 --> 00:20:51,160 тому що якщо ви рекурсивно називати себе занадто багато разів, ви отримаєте переповнення стека 284 00:20:51,160 --> 00:20:54,990 , Оскільки, як я вже говорив, кожна функція отримує власний фрейм стеку. 285 00:20:54,990 --> 00:20:59,500 Таким чином, кожен виклик рекурсивної функції одержує власний фрейм стеку. 286 00:20:59,500 --> 00:21:04,140 Так що якщо ви зробите 1000 рекурсивних викликів, ви отримуєте 1000 кадрів стека, 287 00:21:04,140 --> 00:21:08,390 і швидко ви привести до того, занадто багато кадрів стека і речі просто зламати. 288 00:21:08,390 --> 00:21:13,480 Так ось чому рекурсивні функції, як правило, погано. 289 00:21:13,480 --> 00:21:19,370 Але є і хороші підмножина рекурсивних функцій називається хвостом рекурсивних функцій, 290 00:21:19,370 --> 00:21:26,120 і це трапляється, наприклад, однієї, де, якщо компілятор помічає це 291 00:21:26,120 --> 00:21:29,920 і він повинен, я думаю, - в Clang, якщо ви передаєте його прапор-O2 292 00:21:29,920 --> 00:21:33,250 то помітите, що це хвіст рекурсивні та зробити все добре. 293 00:21:33,250 --> 00:21:40,050 >> Він буде використовувати той же кадр стека знову і знову для кожного рекурсивного виклику. 294 00:21:40,050 --> 00:21:47,010 І так як ви використовуєте той же кадр стека, вам не потрібно турбуватися про 295 00:21:47,010 --> 00:21:51,690 ніколи стек переповнений, і в той же час, як ви казали, 296 00:21:51,690 --> 00:21:56,380 , Де колись ви повернетеся так, то він повинен повернути всі ці кадри стека 297 00:21:56,380 --> 00:22:01,740 і 10-й виклик SearchHelp повинен повернутися в 9-му, повинен повернутися в 8-м. 298 00:22:01,740 --> 00:22:05,360 Так що не потрібно статися, коли функції хвіст рекурсивної. 299 00:22:05,360 --> 00:22:13,740 І тому те, що робить ця функція є рекурсивною хвіст зверніть увагу, що для будь-якого виклику searchHelp 300 00:22:13,740 --> 00:22:18,470 рекурсивний виклик, що він робить те, що він повертається. 301 00:22:18,470 --> 00:22:25,290 Таким чином, у першому зверненні до SearchHelp, ми або негайно повернутися помилковим, 302 00:22:25,290 --> 00:22:29,590 негайно повернути істинний, або ми робимо рекурсивний виклик SearchHelp 303 00:22:29,590 --> 00:22:33,810 де те, що ми повертаємося какой то виклик повертається. 304 00:22:33,810 --> 00:22:51,560 І ми не могли це зробити, якщо ми зробили щось подібне Int х = SearchHelp, повернення х * 2, 305 00:22:51,560 --> 00:22:55,440 лише деякі випадкові зміни. 306 00:22:55,440 --> 00:23:01,470 >> Так що тепер це рекурсивний виклик, це Int х = SearchHelp рекурсивного виклику, 307 00:23:01,470 --> 00:23:05,740 більше не є хвостовою рекурсією, тому що насправді доведеться повернутися 308 00:23:05,740 --> 00:23:10,400 повернутися до попереднього кадру стека, так що, що попередній виклик функції 309 00:23:10,400 --> 00:23:13,040 може щось робити з повертаним значенням. 310 00:23:13,040 --> 00:23:22,190 Так що це не хвіст рекурсивної, але те, що було раніше це красиво хвіст рекурсивної. Так. 311 00:23:22,190 --> 00:23:27,000 [Студент] не повинні другому випадку база буде в першу чергу перевіряється 312 00:23:27,000 --> 00:23:30,640 тому що не може бути ситуації, коли, коли ви передаєте його аргумент 313 00:23:30,640 --> 00:23:35,770 Ви почати = кінець, але вони голка значення. 314 00:23:35,770 --> 00:23:47,310 Це питання ми не можемо працювати в тому випадку, коли кінець голки значення 315 00:23:47,310 --> 00:23:52,000 або почати = кінець, відповідно, початок = кінець 316 00:23:52,000 --> 00:23:59,480 і ви насправді не перевірив, що особливе значення тим не менш, 317 00:23:59,480 --> 00:24:03,910 Потім починайте + кінця / 2 просто буде мати те ж значення. 318 00:24:03,910 --> 00:24:07,890 Але ми вже повернулися помилковим, і ми ніколи не перевіряли значення. 319 00:24:07,890 --> 00:24:14,240 Так, принаймні, в перший виклик, якщо розмір дорівнює 0, то ми хочемо повернутися помилковим. 320 00:24:14,240 --> 00:24:17,710 Але якщо розмір дорівнює 1, то запуск не буде рівних кінця, 321 00:24:17,710 --> 00:24:19,820 і ми принаймні перевірити один елемент. 322 00:24:19,820 --> 00:24:26,750 Але я думаю, ви маєте рацію в тому, що ми можемо в кінцевому підсумку у разі, коли почати кінця + / 2, 323 00:24:26,750 --> 00:24:31,190 Початок закінчує тим, що так само, як початок кінця + / 2, 324 00:24:31,190 --> 00:24:35,350 але ми ніколи насправді перевірити, що елемент. 325 00:24:35,350 --> 00:24:44,740 >> Таким чином, якщо ми спочатку перевіряємо, є середнім значенням елемента ми шукаємо, 326 00:24:44,740 --> 00:24:47,110 то ми можемо негайно повернути істинний. 327 00:24:47,110 --> 00:24:50,740 Інакше, якщо вони рівні, то немає ніякого сенсу в продовженні 328 00:24:50,740 --> 00:24:58,440 так як ми тільки збираємося оновити випадку, коли ми знаходимося на одного елемента масиву. 329 00:24:58,440 --> 00:25:01,110 Якщо один елемент не той, якого ми шукаємо, 330 00:25:01,110 --> 00:25:03,530 то все не так. Так. 331 00:25:03,530 --> 00:25:08,900 [Студент] Справа в тому, що, оскільки розмір насправді більше, ніж число елементів у масиві, 332 00:25:08,900 --> 00:25:13,070 вже є зсув - >> Так буде розмір - 333 00:25:13,070 --> 00:25:19,380 [Студент] Скажімо, якщо масив був розміром 0, то SearchHelp буде насправді перевірити копиці сіна з 0 334 00:25:19,380 --> 00:25:21,490 за першим покликом. 335 00:25:21,490 --> 00:25:25,300 Масив має розмір 0, тому 0 є - >> Да. 336 00:25:25,300 --> 00:25:30,750 Там Інша справа, що - це може бути хорошим. Давайте подумаємо. 337 00:25:30,750 --> 00:25:40,120 Таким чином, якщо масив був 10 елементів, а середній ми збираємося перевірити, є індексом 5, 338 00:25:40,120 --> 00:25:45,700 так ми перевіряємо 5, і давайте скажемо, що значення менше. 339 00:25:45,700 --> 00:25:50,720 Таким чином, ми кидали всі, від 5 і далі. 340 00:25:50,720 --> 00:25:54,030 Так що почніть з кінця + / 2 буде нашою новою мети 341 00:25:54,030 --> 00:25:57,450 так що так, вона завжди залишиться за межами масиву. 342 00:25:57,450 --> 00:26:03,570 Якщо мова йде про випадок, якщо воно було парних або непарних, то ми б перевірити, скажімо, 4, 343 00:26:03,570 --> 00:26:05,770 але ми все ще викидають - 344 00:26:05,770 --> 00:26:13,500 Так що так, кінець завжди буде за фактичний кінець масиву. 345 00:26:13,500 --> 00:26:18,350 Таким чином, елементи, які ми зосередилися на, кінець завжди буде після цього. 346 00:26:18,350 --> 00:26:24,270 І тому, якщо почати робить всі рівні Зрештою, ми знаходимося в масив розміром 0. 347 00:26:24,270 --> 00:26:35,600 >> Інша річ, я думав, що ми оновлюємо починають почати + кінця / 2, 348 00:26:35,600 --> 00:26:44,020 так що це той випадок, коли у мене виникають проблеми з, де починаються + кінця / 2 349 00:26:44,020 --> 00:26:46,820 є елементом, ми перевіряємо. 350 00:26:46,820 --> 00:26:58,150 Скажімо, у нас був цей 10-елементний масив. Неважливо. 351 00:26:58,150 --> 00:27:03,250 Так що почніть з кінця + / 2 буде щось на зразок цього, 352 00:27:03,250 --> 00:27:07,060 і якщо це не значення, що ми хочемо оновити. 353 00:27:07,060 --> 00:27:10,060 Значення більше, тому ми хочемо подивитися на цю половину масиву. 354 00:27:10,060 --> 00:27:15,910 Отже, як ми оновлюємо початку, ми оновлюємо початку тепер цей елемент. 355 00:27:15,910 --> 00:27:23,790 Але це все ще може працювати, або, принаймні, ви можете зробити старт + кінця / 2 + 1. 356 00:27:23,790 --> 00:27:27,850 [Студент] Вам не потрібно буде почати + кінця [нерозбірливо] >> Да. 357 00:27:27,850 --> 00:27:33,240 Ми вже перевірили цей елемент і знаю, що це не той, який ми шукаємо. 358 00:27:33,240 --> 00:27:36,800 Таким чином, нам не потрібно оновлювати починають цим елементом. 359 00:27:36,800 --> 00:27:39,560 Ми можемо просто пропустити його і оновлювати починають бути цей елемент. 360 00:27:39,560 --> 00:27:46,060 І є чи коли-небудь випадок, скажемо, що це був кінець, 361 00:27:46,060 --> 00:27:53,140 так, то почала було б цього, почніть кінці + / 2 буде таким, 362 00:27:53,140 --> 00:28:00,580 початок + кінець - Так, я думаю, що це може в кінцевому підсумку в нескінченну рекурсію. 363 00:28:00,580 --> 00:28:12,690 Скажімо, це просто масив розміром 2 або масив розміром 1. Я думаю, що це буде працювати. 364 00:28:12,690 --> 00:28:19,490 Таким чином, в даний час, є те, що початок і кінець елемента дорівнює 1 за його межами. 365 00:28:19,490 --> 00:28:24,110 Таким чином, елемент, який ми збираємося перевірити це одне, 366 00:28:24,110 --> 00:28:29,400 а потім, коли ми оновлюємо початку, ми оновлюємо починають 0 + 1/2, 367 00:28:29,400 --> 00:28:33,160 який закінчиться нас з початку буття цього елемента. 368 00:28:33,160 --> 00:28:36,210 >> Таким чином, ми перевіряємо і той же елемент знову і знову. 369 00:28:36,210 --> 00:28:43,310 Так що це той випадок, коли кожен рекурсивний виклик повинен насправді щось оновлювати. 370 00:28:43,310 --> 00:28:48,370 Так що нам потрібно зробити, початок + кінець / 2 + 1, або є випадок 371 00:28:48,370 --> 00:28:50,710 , Де ми насправді не оновленням початку. 372 00:28:50,710 --> 00:28:53,820 Все це бачили? 373 00:28:53,820 --> 00:28:56,310 Добре. 374 00:28:56,310 --> 00:29:03,860 Хто-небудь є питання по цьому рішенню або більше коментарів? 375 00:29:05,220 --> 00:29:10,280 Добре. Хто-небудь є ітераційного рішення, що ми всі можемо дивитися? 376 00:29:17,400 --> 00:29:20,940 Хіба ми все це робимо рекурсивно? 377 00:29:20,940 --> 00:29:25,950 А також, я думаю, якщо ви відкрили її, то вам, можливо, доведеться перевизначити вашу попередню. 378 00:29:25,950 --> 00:29:28,810 Чи означає це автоматично зберігати? Я не впевнений. 379 00:29:35,090 --> 00:29:39,130 Хто-небудь є ітераційний? 380 00:29:39,130 --> 00:29:42,430 Ми можемо пройти через це разом, якщо немає. 381 00:29:46,080 --> 00:29:48,100 Ідея буде те ж саме. 382 00:30:00,260 --> 00:30:02,830 Ітераційні рішення. 383 00:30:02,830 --> 00:30:07,140 Ми збираємося хочуть в основному, роблять ту ж ідею 384 00:30:07,140 --> 00:30:16,530 , Де ми хочемо бути в курсі нових кінці масиву і нові початку масиву 385 00:30:16,530 --> 00:30:18,510 і робити це знову і знову. 386 00:30:18,510 --> 00:30:22,430 І якщо те, що ми відстежують, як початок і кінець ніколи не перетинаються, 387 00:30:22,430 --> 00:30:29,020 тоді ми не знайшли його і ми можемо повернутися помилковим. 388 00:30:29,020 --> 00:30:37,540 Так як я можу це зробити? Будь є пропозиції або код для мене, щоб підтягти? 389 00:30:42,190 --> 00:30:47,450 [Студент] Чи подобається час циклу. >> Да. 390 00:30:47,450 --> 00:30:49,450 Ви збираєтеся хочете зробити петлю. 391 00:30:49,450 --> 00:30:51,830 >> У вас є код, я міг би підтягнути, чи те, що ви збиралися запропонувати? 392 00:30:51,830 --> 00:30:56,340 [Студент] Я так думаю. >> Все правильно. Це робить речі простіше. Яке було ваше ім'я? 393 00:30:56,340 --> 00:30:57,890 [Студент] Лукас. 394 00:31:00,140 --> 00:31:04,190 Перегляд 1. Добре. 395 00:31:04,190 --> 00:31:13,200 Низька те, що ми називали розпочати раніше. 396 00:31:13,200 --> 00:31:17,080 До це не зовсім те, що ми називали до кінця. 397 00:31:17,080 --> 00:31:22,750 Насправді, в кінці Зараз всередині масиву. Це елемент, який ми повинні розглянути. 398 00:31:22,750 --> 00:31:26,890 Таким чином, низьке значення 0, до це розмір масиву - 1, 399 00:31:26,890 --> 00:31:34,780 і тепер ми циклів, і ми перевіряємо - 400 00:31:34,780 --> 00:31:37,340 Я думаю, ви можете пройти через це. 401 00:31:37,340 --> 00:31:41,420 Яке було ваше мислення через це? Йдіть з нами через код. 402 00:31:41,420 --> 00:31:49,940 [Студент] Звичайно. Подивіться на стозі сіна значення в середніх і порівняти його з голки. 403 00:31:49,940 --> 00:31:58,520 Так що, якщо це більше, ніж ваша голка, то ви хочете, щоб - ой, насправді, що повинно бути навпаки. 404 00:31:58,520 --> 00:32:05,180 Ви збираєтеся хочете, щоб викинути правої половини, і так да, це повинен бути шлях. 405 00:32:05,180 --> 00:32:08,830 [Боуден] Таким чином, це повинно бути менше? Це те, що ви сказали? >> [Студент] Так. 406 00:32:08,830 --> 00:32:10,390 [Боуден] Добре. Поменше. 407 00:32:10,390 --> 00:32:15,700 Так що якщо ми дивимося на це менше, ніж те, що ми хочемо, 408 00:32:15,700 --> 00:32:19,410 то так, ми хочемо, щоб викинути ліву половину, 409 00:32:19,410 --> 00:32:22,210 яка означає, що ми оновлюємо всі ми розглядаємо 410 00:32:22,210 --> 00:32:26,610 шляхом переміщення низькою праворуч від масиву. 411 00:32:26,610 --> 00:32:30,130 Це виглядає добре. 412 00:32:30,130 --> 00:32:34,550 Я думаю, що це має те ж питання, що ми говорили на попередньому, 413 00:32:34,550 --> 00:32:49,760 де, якщо низьке значення 0 і вище дорівнює 1, то низько + до / 2 буде налаштований на одне і те ж знову. 414 00:32:49,760 --> 00:32:53,860 >> І навіть якщо це не так, то це ще більш ефективною, принаймні 415 00:32:53,860 --> 00:32:57,630 просто викинути елемент, ми просто дивилися на яких ми знаємо не так. 416 00:32:57,630 --> 00:33:03,240 Так низько + вгору / 2 + 1 - >> [студент] Це повинно бути по-іншому. 417 00:33:03,240 --> 00:33:05,900 [Боуден] Або це має бути - 1, а інша повинна бути + 1. 418 00:33:05,900 --> 00:33:09,580 [Студент] І не повинно бути подвійний знак рівності. >> [Боуден] Так. 419 00:33:09,580 --> 00:33:11,340 [Студент] Так. 420 00:33:14,540 --> 00:33:15,910 Добре. 421 00:33:15,910 --> 00:33:21,280 І, нарешті, тепер, коли у нас є це + 1 - 1 штука, 422 00:33:21,280 --> 00:33:31,520 це - вона не може бути - це взагалі можливо для низькою, щоб у підсумку значення більше, ніж нагорі? 423 00:33:35,710 --> 00:33:40,320 Я думаю, що єдиний спосіб, який може статися - Хіба це можливо? >> [Студент] я не знаю. 424 00:33:40,320 --> 00:33:45,220 Але якщо він отримує усічений, а потім отримує мінус, що 1, а потім - >> Да. 425 00:33:45,220 --> 00:33:47,480 [Студент] Було б, можливо, отримати переплуталися. 426 00:33:49,700 --> 00:33:53,940 Я думаю, що це має бути добре тільки тому, що 427 00:33:53,940 --> 00:33:58,800 для того, щоб в кінцевому підсумку нижче вони повинні бути рівні, я думаю. 428 00:33:58,800 --> 00:34:03,070 Але якщо вони рівні, то ми б не зробили той час як цикл з самого початку 429 00:34:03,070 --> 00:34:06,670 і ми просто повернулися б значення. Так що я думаю, що ми добре зараз. 430 00:34:06,670 --> 00:34:11,530 Зверніть увагу, що, хоча ця проблема більше не є рекурсивною, 431 00:34:11,530 --> 00:34:17,400 такі ж ідеї застосовні, де ми можемо побачити, як це так легко піддається 432 00:34:17,400 --> 00:34:23,659 на рекурсивне рішення тим, що ми просто оновлення індексів знову і знову, 433 00:34:23,659 --> 00:34:29,960 ми робимо проблемою менше і менше, ми фокусуємося на підмножину масиву. 434 00:34:29,960 --> 00:34:40,860 [Студент] Якщо низький дорівнює 0 і вище 1, вони як би 0 + 1/2, який піде на 0, 435 00:34:40,860 --> 00:34:44,429 а то можна було б + 1, можна було б бути - 1. 436 00:34:47,000 --> 00:34:50,870 [Студент] Куди ми перевірка рівності? 437 00:34:50,870 --> 00:34:55,100 Подібно до цього, якщо середній насправді голку? 438 00:34:55,100 --> 00:34:58,590 Ми в даний час не робить цього? О! 439 00:35:00,610 --> 00:35:02,460 Якщо it's - 440 00:35:05,340 --> 00:35:13,740 Так. Ми не можемо просто зробити тест тут, тому що скажімо першій середній - 441 00:35:13,740 --> 00:35:16,430 [Студент] Це насправді хотів не викидайте кордону. 442 00:35:16,430 --> 00:35:20,220 Таким чином, якщо Ви хочете позбутися пов'язаного, ви повинні перевірити його першим або будь-який інший. 443 00:35:20,220 --> 00:35:23,350 Ah. Так. >> [Студент] Так. 444 00:35:23,350 --> 00:35:29,650 Отже, ми викинули, яку ми в даний час дивилися, 445 00:35:29,650 --> 00:35:33,260 яка означає, що ми тепер повинні також мати 446 00:35:33,260 --> 00:35:44,810 якщо (копиці сіна [(низький + вгору) / 2] == голкою), то ми можемо повернутися вірно. 447 00:35:44,810 --> 00:35:52,070 І чи можу я покласти ще або просто якщо це означає буквально те ж саме 448 00:35:52,070 --> 00:35:57,110 тому що це повернувся б правдою. 449 00:35:57,110 --> 00:36:01,450 Так що я поклав ще, якщо, але це не має значення. 450 00:36:01,450 --> 00:36:10,440 >> Так ще, якщо це, ще це, і це є загальним, що я роблю 451 00:36:10,440 --> 00:36:14,340 де, навіть якщо це випадок, коли все тут добре, 452 00:36:14,340 --> 00:36:22,780 як низький ніколи не може бути більше, ніж вгору, не варто міркувань про те, що це правда. 453 00:36:22,780 --> 00:36:28,010 Таким чином, ви можете також сказати, в той час як низьке, менше або дорівнює 454 00:36:28,010 --> 00:36:30,720 або при низькому менше 455 00:36:30,720 --> 00:36:35,300 так що якщо вони коли-небудь рівною або низької відбувається, щоб пройти мимо, 456 00:36:35,300 --> 00:36:40,130 то ми можемо вирватися з цього циклу. 457 00:36:41,410 --> 00:36:44,630 Питання, проблеми, коментарі? 458 00:36:47,080 --> 00:36:49,270 Добре. Це виглядає добре. 459 00:36:49,270 --> 00:36:52,230 Тепер ми хочемо зробити сортування. 460 00:36:52,230 --> 00:37:04,030 Якщо ми підемо до мого другого перегляду, ми бачимо ті ж числа, 461 00:37:04,030 --> 00:37:07,550 але тепер вони більше не в порядку сортування. 462 00:37:07,550 --> 00:37:12,840 І ми хочемо реалізувати за допомогою будь-якого роду алгоритм O п § п. 463 00:37:12,840 --> 00:37:17,240 Отже, який алгоритм ви думаєте, ми повинні реалізувати тут? >> [Студент] Злиття роду. 464 00:37:17,240 --> 00:37:23,810 [Боуден] Так. Злиття сортування O (п § п), так це те, що ми збираємося робити. 465 00:37:23,810 --> 00:37:26,680 І проблема буде досить схожі, 466 00:37:26,680 --> 00:37:31,920 , Де він легко піддається рекурсивне рішення. 467 00:37:31,920 --> 00:37:35,580 Ми також можемо придумати ітераційного рішення, якщо ми хочемо, 468 00:37:35,580 --> 00:37:42,540 але рекурсія буде легше тут, і ми повинні зробити рекурсію. 469 00:37:45,120 --> 00:37:49,530 Я думаю, ми будемо ходити через сортування злиттям перше, 470 00:37:49,530 --> 00:37:54,280 хоча є прекрасні відео на сортування злиттям вже. [Сміх] 471 00:37:54,280 --> 00:37:59,780 Так сортування злиттям є - я витрачати так багато роботи. 472 00:37:59,780 --> 00:38:02,080 О, є тільки один зліва. 473 00:38:02,080 --> 00:38:03,630 Таким чином, злиття. 474 00:38:08,190 --> 00:38:12,470 О, 1, 3, 5. 475 00:38:26,090 --> 00:38:27,440 Добре. 476 00:38:29,910 --> 00:38:33,460 Злиття має два окремих масивів. 477 00:38:33,460 --> 00:38:36,780 Індивідуально цих двох масивів і сортуються. 478 00:38:36,780 --> 00:38:40,970 Таким чином, цей масив, 1, 3, 5, відсортовані. Цей масив, 0, 2, 4, відсортовані. 479 00:38:40,970 --> 00:38:46,710 Тепер те, що злиття повинні зробити, це об'єднати їх в один масив, який сам відсортовані. 480 00:38:46,710 --> 00:38:57,130 Тому ми хочемо масив розміром 6, який буде мати ці елементи всередині нього 481 00:38:57,130 --> 00:38:59,390 в певному порядку. 482 00:38:59,390 --> 00:39:03,390 >> І тому ми можемо скористатися тим, що ці два масиви сортуються 483 00:39:03,390 --> 00:39:06,800 Для цього в лінійному часу, 484 00:39:06,800 --> 00:39:13,510 лінійні сенс часу, якщо цей масив розміром х, і це розмір у, 485 00:39:13,510 --> 00:39:20,970 то загальний алгоритм повинен бути O (х + у). Добре. 486 00:39:20,970 --> 00:39:23,150 Таким чином, пропозиції. 487 00:39:23,150 --> 00:39:26,030 [Студент] Чи можемо ми почати з лівої? 488 00:39:26,030 --> 00:39:30,150 Таким чином, ви будете ставити 0 вниз, а потім 1, а потім тут ви на 2. 489 00:39:30,150 --> 00:39:33,320 Так що це ніби як у вас є вкладка, яка рухається вправо. >> [Боуден] Так. 490 00:39:33,320 --> 00:39:41,070 Для обох цих масивів, якщо ми зосередимося тільки на лівий елемент. 491 00:39:41,070 --> 00:39:43,530 Оскільки обидва масиви сортуються, ми знаємо, що ці 2 елементи 492 00:39:43,530 --> 00:39:46,920 найменші елементи в будь-якому масиві. 493 00:39:46,920 --> 00:39:53,500 Таким чином, це означає, що 1 з цих 2 елементи повинні бути найменший елемент в нашому об'єднаному масиві. 494 00:39:53,500 --> 00:39:58,190 Просто так вийшло, що є найменшим один на цей раз. 495 00:39:58,190 --> 00:40:02,580 Таким чином, ми візьмемо 0, вставте його на лівій, тому що 0 менше 1, 496 00:40:02,580 --> 00:40:08,210 так візьміть 0, вставте її в нашу першу позицію, а потім оновлювати цей 497 00:40:08,210 --> 00:40:12,070 в даний час зосереджена на перший елемент. 498 00:40:12,070 --> 00:40:14,570 А тепер повторіть. 499 00:40:14,570 --> 00:40:20,670 Отже, тепер ми порівняємо 2 і 1. 1 менше, тому ми вставимо 1. 500 00:40:20,670 --> 00:40:25,300 Ми оновлюємо цей покажчик, щоб вказати на цього хлопця. 501 00:40:25,300 --> 00:40:33,160 Зараз ми робимо це знову, так що 2. Це дозволить оновити, порівняти ці 2, 3. 502 00:40:33,160 --> 00:40:37,770 Цей поновлення, то 4 і 5. 503 00:40:37,770 --> 00:40:42,110 Так що це злиття. 504 00:40:42,110 --> 00:40:49,010 >> Це повинно бути досить очевидно, що це лінійний час, так як ми просто йдемо по кожному елементу раз. 505 00:40:49,010 --> 00:40:55,980 І це великий крок до реалізації сортування злиттям це робить. 506 00:40:55,980 --> 00:40:59,330 І це не так складно. 507 00:40:59,330 --> 00:41:15,020 Пара речей, щоб турбуватися про те, скажімо, ми зливалися 1, 2, 3, 4, 5, 6. 508 00:41:15,020 --> 00:41:30,930 У цьому випадку ми в кінцевому підсумку в сценарії, де ця буде менше, 509 00:41:30,930 --> 00:41:36,160 Потім ми оновлюємо цей покажчик, на цей раз буде менше, оновлювати, 510 00:41:36,160 --> 00:41:41,280 цьому це менше, і тепер ви повинні визнати, 511 00:41:41,280 --> 00:41:44,220 коли ви реально працювати з елементів з чим порівнювати. 512 00:41:44,220 --> 00:41:49,400 Так як ми вже використали весь цей масив, 513 00:41:49,400 --> 00:41:55,190 всі в цьому масиві тепер просто вставляється в тут. 514 00:41:55,190 --> 00:42:02,040 Тому, якщо ми коли-небудь працювати в точку, де один з наших масивів повністю об'єднані вже, 515 00:42:02,040 --> 00:42:06,510 Потім ми просто візьмемо всі елементи інших масивів і вставити їх в кінець масиву. 516 00:42:06,510 --> 00:42:13,630 Таким чином, ми можемо просто вставити 4, 5, 6. Добре. 517 00:42:13,630 --> 00:42:18,070 Тобто одна річ, щоб не упустити. 518 00:42:22,080 --> 00:42:26,120 Реалізація, яка повинна бути кроком 1. 519 00:42:26,120 --> 00:42:32,600 Сортування злиттям потім на основі цього, це 2 кроки, 2 дурних кроків. 520 00:42:38,800 --> 00:42:42,090 Давайте просто дати цього масиву. 521 00:42:57,920 --> 00:43:05,680 Таким чином, сортування злиттям, крок 1, щоб рекурсивно розбити масив на дві половини. 522 00:43:05,680 --> 00:43:09,350 Таким чином розділити цей масив на дві половини. 523 00:43:09,350 --> 00:43:22,920 Тепер у нас є 4, 15, 16, 50 і 8, 23, 42, 108. 524 00:43:22,920 --> 00:43:25,800 І тепер ми робимо це знову, і ми розділити ці дві половини. 525 00:43:25,800 --> 00:43:27,530 Я просто зроблю це на цьому боці. 526 00:43:27,530 --> 00:43:34,790 Таким чином, 4, 15 і 16, 50. 527 00:43:34,790 --> 00:43:37,440 Ми хотіли б зробити те ж саме тут. 528 00:43:37,440 --> 00:43:40,340 І тепер ми розділили його на дві половинки знову. 529 00:43:40,340 --> 00:43:51,080 І у нас є 4, 15, 16, 50. 530 00:43:51,080 --> 00:43:53,170 Так що це наш базовий сценарій. 531 00:43:53,170 --> 00:44:00,540 Після масиви розміром 1, то ми зупиняємо з розщепленням на дві половини. 532 00:44:00,540 --> 00:44:03,190 >> Тепер те, що ми будемо робити з цим? 533 00:44:03,190 --> 00:44:15,730 Ми в кінцевому підсумку це також буде розпадатися на 8, 23, 42 і 108. 534 00:44:15,730 --> 00:44:24,000 Так що тепер ми перебуваємо в цій точці, тепер крок два роду злиття просто злиття пари в списках. 535 00:44:24,000 --> 00:44:27,610 Тому ми хочемо, щоб об'єднати ці. Ми просто подзвонити злиття. 536 00:44:27,610 --> 00:44:31,410 Ми знаємо, що злиття буде повернути їх у певному порядку. 537 00:44:31,410 --> 00:44:33,920 4, 15. 538 00:44:33,920 --> 00:44:41,440 Тепер ми хочемо, щоб об'єднати ці, і видасть список з тими, в певному порядку, 539 00:44:41,440 --> 00:44:44,160 16, 50. 540 00:44:44,160 --> 00:44:57,380 Ми об'єднати ці - я не можу написати - 8, 23 і 42, 108. 541 00:44:57,380 --> 00:45:02,890 Отже, ми маємо об'єднану пар відразу. 542 00:45:02,890 --> 00:45:05,140 Тепер ми просто об'єднати знову. 543 00:45:05,140 --> 00:45:10,130 Зверніть увагу, що кожен з цих списків, відсортованих у собі, 544 00:45:10,130 --> 00:45:15,220 і тоді ми можемо просто об'єднати ці списки, щоб отримати список розмірі 4, який сортується 545 00:45:15,220 --> 00:45:19,990 і злиття цих двох списків, щоб отримати список розміром 4, відсортований. 546 00:45:19,990 --> 00:45:25,710 І, нарешті, ми можемо об'єднати ці два списки розмір 4, щоб отримати один список розмірі 8, який сортується. 547 00:45:25,710 --> 00:45:34,030 Таким чином, щоб зрозуміти, що це загальна п § п, ми вже бачили, що злиття є лінійною, 548 00:45:34,030 --> 00:45:40,390 тому, коли ми маємо справу з злиття цих, так як загальна вартість злиття 549 00:45:40,390 --> 00:45:43,410 для цих двох списків знаходиться всього в 2, тому що - 550 00:45:43,410 --> 00:45:49,610 Або добре, це O п, п, але от тільки ці 2 елементи, так що 2. 551 00:45:49,610 --> 00:45:52,850 І ці 2 буде 2 і ці 2 буде 2, і ці 2 буде 2, 552 00:45:52,850 --> 00:45:58,820 так через все зливається, що ми повинні зробити, ми в кінцевому підсумку робить н. 553 00:45:58,820 --> 00:46:03,210 Як 2 + 2 + 2 + 2 складає 8, який є п, 554 00:46:03,210 --> 00:46:08,060 так що вартість злиття в цій безлічі N. 555 00:46:08,060 --> 00:46:10,810 І те ж саме і тут. 556 00:46:10,810 --> 00:46:16,980 Ми об'єднати ці 2, то ці 2 і індивідуально цього злиття займе чотири операції, 557 00:46:16,980 --> 00:46:23,610 це злиття займе чотири операції, але знову ж таки, між усім цим, 558 00:46:23,610 --> 00:46:29,030 ми в кінцевому підсумку злиття п загальна речі, і тому цей крок займає н. 559 00:46:29,030 --> 00:46:33,670 І так кожен рівень має п елементів у злитті. 560 00:46:33,670 --> 00:46:36,110 >> А скільки рівнів є? 561 00:46:36,110 --> 00:46:40,160 На кожному рівні нашого масиву збільшується на розмір 2. 562 00:46:40,160 --> 00:46:44,590 Тут наші масиви мають розмір 1, тут вони розміром 2, тут вони розміром 4, 563 00:46:44,590 --> 00:46:46,470 І, нарешті, вони розміром 8. 564 00:46:46,470 --> 00:46:56,450 Таким чином, оскільки воно подвоюється, там буде в загальній складності § п з цих рівнів. 565 00:46:56,450 --> 00:47:02,090 Так що з § п рівнів, кожен рівень з п загальна операцій, 566 00:47:02,090 --> 00:47:05,720 ми отримуємо § п п алгоритм. 567 00:47:05,720 --> 00:47:07,790 Питання? 568 00:47:08,940 --> 00:47:13,320 У людей, які вже домоглися прогресу на те, як здійснити це? 569 00:47:13,320 --> 00:47:18,260 Хто-небудь вже в стані, коли я можу просто підтягти свій код? 570 00:47:20,320 --> 00:47:22,260 Я можу дати хвилину. 571 00:47:24,770 --> 00:47:27,470 Це одне буде більше. 572 00:47:27,470 --> 00:47:28,730 Я настійно рекомендую повторюються - 573 00:47:28,730 --> 00:47:30,510 Ви не повинні зробити рекурсію для злиття 574 00:47:30,510 --> 00:47:33,750 тому що зробити рекурсію для злиття, ви будете мати, щоб пройти купу різних розмірів. 575 00:47:33,750 --> 00:47:37,150 Можна, але це дратує. 576 00:47:37,150 --> 00:47:43,720 Але рекурсії для сортування саме по собі досить легко. 577 00:47:43,720 --> 00:47:49,190 Ви просто дзвоните роду буквально на лівій половині, сортувати по праву половину. Добре. 578 00:47:51,770 --> 00:47:54,860 Будь-який, є все, що я можу потягнути ще? 579 00:47:54,860 --> 00:47:57,540 Або я дам одну хвилину. 580 00:47:58,210 --> 00:47:59,900 Добре. 581 00:47:59,900 --> 00:48:02,970 Будь-який, є щось, що ми можемо працювати з? 582 00:48:05,450 --> 00:48:09,680 Або ми будемо просто працювати з цим, а потім розгорніть звідти. 583 00:48:09,680 --> 00:48:14,050 >> Будь-який, є більше, ніж це, що я можу потягнути? 584 00:48:14,050 --> 00:48:17,770 [Студент] Так. Ви можете підтягти мої. >> Все правильно. 585 00:48:17,770 --> 00:48:19,730 Так! 586 00:48:22,170 --> 00:48:25,280 [Студент] Існували багато умов. >> О, чорт. Чи можете ви - 587 00:48:25,280 --> 00:48:28,110 [Студент] У мене є для його збереження. >> Да. 588 00:48:32,420 --> 00:48:35,730 Таким чином, ми дійсно робили злиття окремо. 589 00:48:35,730 --> 00:48:38,570 Так, але це не так уже й погано. 590 00:48:39,790 --> 00:48:41,650 Добре. 591 00:48:41,650 --> 00:48:47,080 Таким чином, рід сама просто дзвоню mergeSortHelp. 592 00:48:47,080 --> 00:48:49,530 Поясніть нам, що mergeSortHelp робить. 593 00:48:49,530 --> 00:48:55,700 [Студент] MergeSortHelp в значній мірі робить два основних етапи, 594 00:48:55,700 --> 00:49:01,270 яка є для сортування кожну половину масиву, а потім об'єднати їх обох. 595 00:49:04,960 --> 00:49:08,050 [Боуден] Гаразд, дайте мені секунду. 596 00:49:10,850 --> 00:49:13,210 Я думаю, що це - >> [студент] мені потрібно - 597 00:49:17,100 --> 00:49:19,400 Так. Я чогось не вистачає. 598 00:49:19,400 --> 00:49:23,100 У злитті, я розумію, що мені потрібно, щоб створити новий масив 599 00:49:23,100 --> 00:49:26,530 тому що я не міг зробити це на місці. >> Да. Ви не можете. Виправте. 600 00:49:26,530 --> 00:49:28,170 [Студент] Так я створюю новий масив. 601 00:49:28,170 --> 00:49:31,510 Я забув в кінці злиття з повторною зміниться. 602 00:49:31,510 --> 00:49:34,490 Добре. Ми потребуємо в новому масиві. 603 00:49:34,490 --> 00:49:41,000 В сортування злиттям, це майже завжди так. 604 00:49:41,000 --> 00:49:44,340 Частина витрат на кращий алгоритм часом мудрий 605 00:49:44,340 --> 00:49:47,310 Майже завжди необхідності використовувати трохи більше пам'яті. 606 00:49:47,310 --> 00:49:51,570 Так ось, незалежно від того, як ви це робите сортування злиттям, 607 00:49:51,570 --> 00:49:54,780 Вам неминуче доведеться використовувати додаткову пам'ять. 608 00:49:54,780 --> 00:49:58,240 Він або вона створює новий масив. 609 00:49:58,240 --> 00:50:03,400 І тоді ви говорите в кінці ми просто потрібно скопіювати новий масив у вихідному масиві. 610 00:50:03,400 --> 00:50:04,830 [Студент] Я так думаю, так. 611 00:50:04,830 --> 00:50:08,210 Я не знаю, якщо це працює з точки зору рахунку по посиланню або що завгодно, - 612 00:50:08,210 --> 00:50:11,650 Так, він буде працювати. >> [Студент] Добре. 613 00:50:20,620 --> 00:50:24,480 Чи знаєте ви спробувати запустити це? >> [Студент] Ні, ще ні. >> Добре. 614 00:50:24,480 --> 00:50:28,880 Спробуйте запустити його, і тоді я буду говорити про це на секунду. 615 00:50:28,880 --> 00:50:35,200 [Студент] Мені потрібно, щоб всі прототипи функцій і все, хоча, правда? 616 00:50:37,640 --> 00:50:40,840 Прототипи функцій. О, ти маєш на увазі - так. 617 00:50:40,840 --> 00:50:43,040 Сортувати кличе mergeSortHelp. 618 00:50:43,040 --> 00:50:47,390 >> Таким чином, для того, щоб сортувати подзвонити mergeSortHelp, mergeSortHelp повинні або були визначені 619 00:50:47,390 --> 00:50:56,370 Перед сортування або нам просто необхідно прототипу. Просто скопіюйте та вставте цього. 620 00:50:56,370 --> 00:50:59,490 І точно так само, mergeSortHelp викликає злиття, 621 00:50:59,490 --> 00:51:03,830 але злиття не був визначений, тому ми можемо просто дайте знати mergeSortHelp 622 00:51:03,830 --> 00:51:08,700 що це те, що злиття буде виглядати, ось і все. 623 00:51:09,950 --> 00:51:15,730 Так mergeSortHelp. 624 00:51:22,770 --> 00:51:32,660 У нас є проблема тут, де ми не маємо базовий варіант. 625 00:51:32,660 --> 00:51:38,110 MergeSortHelp рекурсивно, так що будь рекурсивної функції 626 00:51:38,110 --> 00:51:42,610 буде потрібно якусь підставу справа знати, коли зупинитися рекурсивно, що називає себе. 627 00:51:42,610 --> 00:51:45,590 Те, що наша база випадку буде тут? Так. 628 00:51:45,590 --> 00:51:49,110 [Студент] Якщо розмір 1? >> [Боуден] Так. 629 00:51:49,110 --> 00:51:56,220 Так що, як ми бачили, саме там, ми зупинилися розщеплення масивів 630 00:51:56,220 --> 00:52:01,850 як тільки ми отримали в масиви розміром 1, яка неминуче сортуються себе. 631 00:52:01,850 --> 00:52:09,530 Таким чином, якщо розмір дорівнює 1, ми знаємо, що масив вже відсортований, 632 00:52:09,530 --> 00:52:12,970 тому ми можемо просто повернутися. 633 00:52:12,970 --> 00:52:16,880 >> Зверніть увагу, що це порожнеча, так що ми нічого не повертають Зокрема, ми просто повертаємо. 634 00:52:16,880 --> 00:52:19,580 Добре. Так що це наш базовий сценарій. 635 00:52:19,580 --> 00:52:27,440 Я думаю, наш базовий сценарій також може бути, якщо ми, трапляється, злиття масив розміром 0, 636 00:52:27,440 --> 00:52:30,030 ми, ймовірно, хочете, щоб зупинити в якийсь момент, 637 00:52:30,030 --> 00:52:33,610 так що ми можемо тільки сказати, розміром менше 2 або менше або дорівнює 1 638 00:52:33,610 --> 00:52:37,150 так що це буде працювати для будь-якого масиву зараз. 639 00:52:37,150 --> 00:52:38,870 Добре. 640 00:52:38,870 --> 00:52:42,740 Так що це наш базовий сценарій. 641 00:52:42,740 --> 00:52:45,950 Тепер ви хочете йти з нами через злиття? 642 00:52:45,950 --> 00:52:49,140 Що означають всі ці випадки на увазі? 643 00:52:49,140 --> 00:52:54,480 Тут, нагорі, ми просто робимо ту ж ідею, - 644 00:52:56,970 --> 00:53:02,470 [Студент] Мені потрібно проходив розміру з усіма викликами mergeSortHelp. 645 00:53:02,470 --> 00:53:10,080 Я додав розмірі якості додаткового початкового і його там немає, як і розмір / 2. 646 00:53:10,080 --> 00:53:16,210 [Боуден] О, розмір / 2, розмір / 2. >> [Студент] Так, а також у наведеній вище функції, а також. 647 00:53:16,210 --> 00:53:21,320 [Боуден] Тут? >> [Студент] Так же розміру. >> [Боуден] Ох. Розмір, розмір? >> [Студент] Так. 648 00:53:21,320 --> 00:53:23,010 [Боуден] Добре. 649 00:53:23,010 --> 00:53:26,580 Дозвольте мені думати ні на секунду. 650 00:53:26,580 --> 00:53:28,780 Хіба ми зіткнулися з проблемою? 651 00:53:28,780 --> 00:53:33,690 Ми завжди лікуванні лівому як 0. >> [Студент] Немає 652 00:53:33,690 --> 00:53:36,340 Це неправильно теж. Вибачте. Це має бути початок. Так. 653 00:53:36,340 --> 00:53:39,230 [Боуден] Добре. Мені подобається, що краще. 654 00:53:39,230 --> 00:53:43,880 І кінця. Добре. 655 00:53:43,880 --> 00:53:47,200 Так що тепер ви хочете йти з нами через злиття? >> [Студент] Добре. 656 00:53:47,200 --> 00:53:52,150 Я просто йшов по цій новій масив, який я створив. 657 00:53:52,150 --> 00:53:57,420 Її розмір є розміром частині масиву, який ми хочемо бути відсортовані 658 00:53:57,420 --> 00:54:03,460 і намагається знайти елемент, який я повинен покласти в новий етап масиву. 659 00:54:03,460 --> 00:54:10,140 Таким чином, щоб зробити це, спочатку я перевіряю, якщо в лівій половині масиву продовжує мати більше елементів, 660 00:54:10,140 --> 00:54:14,260 і якщо це не так, то ви спускаєтеся до цього ще умова, яка просто говорить 661 00:54:14,260 --> 00:54:20,180 Добре, вона повинна бути в правильному масиві, і ми покладемо, що в поточному індексі newArray. 662 00:54:20,180 --> 00:54:27,620 >> А потім в іншому випадку, я перевіряю, якщо права частина масиву також закінчив, 663 00:54:27,620 --> 00:54:30,630 У цьому випадку я просто поклав у лівий. 664 00:54:30,630 --> 00:54:34,180 Це може і не бути необхідним. Я не впевнений. 665 00:54:34,180 --> 00:54:40,970 Але в будь-якому випадку, дві інші перевірки, який з двох менших в ліву чи праву. 666 00:54:40,970 --> 00:54:49,770 А також в кожному конкретному випадку, я збільшуючи залежності від того, заповнювач Я збільшуватися. 667 00:54:49,770 --> 00:54:52,040 [Боуден] Добре. 668 00:54:52,040 --> 00:54:53,840 Це виглядає добре. 669 00:54:53,840 --> 00:54:58,800 Хто-небудь є зауваження або питання чи проблеми? 670 00:55:00,660 --> 00:55:07,720 Таким чином, чотири випадки, що ми повинні принести речі в просто бути - чи це виглядає як п'ять - 671 00:55:07,720 --> 00:55:13,100 але ми повинні розглянути питання про лівому масиві закінчилися, що нам потрібно об'єднатися, 672 00:55:13,100 --> 00:55:16,390 Чи має право масиві закінчилися речі, які ми повинні об'єднати - 673 00:55:16,390 --> 00:55:18,400 Я вказуючи на нічого. 674 00:55:18,400 --> 00:55:21,730 Так чи лівий масив закінчилися речі або права масиві закінчилися речі. 675 00:55:21,730 --> 00:55:24,320 Ці два випадки. 676 00:55:24,320 --> 00:55:30,920 Ми також потребуємо тривіальному випадку, від того, що залишилося менше, ніж правильні речі. 677 00:55:30,920 --> 00:55:33,910 Тоді ми хочемо вибрати ліву річ. 678 00:55:33,910 --> 00:55:37,630 Ті випадки. 679 00:55:37,630 --> 00:55:40,990 Так що це було правильно, так от що. 680 00:55:40,990 --> 00:55:46,760 Масив залишилося. Це 1, 2, 3. Добре. Так що так, це ті чотири речі, які ми могли б зробити. 681 00:55:50,350 --> 00:55:54,510 І ми не будемо переходити рішення ітераційним. 682 00:55:54,510 --> 00:55:55,980 Я б не рекомендував - 683 00:55:55,980 --> 00:56:03,070 Злиття роду є прикладом функції, яка є одночасно не хвіст рекурсивної, 684 00:56:03,070 --> 00:56:07,040 це не так просто зробити його хвостовій рекурсією, 685 00:56:07,040 --> 00:56:13,450 але і це не дуже легко зробити ітеративним. 686 00:56:13,450 --> 00:56:16,910 Це дуже легко. 687 00:56:16,910 --> 00:56:19,170 Ця реалізація сортування злиттям, 688 00:56:19,170 --> 00:56:22,140 зливатися, що б ви не робили, ви збираєтеся побудувати злиття. 689 00:56:22,140 --> 00:56:29,170 >> Таким чином, сортування злиттям побудований на злитті рекурсивно саме ці три лінії. 690 00:56:29,170 --> 00:56:34,700 Итеративно, більш дратівливими і більш важко думати. 691 00:56:34,700 --> 00:56:41,860 Але зверніть увагу, що це не хвіст рекурсивної, так як mergeSortHelp - коли він називає себе - 692 00:56:41,860 --> 00:56:46,590 його ще потрібно робити речі, після цього повертається рекурсивних викликів. 693 00:56:46,590 --> 00:56:50,830 Так що цей кадр стека повинна продовжувати існувати навіть після виклику цього. 694 00:56:50,830 --> 00:56:54,170 А потім, коли ви називаєте це, стек повинен продовжувати існувати 695 00:56:54,170 --> 00:56:57,780 тому що навіть після цього виклику, ми все ще повинні зливатися. 696 00:56:57,780 --> 00:57:01,920 І це нетривіальна, щоб зробити цей хвіст рекурсивної. 697 00:57:04,070 --> 00:57:06,270 Питання? 698 00:57:08,300 --> 00:57:09,860 Добре. 699 00:57:09,860 --> 00:57:13,400 Таким чином, повертаючись до сортування - ой, є дві речі, які я хочу показати. Добре. 700 00:57:13,400 --> 00:57:17,840 Повертаючись до сортування, ми зробимо це швидко. 701 00:57:17,840 --> 00:57:21,030 Або шукати. Сортування? Сортування. Так. 702 00:57:21,030 --> 00:57:22,730 Повертаючись до витоків роду. 703 00:57:22,730 --> 00:57:29,870 Ми хочемо створити алгоритм, який сортує масив з використанням будь-якого алгоритму 704 00:57:29,870 --> 00:57:33,660 У O п. 705 00:57:33,660 --> 00:57:40,860 Так, як це можливо? Хто-небудь є які-небудь роду - 706 00:57:40,860 --> 00:57:44,300 Я натякнув, перш ніж на - 707 00:57:44,300 --> 00:57:48,300 Якщо ми збираємося поліпшити з п § п к о п, 708 00:57:48,300 --> 00:57:51,450 Ми поліпшили наш алгоритм часом мудрою, 709 00:57:51,450 --> 00:57:55,250 це означає, що ми збираємося потрібно зробити, щоб надолужити це? 710 00:57:55,250 --> 00:57:59,520 [Студент] простору. >> Да. Ми збираємося використовувати більше простору. 711 00:57:59,520 --> 00:58:04,490 І навіть не просто більше місця, це експоненціально більше простору. 712 00:58:04,490 --> 00:58:14,320 Так що я думаю, що цей тип алгоритму є те, псевдо, псевдо полінома - 713 00:58:14,320 --> 00:58:18,980 псевдо - Я не можу пригадати. Псевдо щось. 714 00:58:18,980 --> 00:58:22,210 Але це тому, що ми повинні використовувати так багато місця 715 00:58:22,210 --> 00:58:28,610 що це досяжно, але не реалістично. 716 00:58:28,610 --> 00:58:31,220 >> І як ми можемо цього досягти? 717 00:58:31,220 --> 00:58:36,810 Ми можемо добитися цього, якщо ми гарантуємо, що будь-який конкретний елемент масиву 718 00:58:36,810 --> 00:58:39,600 нижче певного розміру. 719 00:58:42,070 --> 00:58:44,500 Так що давайте просто скажемо, що розміри 200, 720 00:58:44,500 --> 00:58:48,130 будь-який елемент в масиві нижче розміру 200. 721 00:58:48,130 --> 00:58:51,080 І це насправді дуже реалістично. 722 00:58:51,080 --> 00:58:58,660 Ви можете дуже легко мати масив, що ви знаєте все, що в його 723 00:58:58,660 --> 00:59:00,570 буде менше, ніж деяке число. 724 00:59:00,570 --> 00:59:07,400 Подібно до цього, якщо у вас є абсолютно масивного векторного або щось 725 00:59:07,400 --> 00:59:11,810 але ви знаєте, все, що буде між 0 і 5, 726 00:59:11,810 --> 00:59:14,790 то це буде значно швидше це зробити. 727 00:59:14,790 --> 00:59:17,930 І пов'язаний ні по одному з елементів 5, 728 00:59:17,930 --> 00:59:21,980 так що ця оцінка, тобто, скільки пам'яті ви збираєтеся використовувати. 729 00:59:21,980 --> 00:59:26,300 Таким чином, межа 200. 730 00:59:26,300 --> 00:59:32,960 У теорії завжди є пов'язане, так як ціле може бути тільки до 4 млрд. 731 00:59:32,960 --> 00:59:40,600 але це нереально, так як тоді ми будемо з використанням космічних 732 00:59:40,600 --> 00:59:44,400 близько 4 млрд. доларів. Так що це нереально. 733 00:59:44,400 --> 00:59:47,060 Але тут ми будемо говорити наша оцінка є 200. 734 00:59:47,060 --> 00:59:59,570 Весь фокус у тому, щоб робити це в O п Тобто ми робимо ще один масив називається підрахунок розміру кордон. 735 00:59:59,570 --> 01:00:10,470 Таким чином, насправді, це ярлик для - Я насправді не знаю, якщо Clang це робить. 736 01:00:11,150 --> 01:00:15,330 Але в GCC, принаймні - я припускаючи, Clang робить це занадто - 737 01:00:15,330 --> 01:00:18,180 це буде просто ініціалізувати весь масив буде 0s. 738 01:00:18,180 --> 01:00:25,320 Так що, якщо я не хочу цього робити, то я міг би зробити окремо для (INT = 0; 739 01:00:25,320 --> 01:00:31,500 я 01:00:35,260 Так що тепер все встановлюється на 0. 741 01:00:35,260 --> 01:00:39,570 Я перебору мій масив, 742 01:00:39,570 --> 01:00:51,920 і те, що я роблю, я розраховую числа кожного - давай сюди. 743 01:00:51,920 --> 01:00:55,480 У нас є 4, 15, 16, 50, 8, 23, 42, 108. 744 01:00:55,480 --> 01:01:00,010 Що я розраховую число входжень кожного з цих елементів. 745 01:01:00,010 --> 01:01:03,470 Давайте насправді додати ще пару сюди з деякими повторюється. 746 01:01:03,470 --> 01:01:11,070 Таким чином, значення ми маємо тут, значення, яке буде масив [I]. 747 01:01:11,070 --> 01:01:14,850 Таким чином, вал може бути 4 або 8 або будь-який інший. 748 01:01:14,850 --> 01:01:18,870 І тепер я розраховую, скільки з цього значення, я бачив, 749 01:01:18,870 --> 01:01:21,230 так вважає [значення] + +; 750 01:01:21,230 --> 01:01:29,430 Після цього не буде зроблено, розраховує буде виглядати як 0001. 751 01:01:29,430 --> 01:01:42,190 Давайте зробимо підрахунок [значення] - ДОТРИМУВАТИСЬ + 1. 752 01:01:42,190 --> 01:01:48,230 >> Тепер це просто пояснити той факт, що ми, починаючи з 0. 753 01:01:48,230 --> 01:01:50,850 Таким чином, якщо 200 буде наш найбільший номер, 754 01:01:50,850 --> 01:01:54,720 Потім від 0 до 200 складає 201 речей. 755 01:01:54,720 --> 01:02:01,540 Таким чином, вважається, це буде виглядати як 00001, тому що у нас є один 4. 756 01:02:01,540 --> 01:02:10,210 Тоді ми будемо мати 0001, де ми будемо мати 1 у 8-му індекс кол. 757 01:02:10,210 --> 01:02:14,560 Ми будемо мати 2 в 23-й показник кол. 758 01:02:14,560 --> 01:02:17,630 Ми будемо мати 2 в індексі 42-й рахунок. 759 01:02:17,630 --> 01:02:21,670 Таким чином, ми можемо використовувати рахунки. 760 01:02:34,270 --> 01:02:44,920 Так num_of_item = імпульси [I]. 761 01:02:44,920 --> 01:02:52,540 І тому, якщо num_of_item дорівнює 2, це означає, що ми хочемо вставити 2 числа я 762 01:02:52,540 --> 01:02:55,290 в нашому масиві. 763 01:02:55,290 --> 01:03:02,000 Так що ми повинні відслідковувати, як далеко ми в масив. 764 01:03:02,000 --> 01:03:05,470 Таким чином, індекс = 0. 765 01:03:05,470 --> 01:03:09,910 Array - Я просто написати її. 766 01:03:16,660 --> 01:03:18,020 Графи - 767 01:03:19,990 --> 01:03:28,580 масив [індекс + +] = я; 768 01:03:28,580 --> 01:03:32,490 Це те, що я хочу? Я думаю, що те, що я хочу. 769 01:03:35,100 --> 01:03:38,290 Так, це добре виглядає. Добре. 770 01:03:38,290 --> 01:03:43,050 Так само всі розуміють, що мета мого масиву вважається таке? 771 01:03:43,050 --> 01:03:48,140 Це підрахунок числа входжень кожного з цих чисел. 772 01:03:48,140 --> 01:03:51,780 Тоді я ітерація, що має значення масиву, 773 01:03:51,780 --> 01:03:57,190 і ї позиції в масиві розраховує 774 01:03:57,190 --> 01:04:01,930 це число я ось що має з'явитися в моєму масиві. 775 01:04:01,930 --> 01:04:06,840 Ось чому пунктами 4, буде на 1 776 01:04:06,840 --> 01:04:11,840 і налічує від 8 буде 1, пунктами 23, буде 2. 777 01:04:11,840 --> 01:04:16,900 Так от, скільки з них я хочу вставити в мій масиві. 778 01:04:16,900 --> 01:04:19,200 Тоді я просто це зробити. 779 01:04:19,200 --> 01:04:28,960 Я вставка num_of_item я от в моєму масиві. 780 01:04:28,960 --> 01:04:31,670 >> Питання? 781 01:04:32,460 --> 01:04:43,100 І знову ж таки, це лінійний час, так як ми просто ітерації в цей раз, 782 01:04:43,100 --> 01:04:47,470 але це також лінійні в тому, що це число виявиться, 783 01:04:47,470 --> 01:04:50,730 і так в чому залежить від того, що ваша границя. 784 01:04:50,730 --> 01:04:53,290 З пов'язане 200, що не так уже й погано. 785 01:04:53,290 --> 01:04:58,330 Якщо межа буде 10000, то це трохи гірше, 786 01:04:58,330 --> 01:05:01,360 але якщо ваша пов'язаних буде 4 млрд., що це абсолютно нереально 787 01:05:01,360 --> 01:05:07,720 і цей масив буде мати, щоб бути розміром 4 мільярди доларів, що нереально. 788 01:05:07,720 --> 01:05:10,860 Так ось що. Питання? 789 01:05:10,860 --> 01:05:13,270 [Нерозбірливо відповідь студента] >> Гаразд. 790 01:05:13,270 --> 01:05:15,710 Я зрозумів одну річ, коли ми переживаємо. 791 01:05:17,980 --> 01:05:23,720 Я думаю, що проблема була в Лукаса і, напевно, кожен з нас бачив. 792 01:05:23,720 --> 01:05:26,330 Я зовсім забув. 793 01:05:26,330 --> 01:05:31,040 Єдине, що я хотів би прокоментувати, що, коли ви маєте справу з речами, як індекси, 794 01:05:31,040 --> 01:05:38,320 Ви ніколи не бачать цього, коли ви пишете цикл, 795 01:05:38,320 --> 01:05:41,120 але технічно, всякий раз, коли ви маєте справу з цими показниками, 796 01:05:41,120 --> 01:05:45,950 Ви повинні майже завжди справу з цілими числами без знака. 797 01:05:45,950 --> 01:05:53,850 Причина цього в тому, коли ви маєте справу з цілими числами, 798 01:05:53,850 --> 01:05:56,090 так що якщо у вас є 2 цілих чисел, і ви складете їх разом 799 01:05:56,090 --> 01:06:00,640 і вони в кінцевому підсумку занадто великий, то ви в кінцевому підсумку з негативним числом. 800 01:06:00,640 --> 01:06:03,410 Так ось що ціле переповнення. 801 01:06:03,410 --> 01:06:10,500 >> Якщо додати 2 млрд і 1 млрд, я в кінцевому підсумку з негативними 1 мільярд доларів. 802 01:06:10,500 --> 01:06:15,480 Ось як цілі працювати на комп'ютерах. 803 01:06:15,480 --> 01:06:17,510 Таким чином, проблема з використанням - 804 01:06:17,510 --> 01:06:23,500 Це нормально, за винятком, якщо низько, трапляється, 2 млрд і вище, трапляється, 1 млрд, 805 01:06:23,500 --> 01:06:27,120 то це буде негативний 1 млрд. і потім ми збираємося розділити це на 2 806 01:06:27,120 --> 01:06:29,730 і в кінцевому підсумку з негативною 500 мільйонів доларів. 807 01:06:29,730 --> 01:06:33,760 Так що це тільки питання, якщо вам трапиться бути пошук в масиві 808 01:06:33,760 --> 01:06:38,070 мільярди речей. 809 01:06:38,070 --> 01:06:44,050 Але якщо низько + до відбувається переповнювання, то це проблема. 810 01:06:44,050 --> 01:06:47,750 Як тільки ми їх без знака, потім 2 млрд. плюс 1 млрд. 3 млрд. доларів. 811 01:06:47,750 --> 01:06:51,960 3000000000 розділити на 2 становить 1,5 мільярда доларів. 812 01:06:51,960 --> 01:06:55,670 Тому, як тільки вони підписаний, все ідеально. 813 01:06:55,670 --> 01:06:59,900 І це теж проблема, коли ви пишете ваші цикли, 814 01:06:59,900 --> 01:07:03,940 а насправді, це, ймовірно, робить це автоматично. 815 01:07:09,130 --> 01:07:12,330 Це насправді просто кричати на вас. 816 01:07:12,330 --> 01:07:21,610 Так що, якщо це число занадто великим, щоб бути всього лише ціле число, але це буде вписуватися в ціле число без знака, 817 01:07:21,610 --> 01:07:24,970 вона буде кричати на вас, ось чому ви ніколи не зіштовхнетеся з проблемою. 818 01:07:29,150 --> 01:07:34,820 Ви можете бачити, що індекс ніколи не буде негативним, 819 01:07:34,820 --> 01:07:39,220 і тому, коли ви ітерації по масиву, 820 01:07:39,220 --> 01:07:43,970 Ви можете майже завжди говорять непідписаних Int я, але ви дійсно не потрібно. 821 01:07:43,970 --> 01:07:47,110 Справи йдуть працювати в значній мірі так само добре. 822 01:07:48,740 --> 01:07:50,090 Добре. [Пошепки] Скільки зараз часу? 823 01:07:50,090 --> 01:07:54,020 Останнє, що я хотів показати, - і я буду просто робити це дуже швидко. 824 01:07:54,020 --> 01:08:03,190 Ви знаєте, як ми # визначити таким чином ми можемо визначити # MAX, як 5 або ще що-небудь? 825 01:08:03,190 --> 01:08:05,940 Давайте не будемо робити MAX. # Визначити пов'язаний як 200. Це те, що ми робили раніше. 826 01:08:05,940 --> 01:08:10,380 Це визначає постійне, яка тільки збирається бути скопійований і вставлений 827 01:08:10,380 --> 01:08:13,010 де б ми не трапилося, щоб написати пов'язані. 828 01:08:13,010 --> 01:08:18,189 >> Так що ми дійсно можемо зробити більше з # визначає. 829 01:08:18,189 --> 01:08:21,170 Ми можемо визначити функції #. 830 01:08:21,170 --> 01:08:23,410 Вони насправді не функції, але ми будемо називати їх функцій. 831 01:08:23,410 --> 01:08:36,000 Прикладом може бути щось на зразок MAX (х, у) визначається як (х <у у: х). Добре. 832 01:08:36,000 --> 01:08:40,660 Таким чином, ви повинні звикнути до потрійної синтаксис оператора, 833 01:08:40,660 --> 01:08:49,029 але х менше, ніж у? Повернутися в, ще повернуться х. 834 01:08:49,029 --> 01:08:54,390 Таким чином, ви можете бачити ви можете зробити це окремою функцією, 835 01:08:54,390 --> 01:09:01,399 і функція може бути як BOOL MAX займає 2 аргументів, повернути це. 836 01:09:01,399 --> 01:09:08,340 Це один з найбільш поширених з них я бачу, як це зробити. Ми називаємо їх макросів. 837 01:09:08,340 --> 01:09:11,790 Це макрос. 838 01:09:11,790 --> 01:09:15,859 Це тільки синтаксис для цього. 839 01:09:15,859 --> 01:09:18,740 Ви можете написати макрос, щоб зробити все, що ви хочете. 840 01:09:18,740 --> 01:09:22,649 Ви часто бачите макроси для налагодження printfs та інше. 841 01:09:22,649 --> 01:09:29,410 Таким чином, тип Printf, існують спеціальні константи в C, як підкреслюють ЛІНІЯ підкреслення, 842 01:09:29,410 --> 01:09:31,710 2 підкреслює ЛІНІЯ підкреслення, 843 01:09:31,710 --> 01:09:37,550 і є також я думаю, що 2 підкреслення FUNC. Це могло б бути. Щось на зразок цього. 844 01:09:37,550 --> 01:09:40,880 Ці речі будуть замінені на ім'я функції 845 01:09:40,880 --> 01:09:42,930 або номер рядка, що ви перебуваєте. 846 01:09:42,930 --> 01:09:48,630 Часто, ви пишете налагодження printfs, що тут я міг би просто написати 847 01:09:48,630 --> 01:09:54,260 Налагодження і він буде друкувати номер рядка та функції, які я опинитися в 848 01:09:54,260 --> 01:09:57,020 що вона зустрічається, що DEBUG заяві. 849 01:09:57,020 --> 01:09:59,550 І ви також можете роздрукувати інших речей. 850 01:09:59,550 --> 01:10:05,990 Таким чином, єдине, що ви повинні стежити за то, якщо я, трапляється, # визначити DOUBLE_MAX 851 01:10:05,990 --> 01:10:11,380 як щось подібне до 2 * у і 2 * х. 852 01:10:11,380 --> 01:10:14,310 Так з якої причини, ви, виявляється, зробити це багато. 853 01:10:14,310 --> 01:10:16,650 Так що зробіть це макрос. 854 01:10:16,650 --> 01:10:18,680 Це дійсно зламаний. 855 01:10:18,680 --> 01:10:23,050 Я б назвав це, роблячи щось на зразок DOUBLE_MAX (3, 6). 856 01:10:23,050 --> 01:10:27,530 Отже, що має бути повернуто? 857 01:10:28,840 --> 01:10:30,580 [Студент] 12. 858 01:10:30,580 --> 01:10:34,800 Так, 12 повинні бути повернуті, і 12 повертається. 859 01:10:34,800 --> 01:10:43,350 3 замінюється на х, 6 замінюється на в, і ми повертаємося 2 * 6, що на 12. 860 01:10:43,350 --> 01:10:47,710 А що з цього приводу? Що має бути повернуто? 861 01:10:47,710 --> 01:10:50,330 [Студент] 14. >> В ідеалі, 14. 862 01:10:50,330 --> 01:10:55,290 Справа в тому, що, як хеш визначає роботу, пам'ятайте, що це буквальне копіювання і вставка 863 01:10:55,290 --> 01:11:00,160 в значній мірі все, так що це буде інтерпретуватися як 864 01:11:00,160 --> 01:11:11,270 в 3 менше, ніж 1 плюс 6, 2 рази 1 плюс 6, 2 рази 3. 865 01:11:11,270 --> 01:11:19,780 >> Таким чином, з цієї причини ви майже завжди обернути все в круглих дужках. 866 01:11:22,180 --> 01:11:25,050 Будь-яка змінна, ви майже завжди обернути в дужки. 867 01:11:25,050 --> 01:11:29,570 Є випадки, коли вам не доведеться, як я знаю, що мені не потрібно, щоб зробити це тут 868 01:11:29,570 --> 01:11:32,110 тому, що менше, ніж в значній мірі завжди просто ходити на роботу, 869 01:11:32,110 --> 01:11:34,330 Незважаючи на те, що може навіть не бути правдою. 870 01:11:34,330 --> 01:11:41,870 Якщо є щось смішне, як DOUBLE_MAX (1 == 2), 871 01:11:41,870 --> 01:11:49,760 те, що відбувається, щоб замінити 3 менше, ніж 1 дорівнює дорівнює 2, 872 01:11:49,760 --> 01:11:53,460 і так, то це буде зробити 3 менше 1, чи означає це, що дорівнює 2, 873 01:11:53,460 --> 01:11:55,620 які не те, що ми хочемо. 874 01:11:55,620 --> 01:12:00,730 Таким чином, з метою запобігання будь-якого оператора пріоритет проблеми, 875 01:12:00,730 --> 01:12:02,870 завжди обернути в дужки. 876 01:12:03,290 --> 01:12:07,700 Добре. І ось воно, 5:30. 877 01:12:08,140 --> 01:12:12,470 Якщо у вас є питання по PSET, дайте нам знати. 878 01:12:12,470 --> 01:12:18,010 Це має бути весело, і хакером видання також є набагато більш реалістичним 879 01:12:18,010 --> 01:12:22,980 ніж хакером видання минулого року, так що ми сподіваємося, що багато хто з вас спробувати. 880 01:12:22,980 --> 01:12:26,460 У минулому році було дуже переважною. 881 01:12:28,370 --> 01:12:30,000 >> [CS50.TV]