1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> СПІКЕР 1: Привіт всім! 3 00:00:12,300 --> 00:00:13,890 Ласкаво просимо в розділ. 4 00:00:13,890 --> 00:00:17,480 Так рада, що так багато з вас як тут, і кожен, хто дивиться онлайн. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Так, як звичайно Ласкаво просимо. 7 00:00:20,920 --> 00:00:24,360 Я сподіваюся, що ви всі були прекрасні вихідні, повні відпочинку, релаксації. 8 00:00:24,360 --> 00:00:26,026 Це було красиво вчора. 9 00:00:26,026 --> 00:00:27,525 Так що, я сподіваюся, вам сподобалася на відкритому повітрі. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Отже, спочатку пару оголошень. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Класифікація. 14 00:00:32,700 --> 00:00:37,350 Так, більшість з вас мав отримати по електронній пошті від мене про ваше подряпин Pset, 15 00:00:37,350 --> 00:00:39,920 а також класифікації для Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Так, тільки пара речей. 18 00:00:42,220 --> 00:00:45,150 Обов'язково використовуйте check50 в style50. 19 00:00:45,150 --> 00:00:47,250 Вони призначені, щоб бути Ресурси для вас, хлопці, 20 00:00:47,250 --> 00:00:50,660 щоб переконатися, що ви отримуєте якомога більше очок, як ви можете 21 00:00:50,660 --> 00:00:52,390 без потреби втрачати їх. 22 00:00:52,390 --> 00:00:54,407 Так, такі речі, як стиль дуже важливі. 23 00:00:54,407 --> 00:00:55,740 Ми збираємося зняти для нього. 24 00:00:55,740 --> 00:00:58,115 Деякі з вас, можливо, вже зауважив, що від вашого Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 І check50 просто дійсно простий спосіб, щоб переконатися, 27 00:01:01,450 --> 00:01:05,050 що ми насправді повернення того, що повинен бути повернутий користувачеві, 28 00:01:05,050 --> 00:01:06,690 і що все працює правильно. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> На другому ноті, переконайтеся, що ваш завантаження речей в потрібну папку. 31 00:01:12,040 --> 00:01:14,470 Це робить моє життя тільки Трохи складніше 32 00:01:14,470 --> 00:01:18,836 якщо ви завантажуєте Pset 2 в Pset 1 тому що, коли я завантажити речі, 33 00:01:18,836 --> 00:01:20,085 вони не скачати правильно. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 І я знаю, що це трохи хиткий в системі, щоб звикнути до, 36 00:01:24,560 --> 00:01:26,950 але просто супер обережні, якщо тільки для мене, 37 00:01:26,950 --> 00:01:30,080 так що, коли ви отримуєте листи на як 2 ранку і я градація. 38 00:01:30,080 --> 00:01:33,710 Якщо не викликати у мене є, щоб подивитися все навколо для вашого Pset. 39 00:01:33,710 --> 00:01:34,440 Прохолодний. 40 00:01:34,440 --> 00:01:37,270 >> Я знаю, що це рано, але я повністю були взяті зненацька 41 00:01:37,270 --> 00:01:40,800 по есе, це через це в п'ятницю, то мої професори були просто подобається, о да. 42 00:01:40,800 --> 00:01:42,550 Пам'ятайте, у вас є есе за п'ятницю. 43 00:01:42,550 --> 00:01:45,780 Так, я знаю, ніхто не любить думати про проміжні вибори, 44 00:01:45,780 --> 00:01:50,620 але ваш перший вікторина на 15 жовтня які жовтня розпочинає на цьому тижні. 45 00:01:50,620 --> 00:01:53,290 Так, це може бути раніше ніж ви очікували всі. 46 00:01:53,290 --> 00:01:57,510 Так що ви не кинули зненацька, коли Я вже розділ на наступному тижні, що о, 47 00:01:57,510 --> 00:02:00,560 ваш тест на наступному тижні, я думав, Я хотів би дати вам трохи більше 48 00:02:00,560 --> 00:02:01,500 з керівників зараз. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Так, встановлено, ваша проблема, номер три. 51 00:02:04,660 --> 00:02:07,070 Як люди читали спец з цікавості? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 Добре. 54 00:02:09,199 --> 00:02:10,229 Ми отримали декілька. 55 00:02:10,229 --> 00:02:12,320 Вид вниз з минулого тиждень, але це нормально. 56 00:02:12,320 --> 00:02:13,650 Я знаю, що це було красиво поза. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Так Break Out. 59 00:02:16,660 --> 00:02:21,010 Виразно, після ви зробили сьогодні прочитав вашу специфікацію по крайней мере, 60 00:02:21,010 --> 00:02:25,240 спробуйте, як скачування Код розподілу і працює 61 00:02:25,240 --> 00:02:27,430 як в перший ініціал річ, що вони питають вас. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Так як ми використовуємо Код розподілу і бібліотека 64 00:02:32,590 --> 00:02:36,790 що ми тільки using-- --Она ​​тільки Вдруге ми зробили це Pset, 65 00:02:36,790 --> 00:02:38,650 божевільні речі можуть відбутися з Вашої машини, 66 00:02:38,650 --> 00:02:41,370 і ви хочете, щоб знайти, що прямо зараз порівняно з пізніше. 67 00:02:41,370 --> 00:02:45,570 >> Тому що, якщо це в четвер ввечері або це В середу ввечері, і почему- 68 00:02:45,570 --> 00:02:48,912 Ваш прилад просто не хочу працювати з бібліотекою 69 00:02:48,912 --> 00:02:50,620 або з розподілом Код, який засобу 70 00:02:50,620 --> 00:02:52,309 Ви не можете навіть почати робити кодування. 71 00:02:52,309 --> 00:02:54,100 Тому що ви не можете перевірити щоб побачити, якщо він працює. 72 00:02:54,100 --> 00:02:55,975 Ваш не збираюся бути в змозі щоб побачити, якщо він збирає. 73 00:02:55,975 --> 00:03:00,500 Ви хочете, щоб піклуватися про тих, на початку тиждень, коли ви все ще можете написати мені 74 00:03:00,500 --> 00:03:03,100 або один з інших ТФ, і ми можемо отримати ті фіксованою. 75 00:03:03,100 --> 00:03:05,410 Тому що ті питання, що збираються, щоб зупинити вас 76 00:03:05,410 --> 00:03:07,120 від будь-якого реального прогресу. 77 00:03:07,120 --> 00:03:10,055 Це не так, як одна помилка, що Ви можете тільки почасти пропустити. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Якщо у вас виникли проблеми з вашим Прилад або код розподіл, 80 00:03:13,420 --> 00:03:16,211 Ви дійсно хочете, щоб що прийнято дбати про швидше раніше, ніж пізніше. 81 00:03:16,211 --> 00:03:20,410 Так що навіть якщо ви не збираєтеся насправді почати кодування, завантажити дистрибутив 82 00:03:20,410 --> 00:03:24,040 Код, прочитати специфікацію, переконайтеся все працює там. 83 00:03:24,040 --> 00:03:25,134 Добре? 84 00:03:25,134 --> 00:03:27,675 Якщо ви можете просто зробити це, я обіцяю вам життя буде легше. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 І так ви, ймовірно, зробити це прямо зараз не так? 87 00:03:31,410 --> 00:03:32,100 Добре. 88 00:03:32,100 --> 00:03:33,950 Таким чином, будь-які питання там? 89 00:03:33,950 --> 00:03:35,850 Будь-які логістичні речі? 90 00:03:35,850 --> 00:03:36,910 Все добре? 91 00:03:36,910 --> 00:03:38,270 Добре. 92 00:03:38,270 --> 00:03:41,700 >> Відмова від відповідальності для тих з Ви в кімнаті і на сайті. 93 00:03:41,700 --> 00:03:45,437 Я збираюся намагатися переключити між PowerPoint в приладі 94 00:03:45,437 --> 00:03:47,270 тому що ми збираємося бути робити деякі кодування 95 00:03:47,270 --> 00:03:53,630 сьогодні на численні прохання з анонімного Пропозиція опитування я розіслав минулого тижня. 96 00:03:53,630 --> 00:03:55,480 Таким чином, ми будемо робити деякі кодування. 97 00:03:55,480 --> 00:03:57,800 Так що, якщо ви, хлопці, теж хочу щоб запустити ваші прилади, 98 00:03:57,800 --> 00:04:02,910 і ви повинні їсти по електронній пошті від мене, з файлом зразка. 99 00:04:02,910 --> 00:04:04,310 Будь ласка, не соромтеся зробити це. 100 00:04:04,310 --> 00:04:07,340 >> Так, ми збираємося говорити про GDB, який є відладчик. 101 00:04:07,340 --> 00:04:09,970 Це допоможе вам вид з'ясувати, де 102 00:04:09,970 --> 00:04:11,860 справи йдуть не так у вашому коді. 103 00:04:11,860 --> 00:04:15,370 Це просто спосіб для вас крок за кодом, як це відбувається, 104 00:04:15,370 --> 00:04:19,100 і мати можливість роздрукувати змінні або подивитися, що відбувається насправді 105 00:04:19,100 --> 00:04:22,980 під капот вірші програму просто працює, це як розломів, 106 00:04:22,980 --> 00:04:25,030 і ви, як, не маючи уявлення, що тільки що відбулося тут. 107 00:04:25,030 --> 00:04:26,730 Я не знаю, що лінія його не вдалося в. 108 00:04:26,730 --> 00:04:29,040 Я не знаю, де пішло не так. 109 00:04:29,040 --> 00:04:31,280 Так, GDB допомагатиме вам у цьому. 110 00:04:31,280 --> 00:04:35,240 Крім того, якщо ви вирішите продовжити да, і прийняти 61, 111 00:04:35,240 --> 00:04:38,430 це буде дуже, дуже б ваш кращий друг, бо я можу вам сказати, 112 00:04:38,430 --> 00:04:40,840 бо я збираюся через цього класу. 113 00:04:40,840 --> 00:04:43,620 >> Ми будемо дивитися на довічним Пошук, який, якщо ви, хлопці, пам'ятайте 114 00:04:43,620 --> 00:04:47,540 Відмінний приклад телефонна книга Видовище з класу. 115 00:04:47,540 --> 00:04:50,620 Ми будемо реалізації, що і ходити через що трохи більше, 116 00:04:50,620 --> 00:04:54,650 а потім ми збираємося через чотири різні види, які Bubble, 117 00:04:54,650 --> 00:04:56,285 Вибір, вставки, і об'єднати. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Прохолодний. 120 00:04:58,330 --> 00:05:00,390 Так, GDB, як я вже казав, це відладчик. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 І це свого роду великий речі, великі функції або команди 123 00:05:09,370 --> 00:05:13,240 що ви використовуєте в GDB, і буду ходити Ви через демо ній в секунду. 124 00:05:13,240 --> 00:05:15,360 >> Таким чином, це не просто збираюся залишитися реферат. 125 00:05:15,360 --> 00:05:18,000 Я постараюся і зробити його як бетон наскільки це можливо для вас, хлопці. 126 00:05:18,000 --> 00:05:19,870 Так, зламати. 127 00:05:19,870 --> 00:05:22,200 Це буде прорив небудь як, деяке число, яке 128 00:05:22,200 --> 00:05:26,900 являє собою рядок у вашій програмі, або ви можете назвати функцію. 129 00:05:26,900 --> 00:05:30,150 Так що, якщо ви говорите, зламати основний, він зупиниться на головній, 130 00:05:30,150 --> 00:05:32,400 і нехай ви йдете через цю функцію. 131 00:05:32,400 --> 00:05:36,350 >> Точно так же, якщо у вас є якась зовнішня функціонувати як своп або Cube, 132 00:05:36,350 --> 00:05:38,450 що ми дивилися минулого тижня. 133 00:05:38,450 --> 00:05:41,780 Якщо ви говорите, порушить одну з тих, всякий раз, коли ваша програма потрапляє, що, 134 00:05:41,780 --> 00:05:44,290 це буду чекати тебе, щоб скажіть йому, що робити. 135 00:05:44,290 --> 00:05:47,860 Перш, ніж це буде просто виконати так вам може насправді крок всередині функції 136 00:05:47,860 --> 00:05:49,020 і подивитися, що відбувається. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Так, наступний, просто пропускає Наступний рядок, переходить функцій. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Крок. 141 00:05:55,560 --> 00:05:56,810 Це все трохи абстрактний. 142 00:05:56,810 --> 00:06:00,530 Так, я тільки збираюся бігти через них, але ви побачите їх у використанні в секунду. 143 00:06:00,530 --> 00:06:01,810 >> Крок в залежності. 144 00:06:01,810 --> 00:06:04,170 Так як я вже казав, як з своп, це було б 145 00:06:04,170 --> 00:06:07,110 дозволяють насправді, як ніби ти як фізично активізації всередині, 146 00:06:07,110 --> 00:06:10,990 Ви можете зв'язуватися з цими змінними, друк те, що вони, бачите, що відбувається. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Список буде буквально друку з навколишнього коду. 149 00:06:14,830 --> 00:06:17,570 Так що, якщо ви начебто забути де ви знаходитесь у вашій програмі, 150 00:06:17,570 --> 00:06:19,880 або вам цікаво що відбувається навколо нього, 151 00:06:19,880 --> 00:06:23,790 це буде просто роздрукувати сегмент з подобаються п'ять чи шість ліній навколо нього. 152 00:06:23,790 --> 00:06:26,080 Таким чином, ви можете зорієнтуватися про те, де ви знаходитесь. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Роздрукувати деякі змінні. 155 00:06:28,650 --> 00:06:34,590 Так що, якщо у вас є ключ, як в Цезаря, що ми будемо дивитися на. 156 00:06:34,590 --> 00:06:36,220 Ви можете сказати, друку Key в будь-який момент. 157 00:06:36,220 --> 00:06:40,070 Це вам скажу, що це значення так що, може бути, десь по дорозі, 158 00:06:40,070 --> 00:06:42,070 Ви переписав свій ключ. 159 00:06:42,070 --> 00:06:45,495 Ви дійсно можете сказати, що через Ви можете фактично спостерігати це значення. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> У місцевих жителів, всього принтами з локальних змінних. 162 00:06:48,780 --> 00:06:53,120 Так, в будь-який час ви в циклі, і ви просто хочете, щоб побачити, як, ой. 163 00:06:53,120 --> 00:06:54,270 Яка моя я? 164 00:06:54,270 --> 00:06:57,020 Що це ключова цінність що я инициализировать тут? 165 00:06:57,020 --> 00:06:58,537 Що таке повідомлення в цій точці? 166 00:06:58,537 --> 00:07:00,370 Це буде просто роздрукувати всі з тих, так що вам 167 00:07:00,370 --> 00:07:04,330 не повинні індивідуально кажуть, друку I. друку повідомлення. 168 00:07:04,330 --> 00:07:04,970 Друк Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 А потім Дисплей. 171 00:07:07,700 --> 00:07:10,370 Те, що це робить, як ви крок в рамках програми, 172 00:07:10,370 --> 00:07:13,980 це просто щоб переконатися, що це відображення деяких певну змінну 173 00:07:13,980 --> 00:07:14,780 в кожній точці. 174 00:07:14,780 --> 00:07:17,160 Так що ви also-- --Она ​​це вид ярлика де 175 00:07:17,160 --> 00:07:19,530 Ви не повинні продовжувати йти, як, ой. 176 00:07:19,530 --> 00:07:23,150 Друк Key або друку I. Це просто автоматично зробить це за вас. 177 00:07:23,150 --> 00:07:25,959 >> Так, з тим, що ми збираємося щоб бачити, як це йде. 178 00:07:25,959 --> 00:07:28,000 Я збираюся спробувати і перемикач в мій прилад. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Дивіться, якщо я можу зробити це. 181 00:07:31,271 --> 00:07:31,770 Все. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Ми просто збираємося, щоб відобразити його. 184 00:07:42,370 --> 00:07:44,530 Там немає нічого, з глузду на моєму ноутбуці в будь-якому випадку. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 Добре. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Це має бути цей. 189 00:08:01,054 --> 00:08:01,795 Це настільки крихітні. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Давайте подивимося, якщо ми можемо зробити це. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> Добре. 194 00:08:10,940 --> 00:08:15,305 Аліса, очевидно, бореться тут чуть-чуть, 195 00:08:15,305 --> 00:08:17,995 але ми отримаємо її в Momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 Добре. 198 00:08:22,020 --> 00:08:25,900 Ми просто збираємося збільшити це. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 Добре. 201 00:08:29,380 --> 00:08:31,679 Може все начебто бачили? 202 00:08:31,679 --> 00:08:32,470 Може бути, трохи? 203 00:08:32,470 --> 00:08:33,594 Я знаю, це трохи мала. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Ви не можете достатньо з'ясувати як зробити це більше. 206 00:08:37,530 --> 00:08:38,350 Якщо хто-небудь знає. 207 00:08:38,350 --> 00:08:40,309 Хто-небудь знає, як зробити його більше? 208 00:08:40,309 --> 00:08:40,932 Добре. 209 00:08:40,932 --> 00:08:42,140 Ми збираємося звернути з нього. 210 00:08:42,140 --> 00:08:45,801 Не має значення, в будь-якому випадку, тому що це просто що код, який ви, хлопці, повинні 211 00:08:45,801 --> 00:08:46,300 є. 212 00:08:46,300 --> 00:08:48,310 >> Що більш важливо, є термінал тут. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 І тут ми маємо Чому так мало? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Установки. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 О. 219 00:09:08,420 --> 00:09:09,500 Правда Айк. 220 00:09:09,500 --> 00:09:10,880 Як це? 221 00:09:10,880 --> 00:09:11,770 З там. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Так краще для всіх? 224 00:09:21,810 --> 00:09:22,525 Добре,. 225 00:09:22,525 --> 00:09:23,025 Прохолодний. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Ви знаєте, коли ви знаходитесь в CS технічні труднощі класу 228 00:09:28,220 --> 00:09:32,971 є свого роду частиною the-- Так, давайте прояснимо це. 229 00:09:32,971 --> 00:09:33,470 Добре. 230 00:09:33,470 --> 00:09:38,060 Так, прямо тут, в розділі, які ми мали тут. 231 00:09:38,060 --> 00:09:40,830 Цезар являє собою виконуваний файл. 232 00:09:40,830 --> 00:09:41,800 Так що я зробив це. 233 00:09:41,800 --> 00:09:46,370 Так, одна річ, щоб зрозуміти, з GDB є що він працює тільки на виконуваних файлах. 234 00:09:46,370 --> 00:09:48,040 Таким чином, ви не можете запустити його на dotsy. 235 00:09:48,040 --> 00:09:50,532 Ви повинні реально зробити Переконайтеся, що ваш код компілюється, 236 00:09:50,532 --> 00:09:51,865 і що він насправді може працювати. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Отже, переконайтеся, що якщо це не так компіляції, отримати його для компіляції, 239 00:09:56,186 --> 00:09:57,810 так що ви можете роду проходять через нього. 240 00:09:57,810 --> 00:10:04,590 Отже, для початку GDB, все, що вам робити, Глорія типу GDB, а потім просто 241 00:10:04,590 --> 00:10:06,250 файл, який ви хочете. 242 00:10:06,250 --> 00:10:08,240 Я завжди опечатки Цезаря. 243 00:10:08,240 --> 00:10:11,730 Але ви хочете, щоб переконатися, так як це виконуваний, 244 00:10:11,730 --> 00:10:14,210 Точка спалаху Ті так що означає, що ви йдете 245 00:10:14,210 --> 00:10:19,240 запустити CSI ви збираєтеся виконати це файли або за допомогою відладчика. 246 00:10:19,240 --> 00:10:19,910 Добре. 247 00:10:19,910 --> 00:10:22,885 Так, ви що, ви отримуєте цей вид тарабарщина. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Це просто всі речі про відладчика. 250 00:10:25,750 --> 00:10:28,200 Ви дійсно не потрібно турбуватися про це прямо зараз. 251 00:10:28,200 --> 00:10:31,460 І, як ви бачите, у нас є це відкриті круглі дужки, ВВП, близькі круглі дужки, 252 00:10:31,460 --> 00:10:34,690 і тільки почасти схожий наша командна рядок, чи не так? 253 00:10:34,690 --> 00:10:37,010 >> Отже, що ж ми хочемо do-- --So, Перше, що 254 00:10:37,010 --> 00:10:39,570 це ми хочемо вибрати місце, щоб розбити його. 255 00:10:39,570 --> 00:10:42,332 Так, є одна помилка У цій програмі Цезар 256 00:10:42,332 --> 00:10:44,290 що я представляю, що ми збираємося з'ясувати. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 Це Що вона робить, це він приймає на вхід Barfoo заголовними буквами, і почему- 259 00:10:56,350 --> 00:11:01,950 це не міняє А. Це просто залишає тільки вона, все інше правильно, 260 00:11:01,950 --> 00:11:03,980 але друга буква Залишається незмінним. 261 00:11:03,980 --> 00:11:07,120 Так, ми збираємося, щоб спробувати з'ясувати, чому це. 262 00:11:07,120 --> 00:11:10,440 Так, перше, що ви, як правило, хочу зробити, коли ви починаєте на GDB 263 00:11:10,440 --> 00:11:12,010 є з'ясувати, де розбити його. 264 00:11:12,010 --> 00:11:14,956 >> Так Цезар є досить коротка програма. 265 00:11:14,956 --> 00:11:16,330 Ми просто повинні одну функцію, чи не так? 266 00:11:16,330 --> 00:11:18,520 Що наша функція в Цезаря? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Там тільки одна функція, Головне правильно? 269 00:11:24,350 --> 00:11:26,490 Головна функція для всіх ваших програм. 270 00:11:26,490 --> 00:11:29,230 Якщо у вас не було Main, я міг би бути трохи хвилювався зараз, 271 00:11:29,230 --> 00:11:31,000 але я сподіваюся, що ви всі були Main там. 272 00:11:31,000 --> 00:11:34,150 Отже, що ми можемо зробити, це ми можемо просто розірвати Main, як і що. 273 00:11:34,150 --> 00:11:35,190 Так, він говорить, ОК. 274 00:11:35,190 --> 00:11:37,430 Ми ставимо нашу зупину один є. 275 00:11:37,430 --> 00:11:42,870 >> Так, в даний час пам'ятати, Цезар займає одне командної рядку аргументів право 276 00:11:42,870 --> 00:11:45,150 і ми не зробили, що ще ніде. 277 00:11:45,150 --> 00:11:47,560 Отже, що ж ви робите, коли Ви насправді йти працювати 278 00:11:47,560 --> 00:11:51,540 програма, будь-яка програма, що ти працює в GDB, який потребує командного рядка 279 00:11:51,540 --> 00:11:55,010 Аргументи, що ви збираєтеся вхід при першому запуску її запуску. 280 00:11:55,010 --> 00:11:59,280 Так, в даному випадку, ми робимо Запуск з ключем в три рази. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 І це буде насправді почати. 283 00:12:02,040 --> 00:12:08,480 >> Так що, якщо ви бачите тут, у нас є Якщо RC не дорівнює 2. 284 00:12:08,480 --> 00:12:12,210 Так що, якщо ви, хлопці, у всіх є що файл, який я розіслав до 285 00:12:12,210 --> 00:12:15,100 Ви побачите, що це як Перша лінія наша головна функція, чи не так? 286 00:12:15,100 --> 00:12:17,890 Це перевірка того, якщо у нас є правильну кількість аргументів. 287 00:12:17,890 --> 00:12:20,620 Так що, якщо вам цікаво, якщо RC правильно, 288 00:12:20,620 --> 00:12:23,250 Ви можете зробити щось так само, як для друку RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC дорівнює двом, який що ми очікували, чи не так? 291 00:12:28,640 --> 00:12:32,010 >> Так, ми можемо йти далі, і продовжувати до кінця. 292 00:12:32,010 --> 00:12:33,200 Так, у нас є деякі клавіші там. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 І ми можемо роздрукувати наш ключ щоб переконатися, що це правильно. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Цікаво. 297 00:12:39,500 --> 00:12:41,210 Не зовсім те, що ми очікували. 298 00:12:41,210 --> 00:12:44,810 Так, одна річ, щоб зрозуміти, з GDB також, є 299 00:12:44,810 --> 00:12:49,000 що це не поки ви не потрапили Далі, що лінія, що ви тільки що бачили 300 00:12:49,000 --> 00:12:50,720 насправді виконані. 301 00:12:50,720 --> 00:12:53,870 Так, в цьому випадку ключ не призначено ще. 302 00:12:53,870 --> 00:12:57,050 Так, Key деяке значення сміття що ви бачите на дні там. 303 00:12:57,050 --> 00:13:03,680 Від'ємний $ 120-- --Она ​​одного мільярда і щось дивні речі правильно? 304 00:13:03,680 --> 00:13:05,340 Це не той ключ, який ми очікували. 305 00:13:05,340 --> 00:13:10,720 Але якщо ми потрапили Далі, а потім ми спробуйте і ключ друку, це три. 306 00:13:10,720 --> 00:13:11,710 >> Все це бачили? 307 00:13:11,710 --> 00:13:13,780 Так що, якщо ви отримуєте щось що ви, як, чекати. 308 00:13:13,780 --> 00:13:15,540 Це повністю не так, і я не знаю, 309 00:13:15,540 --> 00:13:20,150 як це відбуватиметься, тому що все, що я хочу зробити, це призначити номер, змінна, 310 00:13:20,150 --> 00:13:22,900 спробуйте натиснути Далі, спробуйте друк це знову, щоб побачити, якщо це працює. 311 00:13:22,900 --> 00:13:27,830 Бо це тільки збирається виконати і фактично призначити щось після вас 312 00:13:27,830 --> 00:13:29,340 хіт Далі. 313 00:13:29,340 --> 00:13:30,336 Зробити сенс для всіх? 314 00:13:30,336 --> 00:13:30,836 Угу? 315 00:13:30,836 --> 00:13:33,220 >> СПІКЕР 2: Коли ви випадковим номера, що це означає? 316 00:13:33,220 --> 00:13:34,790 >> СПІКЕР 1: Це просто випадковий. 317 00:13:34,790 --> 00:13:35,710 Це просто сміття. 318 00:13:35,710 --> 00:13:38,320 Це просто щось, що ваш Комп'ютер випадковим чином привласнити. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Прохолодний. 321 00:13:40,220 --> 00:13:45,760 Отже, тепер ми можемо рухатися через, і так Тепер у нас є цей простий текстовий GetString. 322 00:13:45,760 --> 00:13:48,600 Отже, дозвольте мені просто ввести що відбудеться, коли ми потрапили Далі тут. 323 00:13:48,600 --> 00:13:51,320 Наша GDB вид зникає, чи не так? 324 00:13:51,320 --> 00:13:55,720 Це тому, що GetString Тепер виконання, чи не так? 325 00:13:55,720 --> 00:14:01,460 Так, коли ми побачили звичайний текст дорівнює GetString, відкриті круглі дужки і круглі дужки, 326 00:14:01,460 --> 00:14:04,380 і ми потрапили Далі, що має фактично виконано зараз. 327 00:14:04,380 --> 00:14:06,580 Так, він чекає нам вхідного щось. 328 00:14:06,580 --> 00:14:13,560 >> Так, ми збираємося ввести нашу їжу, яка є те, що він зазнає невдачі, як я сказав вам, 329 00:14:13,560 --> 00:14:18,020 і що як раз говорить, що це закінчив роботу, що закриті 330 00:14:18,020 --> 00:14:19,980 Кронштейн означає, що це виходу з цього циклу. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Так, ми можемо вдарити Далі, і зараз, як я що ви всі знайомі з Цезарем, 333 00:14:25,420 --> 00:14:27,260 це, що ця лінія збирається робити. 334 00:14:27,260 --> 00:14:32,030 Це для Int я дорівнює 0, N дорівнює STRLEN, простий текст, а потім 335 00:14:32,030 --> 00:14:33,960 Я менше п, я, плюс, плюс. 336 00:14:33,960 --> 00:14:35,210 Що це петля збираєтеся робити? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Відкрийте ваше повідомлення. 339 00:14:39,160 --> 00:14:39,770 Прохолодний. 340 00:14:39,770 --> 00:14:41,330 Так, давайте почнемо це робити. 341 00:14:41,330 --> 00:14:47,210 >> Так, якщо це умова збігаються, для нашого першого? 342 00:14:47,210 --> 00:14:52,250 Якщо це B, це звичайний текст І. Ми можна отримати інформацію про наших місцевих жителів. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Таким чином, я дорівнює нулю, а якщо шість, який ми очікуємо, і наш ключ три. 345 00:14:57,970 --> 00:14:59,227 Все, що має сенс, чи не так? 346 00:14:59,227 --> 00:15:01,310 Ці цифри все саме те, що вони повинні бути. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Так, наспівувати? 349 00:15:03,870 --> 00:15:05,620 СПІКЕР 3: У мене є випадкові числа для шахти. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 СПІКЕР 1: Ну, ми можемо check-- --Ми може поговорити про те, що в одну секунду. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Але ви повинні отримувати це. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Так що, якщо у нас є капітал У нашій першій, 356 00:15:20,130 --> 00:15:22,080 ця умова має зловити його, чи не так? 357 00:15:22,080 --> 00:15:27,120 Так що, якщо ми потрапили Далі, ми бачимо, що це Якщо насправді виконує. 358 00:15:27,120 --> 00:15:29,220 Тому що, якщо ви прямуєте разом в коді, 359 00:15:29,220 --> 00:15:33,460 ця лінія тут, де звичайний текст я замінюється цієї арифметики, 360 00:15:33,460 --> 00:15:35,720 виконується тільки в If умова правильного право? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB тільки збираюся показати вам, речі, які насправді виконавці. 363 00:15:40,240 --> 00:15:45,140 Так що якщо це умова Якщо не було виконано, це просто хочу, щоб перейти до наступного рядка. 364 00:15:45,140 --> 00:15:46,540 Добре? 365 00:15:46,540 --> 00:15:48,510 Так, у нас є що. 366 00:15:48,510 --> 00:15:51,171 Цей кронштейн означає, що це закритий з цієї петлі тепер. 367 00:15:51,171 --> 00:15:52,420 Так, він збирається почати знову. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Так само, як, що. 370 00:15:56,280 --> 00:15:59,120 Так, що ми можемо отримати інформацію про наших місцевих жителів тут, 371 00:15:59,120 --> 00:16:02,575 і ми бачимо, що наша перша Лист змінилося, чи не так? 372 00:16:02,575 --> 00:16:05,150 Це зараз E, як і має бути. 373 00:16:05,150 --> 00:16:07,360 Так, ми можемо продовжувати. 374 00:16:07,360 --> 00:16:08,500 >> І у нас є цей чек. 375 00:16:08,500 --> 00:16:09,916 І ця перевірка повинна працювати, чи не так? 376 00:16:09,916 --> 00:16:12,570 Це А. Це має бути змінене три букви вперед. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Але якщо ви помітили, ми отримати щось інше. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Таким чином, в цьому випадку тут, він зловив це і так ця лінія виконана, 381 00:16:22,860 --> 00:16:28,620 які змінені наш B. Але, в цьому випадку тут, 382 00:16:28,620 --> 00:16:32,860 у нас є, що він просто пропустив його, і пішов в [? L Сіфф. ?] 383 00:16:32,860 --> 00:16:34,660 Так щось там відбувається. 384 00:16:34,660 --> 00:16:37,780 Те, що це говорить вам, що, ми знаємо, що він повинен зловити тут, 385 00:16:37,780 --> 00:16:39,200 але це не так. 386 00:16:39,200 --> 00:16:42,210 Може хто-небудь подивитися, що наш Проблема в тому, в цьому рядку? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Це дуже хвилин, що. 389 00:16:46,969 --> 00:16:48,510 І ви також можете подивитися на коді. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Він також line-- забути те, що лінія це в there-- але це в [нерозбірливо]. 392 00:16:54,940 --> 00:16:55,480 Да? 393 00:16:55,480 --> 00:16:58,639 >> СПІКЕР 4: Це на більше ніж сторінку, якщо ви читаєте це в книзі. 394 00:16:58,639 --> 00:16:59,430 СПІКЕР 1: Точно. 395 00:16:59,430 --> 00:17:02,620 Так, відладчик не міг сказати, Ви що, але відладчик 396 00:17:02,620 --> 00:17:05,880 може вам вниз до лінії що ви знаєте, не функціонує. 397 00:17:05,880 --> 00:17:09,319 І іноді, коли особливо пізніше в семестр, коли 398 00:17:09,319 --> 00:17:12,910 Ви маєте справу з сотнею, з сто кілька рядків коду, і ви 399 00:17:12,910 --> 00:17:16,190 не знаю, де це не вдається, це відмінний спосіб зробити це. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Так, ми знайшли наш помилка. 402 00:17:18,989 --> 00:17:21,530 Ви можете це виправити у файлі, а потім ви можете запустити його знову, 403 00:17:21,530 --> 00:17:23,029 і все буде працювати відмінно. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 І, найважливіше, це це може здатися, ОК. 406 00:17:30,590 --> 00:17:31,090 Так. 407 00:17:31,090 --> 00:17:31,370 Прохолодний. 408 00:17:31,370 --> 00:17:32,744 Ви знали, що ви шукаєте. 409 00:17:32,744 --> 00:17:34,910 Таким чином, ви знали, що робити. 410 00:17:34,910 --> 00:17:39,021 >> GDB може бути супер корисно, тому що вас можна роздрукувати всі ці речі, які ви 411 00:17:39,021 --> 00:17:39,520 не буде. 412 00:17:39,520 --> 00:17:41,160 Це набагато корисніше, ніж PRINTF. 413 00:17:41,160 --> 00:17:43,440 Як багато з вас використовувати як PRINTF звітності 414 00:17:43,440 --> 00:17:46,200 щоб з'ясувати, де помилка була, чи не так? 415 00:17:46,200 --> 00:17:48,450 Так, з цим, ви не повинні продовжувати повертатися, 416 00:17:48,450 --> 00:17:51,139 і подобається коментуючи в PRINTF або коментування, 417 00:17:51,139 --> 00:17:52,930 і з'ясувати, що Ви повинні бути друку. 418 00:17:52,930 --> 00:17:55,670 Це насправді просто дозволяє покроково, роздрукувати речі 419 00:17:55,670 --> 00:18:00,000 як ви проходите, так, ви можете спостерігати, як вони змінюються в режимі реального часу, 420 00:18:00,000 --> 00:18:02,190 як вашій програмі працює. 421 00:18:02,190 --> 00:18:04,390 >> І для цього треба трохи Трохи звикнути. 422 00:18:04,390 --> 00:18:07,850 Я дуже рекомендую просто вид бути трохи розчаровані з ним 423 00:18:07,850 --> 00:18:08,930 прямо зараз. 424 00:18:08,930 --> 00:18:13,450 Якщо ви проводите годину протягом на наступному тижні навчання, як використовувати GDB, 425 00:18:13,450 --> 00:18:16,140 Ви позбавите себе так багато часу в подальшому. 426 00:18:16,140 --> 00:18:18,750 І буквально. ми говоримо це людям щороку, 427 00:18:18,750 --> 00:18:23,890 і я пам'ятаю, коли я взяв клас, я був би, мені буде добре. 428 00:18:23,890 --> 00:18:24,700 Ні. 429 00:18:24,700 --> 00:18:27,030 Pset 6 загорілися і я був як, я збираюся вчитися 430 00:18:27,030 --> 00:18:29,500 як використовувати GDB, тому що я не знаю, що тут відбувається. 431 00:18:29,500 --> 00:18:32,940 >> Так що, якщо ви не поспішайте, так використовувати його на більш дрібні програм 432 00:18:32,940 --> 00:18:35,697 що ви збираєтеся бути працювати, як працює 433 00:18:35,697 --> 00:18:37,530 через щось подібне Visionare, як це. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Або, якщо ви хочете додаткову практику, я впевнений, що Я міг придумати баггі програм, 436 00:18:42,850 --> 00:18:45,300 для налагоджувати, якщо ви хочете. 437 00:18:45,300 --> 00:18:49,300 >> Але якщо ви просто зайняти деякий час, щоб отримати звик до нього, просто пограйте з ним, 438 00:18:49,300 --> 00:18:50,550 це буде дійсно служити вам добре. 439 00:18:50,550 --> 00:18:52,591 І це дійсно один з ті речі, які ви просто 440 00:18:52,591 --> 00:18:57,340 повинні спробувати, і бруднити руки с, перш ніж ви насправді зрозуміти це. 441 00:18:57,340 --> 00:19:02,090 Я дійсно тільки зрозумів його один раз У мене було налагоджувати речі з ним, 442 00:19:02,090 --> 00:19:08,170 і це набагато приємніше мати уявлення про те, як налагоджувати швидше раніше, ніж пізніше. 443 00:19:08,170 --> 00:19:08,850 Добре. 444 00:19:08,850 --> 00:19:09,625 Прохолодний. 445 00:19:09,625 --> 00:19:12,960 Я знаю, що це ніби як прискорений курс GDB, 446 00:19:12,960 --> 00:19:16,400 і я, безумовно, працювати на отримання це дивитися більше в наступний раз. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Прохолодний. 449 00:19:18,280 --> 00:19:20,390 >> Так що, якщо ми повернемося до нашого PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Чи буде це працювати? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 АДД. 454 00:19:30,210 --> 00:19:31,101 Так. 455 00:19:31,101 --> 00:19:31,600 Добре. 456 00:19:31,600 --> 00:19:35,480 Так що, якщо ви коли-небудь знадобиться будь-який з ті, знову ж таки, є список. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Так Двійковий пошук, який все пам'ятає велику видовище Давида 459 00:19:40,830 --> 00:19:42,259 розриваючи телефонні книги в половині. 460 00:19:42,259 --> 00:19:44,050 Я дійсно не отримати телефонні книги більше, 461 00:19:44,050 --> 00:19:46,530 тому як де ти отримати телефонні книги в ці дні? 462 00:19:46,530 --> 00:19:48,220 Я дійсно не знаю. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 Двійковий пошук. 465 00:19:50,590 --> 00:19:52,464 Чи пам'ятає хто- Як бінарний пошук роботи? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Будь взагалі? 468 00:19:55,220 --> 00:19:56,325 Да? 469 00:19:56,325 --> 00:19:58,283 СПІКЕР 5: Ви знаєте, коли Ви дивіться на яких половина 470 00:19:58,283 --> 00:20:01,146 це було б в, Виходячи з цього, і позбутися від іншої половини. 471 00:20:01,146 --> 00:20:01,896 >> СПІКЕР 1 Рівному. 472 00:20:01,896 --> 00:20:06,290 Так, бінарний пошук, це частково a-- --ми подобається називати це розділяй і володарюй. 473 00:20:06,290 --> 00:20:09,170 Отже, що ж ви будете робити це Ви будете виглядати в середині, 474 00:20:09,170 --> 00:20:11,990 і ви побачите, якщо він відповідає то, що ви шукаєте. 475 00:20:11,990 --> 00:20:15,420 А якщо це не так, то ви намагаєтеся з'ясувати, він збирається залишити 476 00:20:15,420 --> 00:20:16,450 половина або права половина. 477 00:20:16,450 --> 00:20:19,325 Так, це може бути, якщо ви шукаєте на щось, що це алфавітний, 478 00:20:19,325 --> 00:20:20,720 Ви бачите, о. 479 00:20:20,720 --> 00:20:22,750 Чи приходить Еллісон до М? 480 00:20:22,750 --> 00:20:23,250 Так. 481 00:20:23,250 --> 00:20:25,030 Так, ми збираємося подивіться на першу половину. 482 00:20:25,030 --> 00:20:26,450 >> Або це може бути як з числами. 483 00:20:26,450 --> 00:20:28,830 Все, що ви можете порівняти, це можуть бути відсортовані. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Ви можете використовувати бінарний пошук на. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Так, хтось пам'ятає це Графік або що це таке? 488 00:20:37,455 --> 00:20:39,520 Це асимптотической складності. 489 00:20:39,520 --> 00:20:42,830 Таким чином, цей графік тільки описує, як довго він 490 00:20:42,830 --> 00:20:46,230 приймає вас, щоб вирішити проблему, як Ви збільшити кількість речей 491 00:20:46,230 --> 00:20:47,090 що ви використовуєте. 492 00:20:47,090 --> 00:20:51,260 >> Так, у нас є N, який є лінійний час. 493 00:20:51,260 --> 00:20:54,560 Якщо N за два, що трохи краще, ще росте дуже швидко. 494 00:20:54,560 --> 00:20:58,360 А потім ми Увійдіть, який є що ми вважаємо бінарний пошук. 495 00:20:58,360 --> 00:21:03,630 Якщо ми помічаємо, як вашої проблеми стає набагато і набагато більше, 496 00:21:03,630 --> 00:21:06,600 Час, який потрібен вам її вирішити насправді не збільшити, що багато. 497 00:21:06,600 --> 00:21:09,010 Це як порівняти Тут на початку. 498 00:21:09,010 --> 00:21:10,060 Ти як, в порядку. 499 00:21:10,060 --> 00:21:13,000 Нічого тут не дійсно від того, який ми використовуємо, 500 00:21:13,000 --> 00:21:16,220 але ви вийти на мільйон, мільярд. 501 00:21:16,220 --> 00:21:20,010 Ви намагаєтеся знайти some-- --you're намагаючись знайти голку в стозі сіна. 502 00:21:20,010 --> 00:21:21,550 >> Я думаю, що ви хочете цю проблему. 503 00:21:21,550 --> 00:21:25,850 Ви хочете, щоб ця складність, а не лінійної, оскільки для всіх вас 504 00:21:25,850 --> 00:21:30,049 знаю, що ви збиралися бути пошук через кожна людина голка, річ сіна, 505 00:21:30,049 --> 00:21:31,340 намагаючись відшукати голку. 506 00:21:31,340 --> 00:21:34,730 І це не надто цікаво, на мій погляд. 507 00:21:34,730 --> 00:21:35,500 Я швидко подобається. 508 00:21:35,500 --> 00:21:36,620 Мені подобається ефективним. 509 00:21:36,620 --> 00:21:40,450 І як працьовиті студенти ви Хлопці, ви знаєте, працювати розумніше, 510 00:21:40,450 --> 00:21:43,010 не складніше річ типу, як вам може зробити ці алгоритми. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Так, ми збираємося ходити тільки через невеликий приклад. 513 00:21:47,910 --> 00:21:51,090 Я думаю, що ви, хлопці, повинні мати Рука на бінарний пошук, 514 00:21:51,090 --> 00:21:54,352 але в разі, якщо хтось трохи нечітка, хочете, щоб зміцнити його, 515 00:21:54,352 --> 00:21:56,310 ми збираємося, щоб просто піти через приклад тут. 516 00:21:56,310 --> 00:21:59,490 Так, ми шукаємо, якщо масив містить сім. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Так, перше, що ми робимо, шукати в середині, чи не так? 519 00:22:06,010 --> 00:22:09,340 А також ви збираєтеся бути кодування Двійковий пошук в тільки другий. 520 00:22:09,340 --> 00:22:11,310 Таким чином, це буде весело. 521 00:22:11,310 --> 00:22:13,710 Таким чином, ми з нетерпінням в середні маленькі масиви 3. 522 00:22:13,710 --> 00:22:15,501 3 Чи відповідає 7? 523 00:22:15,501 --> 00:22:16,000 Чи не правда. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Це шість. 526 00:22:19,550 --> 00:22:21,480 Таким чином, це менш або більше, ніж сім? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Менше ніж. 529 00:22:23,960 --> 00:22:24,570 Так. 530 00:22:24,570 --> 00:22:25,170 Хороші хлопці роботи. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Я відчуваю, що я хотів, я повинен їсти цукерки, бо я 533 00:22:27,360 --> 00:22:29,460 хочу кинути його у двори. 534 00:22:29,460 --> 00:22:30,270 Це те, що я збираюся робити на наступному тижні. 535 00:22:30,270 --> 00:22:31,436 Він буде тримати вас, хлопці різкий. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Так, ми викидаємо, що Перша половина, чи не так? 538 00:22:34,690 --> 00:22:35,670 це було менше, ніж. 539 00:22:35,670 --> 00:22:39,325 ми знаємо, що все, на цій лівого боку 540 00:22:39,325 --> 00:22:41,700 буде менше, ніж ми насправді шукаємо. 541 00:22:41,700 --> 00:22:43,491 Таким чином, немає ніякої необхідності звернути на це увагу. 542 00:22:43,491 --> 00:22:45,120 Просто забудьте про це. 543 00:22:45,120 --> 00:22:48,720 Отже, тепер ми дивимося на нашу праворуч, і ми дивимося на середині там, 544 00:22:48,720 --> 00:22:50,510 і тепер це дев'ять. 545 00:22:50,510 --> 00:22:55,510 Так, 9 is-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Більше, ніж те, що ми шукаю, чи не так? 547 00:22:57,470 --> 00:22:59,860 Так, ми збираємося кинути від все вправо. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Ось так. 550 00:23:01,940 --> 00:23:03,700 Тепер, все, що ми залишилися з одним. 551 00:23:03,700 --> 00:23:07,760 Так ми перевіряємо, це один, що ми шукаємо? це. 552 00:23:07,760 --> 00:23:08,970 Ми знайшли, що ми хотіли. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Таким чином, ми зробили. 555 00:23:11,690 --> 00:23:12,550 Білінійні Пошук. 556 00:23:12,550 --> 00:23:15,740 >> І якщо ви помітили, ми було сім входів там. 557 00:23:15,740 --> 00:23:24,320 Це тільки нам, як три рази, але якщо ви робите, як мільярд, 558 00:23:24,320 --> 00:23:28,190 Ви, хлопці, знаєте, скільки кроків було б прийняти, якщо у нас було чотири мільярди речі? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Будь-які здогади? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Це 32. 563 00:23:33,960 --> 00:23:37,110 32 кроків, щоб знайти щось в чотири мільярди 564 00:23:37,110 --> 00:23:39,650 елемент масиву зі ступенів двійки. 565 00:23:39,650 --> 00:23:43,550 Так два це 32, це до чотирьох мільярдів. 566 00:23:43,550 --> 00:23:50,430 >> Так досить божевільним, як ви все ще в як досить невеликого числа кроків 567 00:23:50,430 --> 00:23:52,650 знайти щось в чотири мільярди елементів. 568 00:23:52,650 --> 00:23:55,730 Так на цій ноті, ми збираюся кодувати це 569 00:23:55,730 --> 00:23:58,950 так ви, хлопці, може насправді вид подивитися, як це працює. 570 00:23:58,950 --> 00:24:01,520 Гаразд, так що ви, хлопці, можете закодувати. 571 00:24:01,520 --> 00:24:04,100 Я збираюся дозволити вам, хлопці говорити на трохи. 572 00:24:04,100 --> 00:24:07,970 Познайомтеся з людьми навколо вас, що є що хтось хотів від останньої секції. 573 00:24:07,970 --> 00:24:10,280 >> Тож знати людей навколо вас. 574 00:24:10,280 --> 00:24:11,305 Поговоріть для небагато. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 І все, що я хочу від вас Хлопці зараз просто 577 00:24:15,730 --> 00:24:17,575 спробувати створити начерк псевдокоде. 578 00:24:17,575 --> 00:24:18,075 Добре? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Вау. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Все, що я хочу від вас, хлопці це ти просто хочу, щоб заповнити це поки разі. 583 00:24:29,520 --> 00:24:32,170 Так я поставив ці верхня і нижня межі якої 584 00:24:32,170 --> 00:24:35,250 являють собою початок і кінець нашого масиву. 585 00:24:35,250 --> 00:24:40,440 І ви збираєтеся насправді цикл по і з'ясувати 586 00:24:40,440 --> 00:24:42,470 що ми робимо в цьому час циклу. 587 00:24:42,470 --> 00:24:45,810 >> Так що якщо ви можете з'ясувати out-- мене є натяк there-- якими є справи 588 00:24:45,810 --> 00:24:46,640 що ми маємо тут? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Так що, якщо ви хочете, щоб з'ясувати, випадки, ми будемо псевдокод тих 591 00:24:51,560 --> 00:24:53,350 і тоді ми будемо дійсно закодувати їх. 592 00:24:53,350 --> 00:24:55,330 І це буде, я думаю, ми сподіваємося, це буде 593 00:24:55,330 --> 00:24:56,788 бути трохи легше, ніж ви очікуєте. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Тому що це не так вже й багато коду, насправді, що це дійсно круто. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Мм-хм? 598 00:25:35,018 --> 00:25:35,893 >> СТУДЕНТ: [нерозбірливо]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 ВИКЛАДАЧ: Так. 601 00:25:37,650 --> 00:25:38,595 Існував щось знайти в середині. 602 00:25:38,595 --> 00:25:39,552 >> СТУДЕНТ: Таким чином, ми можемо використовувати його. 603 00:25:39,552 --> 00:25:39,770 Добре. 604 00:25:39,770 --> 00:25:40,603 >> ВИКЛАДАЧ: Прекрасно. 605 00:25:40,603 --> 00:25:42,950 Так що перше, що нам потрібно зробити. 606 00:25:42,950 --> 00:25:44,330 Так знайти середину. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Велика. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Так що у вас є уявлення про те, як ми могли б насправді знайти середину з кодом? 611 00:25:55,010 --> 00:25:55,980 >> СТУДЕНТ: Так. 612 00:25:55,980 --> 00:25:57,000 п над 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 ВИКЛАДАЧ: Так п над 2. 615 00:25:59,500 --> 00:26:05,170 Так що головне пам'ятати, що Ваші верхні та нижні межі зміни. 616 00:26:05,170 --> 00:26:08,110 Ми продовжуємо звужуючи участь з масиву ми сподіваємося. 617 00:26:08,110 --> 00:26:11,970 Так п над 2 працюватиме тільки для першої речі ми робимо. 618 00:26:11,970 --> 00:26:17,810 Так що, верхній і нижній до уваги, як ми могли б отримати, що середній елемент? 619 00:26:17,810 --> 00:26:20,640 Тому що ми хочемо, щоб середина між верхньою і нижньою, чи не так? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Мм-хм? 622 00:26:22,494 --> 00:26:23,369 >> СТУДЕНТ: [нерозбірливо]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> ВИКЛАДАЧ: Отже, ми маємо деяку середину. 625 00:26:28,080 --> 00:26:32,730 І це буде верхня плюс нижче більш 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Дивовижний. 628 00:26:35,690 --> 00:26:36,570 Там ми йдемо. 629 00:26:36,570 --> 00:26:37,280 Одна лінія вниз. 630 00:26:37,280 --> 00:26:38,560 Ви, хлопці, на вашому шляху. 631 00:26:38,560 --> 00:26:41,400 Так що тепер у нас є наш середнього, те, що ми хочемо зробити? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Просто в цілому. 634 00:26:45,900 --> 00:26:47,734 Вам не потрібно кодувати його. 635 00:26:47,734 --> 00:26:48,335 Так. 636 00:26:48,335 --> 00:26:49,210 СТУДЕНТ: [нерозбірливо]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 ВИКЛАДАЧ: Так що це плюс, бо ти знайти середнє між двома 639 00:27:10,310 --> 00:27:10,810 з них. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Так що якщо ви думаєте про них, як вид збільшення в з боків, 642 00:27:17,370 --> 00:27:21,640 думаю про це, коли ви наближаєтеся середній, ви хочете так. 643 00:27:21,640 --> 00:27:27,150 Так що, якщо ви були по обидві сторони від середній, і у нас є як 5 і 7. 644 00:27:27,150 --> 00:27:31,440 При додаванні їх разом вам отримати 12, ви розділите на 2, 6. 645 00:27:31,440 --> 00:27:33,726 >> Іноді це важко пояснити, чому це працює, 646 00:27:33,726 --> 00:27:35,600 але якщо ви працюєте через приклад іноді, 647 00:27:35,600 --> 00:27:37,962 це допоможе вам зрозуміти, якщо вона повинна бути плюс або мінус. 648 00:27:37,962 --> 00:27:38,846 Так. 649 00:27:38,846 --> 00:27:40,830 >> СТУДЕНТ: [нерозбірливо] рівно посередині 650 00:27:40,830 --> 00:27:43,950 якщо вони був випадок, коли є багато менших кількостях 651 00:27:43,950 --> 00:27:45,860 і як один великої кількості? 652 00:27:45,860 --> 00:27:49,750 >> ВИКЛАДАЧ: Все, що Вам потрібно це середина масиву. 653 00:27:49,750 --> 00:27:53,010 Так що, якщо у вас була купа невеликих кількостях а потім один дійсно велика кількість 654 00:27:53,010 --> 00:27:54,799 зрештою, це не має значення. 655 00:27:54,799 --> 00:27:56,840 Все, що має значення в тому, що вони сортуються, ви просто 656 00:27:56,840 --> 00:27:59,339 хочу подивитися на середині масив, тому що ви все ще 657 00:27:59,339 --> 00:28:00,700 нарізки вашу проблему в два рази. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Прохолодний. 660 00:28:03,680 --> 00:28:06,430 Так що тепер у нас є середній, що ми будемо робити далі? 661 00:28:06,430 --> 00:28:07,150 >> СТУДЕНТ: Порівняння. 662 00:28:07,150 --> 00:28:08,150 ВИКЛАДАЧ: порівняти. 663 00:28:08,150 --> 00:28:11,670 Так порівнювати середній для value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Прохолодний. 666 00:28:15,160 --> 00:28:17,950 Отже, ви бачите тут у нас є це значення ми хочемо тут. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Пам'ятайте, що це масив. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Так середній відноситься до індексу. 671 00:28:26,970 --> 00:28:29,785 Таким чином, ми хочемо зробити значення середині. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Не забувайте, якщо ви хочете порівняти, подвійні рівних. 674 00:28:35,650 --> 00:28:38,250 Ви робите один дорівнює ви просто хочу, щоб перепризначити його, 675 00:28:38,250 --> 00:28:41,090 а потім, звичайно, це буде значення, яке ви хочете. 676 00:28:41,090 --> 00:28:42,300 Так що не робіть цього. 677 00:28:42,300 --> 00:28:44,350 >> Отже, ми збираємося, щоб побачити, якщо значення в середині 678 00:28:44,350 --> 00:28:46,460 дорівнює вартості ми хочемо. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Не забувайте свої брекети. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox має піти. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Так що ж нам робити в цьому випадку? 685 00:28:56,200 --> 00:28:59,360 Якщо це те, що ми хочемо повернутися? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Ми намагаємося сказати. 688 00:29:02,626 --> 00:29:03,440 >> СТУДЕНТ: Роздрукуйте. 689 00:29:03,440 --> 00:29:05,314 >> ВИКЛАДАЧ: Ну, ми не хочу, щоб роздрукувати. 690 00:29:05,314 --> 00:29:08,220 Так що це Ьоо тут, тому ми хочу повернутися істинним або хибним. 691 00:29:08,220 --> 00:29:12,280 Ми говоримо, це число [? АСР? ?] Таким чином, якщо вона є, 692 00:29:12,280 --> 00:29:13,788 ми щойно повернулися чи правда. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Якщо я можу записати вірно. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> СТУДЕНТ: Чому б вам не повернутися до нуля? 697 00:29:20,805 --> 00:29:22,930 ВИКЛАДАЧ: Таким чином, ви могли повернути нуль, якщо ви хотіли. 698 00:29:22,930 --> 00:29:26,780 Але в даному випадку, тому що наша функція повертає логічне значення, 699 00:29:26,780 --> 00:29:28,962 ми повинні повернутися істинним або хибним. 700 00:29:28,962 --> 00:29:30,920 СТУДЕНТ: Коли ти кажучи логічне вираз, 701 00:29:30,920 --> 00:29:33,450 Ви можете встановити його рівним брехня? 702 00:29:33,450 --> 00:29:39,860 Як якщо я хочу сказати, якщо ця умова не виконується, як це верхня дорівнює брехня. 703 00:29:39,860 --> 00:29:42,332 Чи буде це розуміти, якщо ви просто покласти брехня на іншу сторону? 704 00:29:42,332 --> 00:29:43,040 ВИКЛАДАЧ: Так. 705 00:29:43,040 --> 00:29:44,820 Так насправді, якщо ви коли-небудь щось робити 706 00:29:44,820 --> 00:29:49,600 як зверху або нижче, що повертає істину або брехня 707 00:29:49,600 --> 00:29:53,850 і це насправді поганий стиль скажемо дорівнює дорівнює правда чи рівних 708 00:29:53,850 --> 00:29:54,840 дорівнює брехня. 709 00:29:54,840 --> 00:30:00,210 Ви хочете використовувати цей результат як сам, як ваш чек. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Не те, що я хотів. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Це те, що я хотів. 714 00:30:09,240 --> 00:30:13,205 Таким чином, у випадку, якщо ви питаєте про щось, як зберегти це в с. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Так що, якщо у нас є Int основний (порожнечу) і щось на зразок цього. 717 00:30:25,150 --> 00:30:31,922 І у вас є, якщо є верхня який вхід і ти 718 00:30:31,922 --> 00:30:33,630 з проханням, якщо ви можете зробити щось на зразок цього? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Чи не так? 721 00:30:35,679 --> 00:30:37,470 СТУДЕНТ: я намагався зробити це [нерозбірливо]. 722 00:30:37,470 --> 00:30:38,450 Тому що, якщо it's-- 723 00:30:38,450 --> 00:30:39,200 ВИКЛАДАЧ: справа. 724 00:30:39,200 --> 00:30:41,197 Отже, ви хочете, щоб це було хибним, чи не так? 725 00:30:41,197 --> 00:30:41,780 СТУДЕНТ: Так. 726 00:30:41,780 --> 00:30:45,960 ВИКЛАДАЧ: Так що в цьому випадку ви хочу, щоб це виконати, якщо це не так. 727 00:30:45,960 --> 00:30:50,510 Так здорово, що у вас там таке. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Так що пам'ятайте вигук Точка заперечує речі? 730 00:30:55,650 --> 00:30:58,270 Це говорить [нерозбірливо] означає не. 731 00:30:58,270 --> 00:31:03,590 Так що, якщо ми подивимося на щойно ця частина тут, ви б 732 00:31:03,590 --> 00:31:05,740 сказати, що має значення брехня, як ви хочете, щоб він. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Чи не помилкове істинно, які значить це виконати. 735 00:31:09,880 --> 00:31:11,037 Чи має це сенс? 736 00:31:11,037 --> 00:31:11,620 СТУДЕНТ: Так. 737 00:31:11,620 --> 00:31:12,453 ВИКЛАДАЧ: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 Добре. 740 00:31:14,300 --> 00:31:16,330 Таким чином, ми могли б просто повернутися правда в цьому випадку. 741 00:31:16,330 --> 00:31:20,357 Так що тепер у нас є два інших випадків в цьому випадку. 742 00:31:20,357 --> 00:31:21,565 Які наші два інших випадки? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Давайте просто робити це таким чином. 745 00:31:32,900 --> 00:31:40,660 Отже, давайте почнемо з ще якщо значення в середині 746 00:31:40,660 --> 00:31:43,230 менше, ніж значення ми хочемо. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Таким чином, наша цінність в середині менше ніж значення, що ми шукаємо. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Отже, які кордону зробити вас думаю, що ми хочемо, щоб оновити? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Верхній або нижній? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Верхній? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Так на чиєму боці масиву ми збираємося бути дивлячись на? 757 00:32:06,470 --> 00:32:07,500 >> СТУДЕНТ: Нижній. 758 00:32:07,500 --> 00:32:09,750 >> ВИКЛАДАЧ: Ми будемо щоб дивитися на лівій. 759 00:32:09,750 --> 00:32:11,120 Так ще, якщо мало значення менше. 760 00:32:11,120 --> 00:32:14,730 Так вашому середнього значення тут менше, ніж те, що ми хочемо. 761 00:32:14,730 --> 00:32:17,202 Тому ми хочемо, щоб взяти Права сторона масиві. 762 00:32:17,202 --> 00:32:18,910 Таким чином, ми збираємося оновити наш нижня межа. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Таким чином, ми будемо переназначать нашого нижче. 765 00:32:23,020 --> 00:32:25,221 І що ви думаєте нижче повинна бути? 766 00:32:25,221 --> 00:32:26,304 СТУДЕНТ: середнє значення? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 ВИКЛАДАЧ: Так середній value-- 769 00:32:28,820 --> 00:32:30,136 СТУДЕНТ: Плюс 1. 770 00:32:30,136 --> 00:32:31,010 ВИКЛАДАЧ: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Може хто-небудь сказати мені, чому у нас є, що плюс 1? 773 00:32:34,380 --> 00:32:35,730 >> СТУДЕНТ: [? Немає значення?] Більш дорівнює їй. 774 00:32:35,730 --> 00:32:36,120 >> ВИКЛАДАЧ: справа. 775 00:32:36,120 --> 00:32:38,661 Бо ми вже знаємо, що наша середнє значення не дорівнює 776 00:32:38,661 --> 00:32:42,750 це, і ми хочемо, щоб виключити його від всіх наступних пошуків. 777 00:32:42,750 --> 00:32:46,360 Якщо ви забули, що плюс 1, це сподобається цикл нескінченно. 778 00:32:46,360 --> 00:32:49,620 І ви просто потрапити в нескінченний цикл, а потім ви будете сегментації 779 00:32:49,620 --> 00:32:50,370 і справи йдуть погано. 780 00:32:50,370 --> 00:32:54,780 Так завжди переконайтеся, що ви не в тому числі значення, що ви тільки що 781 00:32:54,780 --> 00:32:55,380 подивився на. 782 00:32:55,380 --> 00:32:58,530 Таким чином, ми дбаємо про те, що з плюсом 1. 783 00:32:58,530 --> 00:33:04,840 >> Так що тепер у нас є остання умова які я завжди заради безпеки 784 00:33:04,840 --> 00:33:12,664 Ви можете перевірити тут, інакше, якщо значення в середній більше, ніж значення 785 00:33:12,664 --> 00:33:13,163 ми хочемо. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Це означає, що ми хочемо ліва рука наполовину. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 То який з них ми збираємося оновити? 790 00:33:23,260 --> 00:33:23,760 Верхній. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 І що це за один збирався рівнятися? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Середній мінус 1, тому що, Звичайно, ми хочемо, 795 00:33:33,690 --> 00:33:38,370 щоб переконатися, що ми не дивлячись на цього середнього значення знову. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 А то у нас його. 798 00:33:45,110 --> 00:33:45,610 Це так. 799 00:33:45,610 --> 00:33:46,820 От і все, бінарний пошук. 800 00:33:46,820 --> 00:33:48,190 Це не так уже й погано, чи не так? 801 00:33:48,190 --> 00:33:51,590 Це як 10 рядків Код з пробілами. 802 00:33:51,590 --> 00:33:57,510 Так, дуже потужний, дуже корисно, ви будете бути з використанням його в одному з ваших подальших psets. 803 00:33:57,510 --> 00:33:59,360 Може бути, це не один, але пізніше. 804 00:33:59,360 --> 00:34:00,670 Так вивчати його. 805 00:34:00,670 --> 00:34:01,510 Люблю це. 806 00:34:01,510 --> 00:34:02,980 Це буде ставитися до вас добре. 807 00:34:02,980 --> 00:34:05,370 Так хто-небудь є які-небудь питання по бінарного пошуку? 808 00:34:05,370 --> 00:34:06,196 Так. 809 00:34:06,196 --> 00:34:09,840 >> СТУДЕНТ: це має значення чи Чи ваш н парних або непарних? 810 00:34:09,840 --> 00:34:10,750 >> ВИКЛАДАЧ: Ні. 811 00:34:10,750 --> 00:34:18,150 Тому що ми кинули його в середину, як INT, це буде просто обрізати його. 812 00:34:18,150 --> 00:34:21,600 Так він залишатиметься ціле, і це буде зрештою розібратися в усьому. 813 00:34:21,600 --> 00:34:23,909 Таким чином, ви не повинні турбуватися про це. 814 00:34:23,909 --> 00:34:24,580 Все добре? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Дивовижний. 817 00:34:26,850 --> 00:34:27,919 Прохолодний. 818 00:34:27,919 --> 00:34:30,836 Так, ви, хлопці, отримав це. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Слайд-шоу. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Так як ми говоримо про, я знаю, Девід згадав складності автономної роботи. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Таким чином, в кращому випадку, це просто один, який ми називаємо постійний час. 825 00:34:50,340 --> 00:34:51,909 Може хто-небудь сказати мені, чому це може бути? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Який тип сценарію буде, що тягне за собою? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Мм-ом. 830 00:34:58,760 --> 00:34:59,926 >> СТУДЕНТ: [нерозбірливо] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 ВИКЛАДАЧ: Так середній будучи Перший елемент, який ми підходимо до, чи не так? 833 00:35:03,830 --> 00:35:08,167 Отже або масив з одного або все, що ми шукаємо тільки 834 00:35:08,167 --> 00:35:09,750 трапляється, прямо по середині. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Так що це наш найкращий випадок. 837 00:35:13,380 --> 00:35:17,540 Ви отримуєте в реальних проблем, ймовірно, не збирається досягти [нерозбірливо], що часто. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 А як щодо нашої гіршому випадку? 840 00:35:19,750 --> 00:35:21,270 Наш найгірший випадок журналу н. 841 00:35:21,270 --> 00:35:25,360 І що повинен робити з усім Повноваження два речі, які я казав о. 842 00:35:25,360 --> 00:35:30,930 >> Таким чином, в гіршому випадку це означатиме, що ми повинні були нарізати масив вниз 843 00:35:30,930 --> 00:35:33,270 поки він не був елементом один. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Так що нам довелося колоти його навпіл стільки раз, скільки ми можливо могли. 846 00:35:38,930 --> 00:35:41,430 Ось чому це журнал н тому Ви просто розділяти на два. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Так припущення, речі, які ви потрібно знати, якщо ви коли-небудь 849 00:35:45,830 --> 00:35:48,050 збираєтеся використовувати бінарний пошук. 850 00:35:48,050 --> 00:35:50,680 Ваші елементи повинні бути відсортовані. 851 00:35:50,680 --> 00:35:53,890 Вони повинні бути відсортовані, бо це єдиний спосіб 852 00:35:53,890 --> 00:35:57,060 може знати, якщо ви зможете викинути половину з нього. 853 00:35:57,060 --> 00:36:00,260 >> Якщо у вас це перемішані мішок чисел і ви говорите, 854 00:36:00,260 --> 00:36:05,380 ОК, я збираюся перевірити середину Кількість і число Я шукаю 855 00:36:05,380 --> 00:36:08,510 менше, ніж, я просто хочу, довільно викинути половину. 856 00:36:08,510 --> 00:36:11,130 Ви не знаєте, якщо ваша Цифри в цій іншій половині. 857 00:36:11,130 --> 00:36:12,655 Ваш список повинен бути відсортований. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Крім того, це може бути йти вперед трохи, 860 00:36:16,560 --> 00:36:18,360 але ви повинні мати довільний доступ. 861 00:36:18,360 --> 00:36:21,940 Ви повинні бути в змозі просто перейти на цю середнього елемента. 862 00:36:21,940 --> 00:36:25,110 Якщо у вас є, щоб пройти через щось 863 00:36:25,110 --> 00:36:28,630 або це займе у вас додаткові кроки щоб дістатися до цього середнього елемента, 864 00:36:28,630 --> 00:36:31,750 це не увійти н більше, бо Ви додаєте більше роботи в ньому. 865 00:36:31,750 --> 00:36:34,800 І це зробить трохи більше сенсу в два тижні, 866 00:36:34,800 --> 00:36:37,950 але я тільки почасти хотів би випередити, дати вам, хлопці уявлення про те, що 867 00:36:37,950 --> 00:36:38,999 прийти. 868 00:36:38,999 --> 00:36:40,790 Але ті два важливі допущення 869 00:36:40,790 --> 00:36:44,804 що вам потрібно для бінарного списку. 870 00:36:44,804 --> 00:36:45,720 Переконайтеся, що він відсортований. 871 00:36:45,720 --> 00:36:47,920 Це великий для Ви, хлопці, прямо зараз. 872 00:36:47,920 --> 00:36:52,170 І на що ми можемо піти в Решта наших сортів. 873 00:36:52,170 --> 00:36:56,444 Так чотири sorts-- міхур, вставка, вибір, і злиття. 874 00:36:56,444 --> 00:36:57,485 Вони все круто. 875 00:36:57,485 --> 00:37:02,860 Якщо ви, хлопці, вирішили взяти CS 124, Ви дізнаєтеся про всілякі сортів. 876 00:37:02,860 --> 00:37:07,575 І якщо ви шанувальник XKCD, є це дійсно здорово комікс про 877 00:37:07,575 --> 00:37:11,530 як дійсно неефективних видів, які я дуже рекомендую вам йти дивитися. 878 00:37:11,530 --> 00:37:16,170 Одним з них є, як панічний роду, які як, ой ні, повернути масив випадкових. 879 00:37:16,170 --> 00:37:16,991 Shutdown система. 880 00:37:16,991 --> 00:37:17,490 Залиште. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Так що викликають гумор завжди добре. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Так хто-небудь пам'ятає вид з як тільки загальне уявлення 885 00:37:25,750 --> 00:37:27,810 про те, як працює бульбашкового сортування. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Ви пам'ятаєте? 888 00:37:32,155 --> 00:37:32,755 >> СТУДЕНТ: Так. 889 00:37:32,755 --> 00:37:33,970 >> ВИКЛАДАЧ: Піти на це. 890 00:37:33,970 --> 00:37:38,980 >> СТУДЕНТ: Так що ви збираєтеся через і якщо він більше, то потрібно поміняти місцями два. 891 00:37:38,980 --> 00:37:39,820 >> ВИКЛАДАЧ: Мм-ом. 892 00:37:39,820 --> 00:37:40,564 Точно. 893 00:37:40,564 --> 00:37:41,730 Таким чином, ви просто перебрати. 894 00:37:41,730 --> 00:37:43,050 Ви перевірити два числа. 895 00:37:43,050 --> 00:37:46,510 Якщо один перед більше ніж той, згодом, 896 00:37:46,510 --> 00:37:50,230 Ви просто обміняти їх таким чином, щоб в Таким чином, все більш високими номерами 897 00:37:50,230 --> 00:37:54,990 міхур вверх до кінця списку і все менше число міхур вниз. 898 00:37:54,990 --> 00:37:59,355 >> Він покаже вам, хлопці здорово звуковий ефект сортування відео? 899 00:37:59,355 --> 00:38:00,480 Це круто. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Так як Роберт просто сказав, алгоритму що ви просто переміщатися за списком, 902 00:38:05,200 --> 00:38:07,930 обмін сусідні значення якщо вони не в порядку. 903 00:38:07,930 --> 00:38:10,975 А потім просто повторювати поки ви не робити будь-яких свопи. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Так не погано, чи не так? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Так що ми просто мати швидкий приклад. 908 00:38:16,319 --> 00:38:18,360 Так це буде сортувати їх у порядку зростання. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Тому, коли ми проходимо через перший Час, ми дивимося через вісім 911 00:38:23,470 --> 00:38:26,880 і шість, очевидно, не для того, що ми поміняти їх місцями. 912 00:38:26,880 --> 00:38:27,985 >> Так що дивіться на наступній. 913 00:38:27,985 --> 00:38:29,430 Вісім і чотири не в порядку. 914 00:38:29,430 --> 00:38:30,450 Поміняти їх. 915 00:38:30,450 --> 00:38:32,530 А потім вісім і два, поміняти їх місцями. 916 00:38:32,530 --> 00:38:33,470 Там ми йдемо. 917 00:38:33,470 --> 00:38:39,519 Таким чином, після першого проходу, ви знаєте, що ваш найбільший номер 918 00:38:39,519 --> 00:38:41,810 буде повністю у верхній, бо це просто 919 00:38:41,810 --> 00:38:44,210 буде постійно більше, ніж все інше 920 00:38:44,210 --> 00:38:46,810 і це тільки збирається міхура всю дорогу до кінця там. 921 00:38:46,810 --> 00:38:48,226 Чи означає це, має сенс для всіх? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Прохолодний. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Отже, ми дивимося на нашу другому проході. 926 00:38:53,920 --> 00:38:54,980 Шість і чотири, перемикач. 927 00:38:54,980 --> 00:38:55,920 Шість і два, перемикач. 928 00:38:55,920 --> 00:38:58,700 І тепер у нас є кілька речей в порядку. 929 00:38:58,700 --> 00:39:02,240 Таким чином, для кожного проходу, що ми зробити через весь наш список, 930 00:39:02,240 --> 00:39:06,320 ми знаємо, що, як, що багато номера в кінці буде були відсортовані. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Так ми робимо третій прохід, який є одним підкачки. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 І тоді на наш четвертий пройти, у нас є нульові слотів. 935 00:39:15,910 --> 00:39:18,570 І тому ми знаємо, що наш масив був відсортований. 936 00:39:18,570 --> 00:39:20,900 >> І це велика річ з бульбашкового сортування. 937 00:39:20,900 --> 00:39:23,720 Ми знаємо, що, коли ми мають нульові свопи, що 938 00:39:23,720 --> 00:39:26,497 означає, що всі, знаходиться в повному порядку. 939 00:39:26,497 --> 00:39:27,580 Це свого роду, як ми перевіряємо. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Таким чином, ми також збираємося кодувати міхур роду, які також не в тому, що погано. 942 00:39:36,480 --> 00:39:38,120 Жоден з них не так уже й погано. 943 00:39:38,120 --> 00:39:40,210 Я знаю, що вони можуть здатися трохи страшно. 944 00:39:40,210 --> 00:39:42,124 Я знаю, коли я взяв клас, навіть коли я 945 00:39:42,124 --> 00:39:44,290 викладав клас для перший раз в минулому році, 946 00:39:44,290 --> 00:39:46,165 Я був, як, як я можу це зробити? 947 00:39:46,165 --> 00:39:48,540 Це має сенс у теорії, але як ми насправді це зробити? 948 00:39:48,540 --> 00:39:51,420 Саме тому я і хочу, щоб йти через код з вами, хлопці тут. 949 00:39:51,420 --> 00:39:54,915 Так що у мене псевдокод для вас, хлопці на цей раз. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Так що майте це на увазі, як ми збираємося перейти протягом. 952 00:39:58,970 --> 00:40:04,210 Тому у нас є якийсь лічильник, що відстежує наші свопи, 953 00:40:04,210 --> 00:40:08,370 тому що нам потрібно, щоб переконатися, що ми перевіряємо, що. 954 00:40:08,370 --> 00:40:11,830 І ми ітерації весь масив як ми тільки що зробили з цим прикладом. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Якщо елемент, перш ніж більше елемент після, де ми знаходимося, 957 00:40:17,325 --> 00:40:20,760 ми обміняти їх і ми збільшуємо OUR Лічильник тому що як тільки ми поміняти, 958 00:40:20,760 --> 00:40:23,850 ми хочемо, щоб наш лічильник знаю, що. 959 00:40:23,850 --> 00:40:26,247 Будь-які питання є? 960 00:40:26,247 --> 00:40:27,580 Щось, здається, смішно тут. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 СТУДЕНТ: Ви встановити лічильник на нуль кожен раз, коли ви йдете через петлю? 963 00:40:32,350 --> 00:40:34,339 Ви не продовжувати назад до нуля кожен раз? 964 00:40:34,339 --> 00:40:35,505 ВИКЛАДАЧ: Не обов'язково. 965 00:40:35,505 --> 00:40:39,710 Так що ж відбувається у нас пройти тут. 966 00:40:39,710 --> 00:40:43,830 Так що в той час, пам'ятайте, що це виконуватиме один раз в обов'язковому порядку. 967 00:40:43,830 --> 00:40:46,480 Так це буде встановлено лічильник дорівнює нулю, 968 00:40:46,480 --> 00:40:48,070 то це буде для перебору. 969 00:40:48,070 --> 00:40:50,590 Як воно проходить по, вона оновить лічильник. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Як він оновлює лічильник, коли це буде зроблено, коли він досяг кінця масиву, 972 00:40:56,900 --> 00:41:00,830 якщо наш списку не відсортований, Лічильник були оновлені. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Так то воно перевіряє стан і каже, добре, це лічильник більше нуля. 975 00:41:07,150 --> 00:41:09,290 Якщо це так, зробити це знову. 976 00:41:09,290 --> 00:41:14,340 Ви хочете скинути, так що, коли вам пройти через, лічильник дорівнює нулю. 977 00:41:14,340 --> 00:41:18,240 Якщо ви йдете через відсортоване Масив, нічого не змінюється, 978 00:41:18,240 --> 00:41:21,355 це не вдається, і ви повернутися відсортований список. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Чи означає це, має сенс? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 СТУДЕНТ: Це може в небагато. 983 00:41:26,356 --> 00:41:27,147 ВИКЛАДАЧ: ОК. 984 00:41:27,147 --> 00:41:28,980 Якщо є будь-яка інша Питання, яке приходить. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Так. 987 00:41:30,680 --> 00:41:33,760 >> СТУДЕНТ: Що б функція бути для перекачки елементи? 988 00:41:33,760 --> 00:41:36,900 >> ВИКЛАДАЧ: Таким чином, ми можемо насправді писати що якщо ми збираємося прямо зараз. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Прохолодний. 991 00:41:38,300 --> 00:41:42,155 Так на цій ноті, Елісон збирається Щоб повернутися назад у прилад. 992 00:41:42,155 --> 00:41:43,080 Це буде весело. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 І у нас є наш славний бульбашкова сортування річ тут. 995 00:41:47,390 --> 00:41:50,800 Так що я вже зробив на велосипеді через масив. 996 00:41:50,800 --> 00:41:53,030 У нас є наші свопи, які дорівнюють нулю. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Тому ми хочемо, щоб поміняти прилеглих елементи, якщо вони вийшли з ладу. 999 00:41:58,440 --> 00:42:03,020 Тому перше, що ми повинні робимо, перебору нашого масиву. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Отже, як ви думаєте, ми могли б перебору нашого масиву? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 У нас є для, і я дорівнює 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Ми хочемо, щоб я бути менше ніж п мінус 1 мінус к. 1006 00:42:22,454 --> 00:42:23,870 І я поясню, що в секунду. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Так що це оптимізація тут, де, пам'ятаю, як я сказав, після кожного проходу 1009 00:42:32,830 --> 00:42:36,655 через масив ми знаю, що все, що це on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Таким чином, після одного проходу ми знаю, що це сортується. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Після двох проходів ми знаємо що все це сортується. 1014 00:42:50,060 --> 00:42:52,750 Після трьох проходів ми знаю, що це сортуються. 1015 00:42:52,750 --> 00:42:55,620 Так речі я ітерації через масив тут, 1016 00:42:55,620 --> 00:43:01,090 буде це робити обов'язково йти тільки через те, що ми знаємо, це несортоване. 1017 00:43:01,090 --> 00:43:01,644 Добре? 1018 00:43:01,644 --> 00:43:02,810 От тільки оптимізація. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Ви могли б написати його наївно просто перебору всього, 1021 00:43:08,210 --> 00:43:09,970 це було б просто зайняти більше часу. 1022 00:43:09,970 --> 00:43:12,470 З цього чотири циклу це просто хороший оптимізація 1023 00:43:12,470 --> 00:43:18,460 тому що ми знаємо, що після того, як кожний повний ітерації по масиву тут, 1024 00:43:18,460 --> 00:43:24,050 як кожний повний петлі тут, ми знаємо, що більше з цих елементів одного 1025 00:43:24,050 --> 00:43:25,760 будуть відсортовані в кінці. 1026 00:43:25,760 --> 00:43:28,294 >> Таким чином, ми не повинні турбуватися про них. 1027 00:43:28,294 --> 00:43:29,710 Чи означає це, має сенс для всіх? 1028 00:43:29,710 --> 00:43:30,950 Це здорово маленька хитрість? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Таким чином, в цьому випадку, якщо ми ітерації, 1031 00:43:37,270 --> 00:43:50,590 ми знаємо, що ми хочемо, щоб перевірити, Масив п і п + 1 в порядку. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 Добре. 1034 00:43:53,559 --> 00:43:54,600 Так ось псевдокод. 1035 00:43:54,600 --> 00:43:57,540 Ми хочемо, щоб перевірити, якщо масив н і н плюс 1 в порядку. 1036 00:43:57,540 --> 00:43:59,520 Так що, можливо, у нас там? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Це буде якийсь умовний. 1039 00:44:03,120 --> 00:44:04,220 Це буде, якщо. 1040 00:44:04,220 --> 00:44:07,066 >> СТУДЕНТ: Якщо масив п менш масиву н плюс 1. 1041 00:44:07,066 --> 00:44:07,816 ВИКЛАДАЧ: Мм-ом. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Ну, менше або більше, ніж. 1044 00:44:10,699 --> 00:44:11,615 СТУДЕНТ: Більше. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Тоді ми хочемо поміняти їх місцями. 1047 00:44:17,620 --> 00:44:18,570 Точно. 1048 00:44:18,570 --> 00:44:23,570 Так що тепер ми потрапляємо в те, що Механізм для перекачки їх? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Таким чином, ми пройшли через цю стисло, тип функції підкачування минулого тижня. 1051 00:44:28,137 --> 00:44:29,595 Хтось пам'ятає, як він працював? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Таким чином, ми не можемо просто передати їх, чи не так? 1054 00:44:34,950 --> 00:44:36,640 Тому що одне з них буде губитися. 1055 00:44:36,640 --> 00:44:41,696 Якщо ми сказали, дорівнює Б, а той дорівнює A, все раптово обидва 1056 00:44:41,696 --> 00:44:43,150 просто дорівнює B. 1057 00:44:43,150 --> 00:44:45,720 >> Отже, що ми повинні зробити, це ми є тимчасову змінну ось 1058 00:44:45,720 --> 00:44:49,055 збирається провести один з наших-то час ми знаходимося в процесі перекачування. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Так що у нас є, ми будемо мати деякий Int Температура дорівнює to-- можна призначити 1061 00:44:56,464 --> 00:44:59,130 залежно від того, що ви хочете, просто переконайтеся, що ви відслідковувати it-- 1062 00:44:59,130 --> 00:45:01,840 тому в даному випадку, я збираюся призначити його на масиві н плюс 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Так що відбувається, щоб вмістити все Значення в цьому другому блоці 1065 00:45:07,674 --> 00:45:08,590 що ми дивимося на. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> І тоді ми можемо зробити, це ми можемо піти вперед, а також переназначать масив н плюс 1, 1068 00:45:13,240 --> 00:45:14,990 тому що ми знаємо, що Тобто це значення зберігається. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Це також є одним із великої things-- Я не знаю, якщо хтось з вас 1071 00:45:19,270 --> 00:45:23,780 були проблеми, коли при перемиканні два рядків коду раптом все працювало. 1072 00:45:23,780 --> 00:45:25,880 Замовити дуже важливо в CS. 1073 00:45:25,880 --> 00:45:29,450 Тому переконайтеся, що ви діаграмі речі, якщо це можливо 1074 00:45:29,450 --> 00:45:31,230 щодо того, що відбувається насправді. 1075 00:45:31,230 --> 00:45:34,256 Так що тепер ми збираємося перепризначити масиву п плюс 1, 1076 00:45:34,256 --> 00:45:36,005 тому що ми знаємо, що Тобто це значення зберігається. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> І ми можемо призначити, що в масиві н а в даному випадку масив я. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Занадто багато змінних. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 Добре. 1083 00:45:55,470 --> 00:46:01,500 Так що тепер ми переведені масив, який я плюс 1 рівним, що знаходиться в масиві I. 1084 00:46:01,500 --> 00:46:08,240 І тепер ми можемо повернутися і призначити масив я до чого? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Будь? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> СТУДЕНТ: 10. 1089 00:46:14,010 --> 00:46:14,680 >> ВИКЛАДАЧ: 10. 1090 00:46:14,680 --> 00:46:15,180 Точно. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 І останнє. 1093 00:46:18,640 --> 00:46:21,840 Якщо ми помінялися це зараз, Що ми повинні зробити? 1094 00:46:21,840 --> 00:46:23,740 Що одна справа що збирається розповісти нам 1095 00:46:23,740 --> 00:46:27,542 якщо ми коли-небудь припинити цю програму? 1096 00:46:27,542 --> 00:46:29,250 Що говорить нам, що ми є відсортований список? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Якщо ми не виконують ніяких свопів, чи не так? 1099 00:46:33,750 --> 00:46:36,900 Якщо свопи дорівнює нулю в кінці цього. 1100 00:46:36,900 --> 00:46:42,975 Тому, коли ви виконати обмін, як ми тільки що зробив тут, ми хочемо оновити свопи. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 І я знаю, що було Питання раніше про можеш 1103 00:46:47,210 --> 00:46:49,689 використовувати нуль або один, а з істинними або помилковими. 1104 00:46:49,689 --> 00:46:50,980 І ось що це робить тут. 1105 00:46:50,980 --> 00:46:52,750 Таким чином, це говорить якщо не свопи. 1106 00:46:52,750 --> 00:47:01,310 Так що, якщо свопи дорівнює нулю, що is-- я завжди отримати мої істини і мої falses переплутали. 1107 00:47:01,310 --> 00:47:03,960 Ми хочемо, щоб нам оцінити щоб вірно і це не так. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Так що, якщо це нуль, то це брехня. 1110 00:47:09,630 --> 00:47:12,560 Якщо ви заперечувати його [? бац?] стає правдою. 1111 00:47:12,560 --> 00:47:13,975 Отже ця лінія виконує. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Істини і брехня, і нулі й одиниці отримати з розуму. 1114 00:47:17,370 --> 00:47:20,690 Просто, якщо ви повільно ходити через нього буде мати сенс. 1115 00:47:20,690 --> 00:47:23,320 Але ось що це трохи шматок коду тут робить. 1116 00:47:23,320 --> 00:47:26,490 Таким чином, це перевіряє, ми зробили ніяких свопів. 1117 00:47:26,490 --> 00:47:30,054 Так що, якщо це що-небудь, крім нулю, це буде брехня 1118 00:47:30,054 --> 00:47:31,970 і все це є збирається виконати знову. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Прохолодний? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> СТУДЕНТ: Що перерву зробити? 1123 00:47:36,000 --> 00:47:38,990 >> ВИКЛАДАЧ: Перерва просто ламає тебе з петлі. 1124 00:47:38,990 --> 00:47:41,570 Таким чином, в даному випадку це було б так само, як завершити програму 1125 00:47:41,570 --> 00:47:43,828 і ви б просто є свій відсортований список. 1126 00:47:43,828 --> 00:47:44,536 СТУДЕНТ: Восхитительно. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 ВИКЛАДАЧ: Я шкодую? 1129 00:47:49,010 --> 00:47:52,110 СТУДЕНТ: Бо раніше ми б написав 1 над написана нулю 1130 00:47:52,110 --> 00:47:54,170 уявити, що якщо що буде працювати чи ні. 1131 00:47:54,170 --> 00:47:54,878 >> ВИКЛАДАЧ: Так. 1132 00:47:54,878 --> 00:47:56,410 Таким чином, ви можете повернутися до нуля або 1. 1133 00:47:56,410 --> 00:47:58,950 В цьому випадку, тому що ми насправді не робити що-небудь за допомогою функції, 1134 00:47:58,950 --> 00:48:00,150 ми просто хочемо, щоб зламати. 1135 00:48:00,150 --> 00:48:02,680 Ми дійсно не піклуються про це. 1136 00:48:02,680 --> 00:48:06,960 Гальмівна також добре, якщо він використовується для виходу з 1137 00:48:06,960 --> 00:48:10,710 з чотирьох петель або умов, які Ви не хочете, щоб виконання. 1138 00:48:10,710 --> 00:48:12,110 Це займе вас з них. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Це щось на зразок нюанс речі. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Я відчуваю, що є багато ручної завивки, 1143 00:48:18,445 --> 00:48:19,740 як ви дізнаєтеся про це найближчим часом. 1144 00:48:19,740 --> 00:48:20,955 >> Але ви дізнаєтеся про це найближчим часом. 1145 00:48:20,955 --> 00:48:21,500 Я обіцяю. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 Добре. 1148 00:48:23,170 --> 00:48:24,840 Так само всі отримують бульбашкового сортування? 1149 00:48:24,840 --> 00:48:25,550 Не надто погано. 1150 00:48:25,550 --> 00:48:31,910 Перебору, своп речі за допомогою Мінлива температура, і ми все ж тут? 1151 00:48:31,910 --> 00:48:32,960 Прохолодний. 1152 00:48:32,960 --> 00:48:34,080 Дивовижний. 1153 00:48:34,080 --> 00:48:34,807 Добре. 1154 00:48:34,807 --> 00:48:35,765 Повернутися до PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Будь-які питання в цілому про них до сих пір? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Прохолодний. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Мм-ом. 1161 00:48:43,695 --> 00:48:45,279 >> СТУДЕНТ: [нерозбірливо] Int основний звичайно. 1162 00:48:45,279 --> 00:48:46,695 Ви повинні мати, що для цього? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> ВИКЛАДАЧ: Таким чином, ми просто шукали просто за фактичною алгоритму сортування. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Якщо ви мали його протягом як великої програми, 1167 00:48:56,350 --> 00:48:57,891 Ви б мати Int основний десь. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Залежно від того, де ви використовувати цей алгоритм, 1170 00:49:02,880 --> 00:49:05,860 було б визначити, що повертається до неї. 1171 00:49:05,860 --> 00:49:09,960 Але для нашого випадку, ми строго дивлячись на те, як це робить насправді 1172 00:49:09,960 --> 00:49:11,300 перебору масиву. 1173 00:49:11,300 --> 00:49:12,570 Таким чином, ми не турбуватися про це. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Таким чином, ми говоримо про кращому випадку і гірші сценарії для бінарного пошуку. 1176 00:49:19,830 --> 00:49:22,470 Так що це також важливо зробити що для кожного з наших сортів. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Так що ви думаєте, це найгірший Справа часу виконання бульбашкового сортування? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Ви, хлопці, пам'ятаєте? 1181 00:49:30,700 --> 00:49:31,784 >> СТУДЕНТ: N мінус 1. 1182 00:49:31,784 --> 00:49:32,700 ВИКЛАДАЧ: N мінус 1. 1183 00:49:32,700 --> 00:49:35,070 Значить, є н мінус 1 порівняння. 1184 00:49:35,070 --> 00:49:40,060 Так одна справа розуміти, що на першій ітерації, 1185 00:49:40,060 --> 00:49:43,360 ми йдемо до кінця, ми порівняємо ці two-- так от 1. 1186 00:49:43,360 --> 00:49:46,685 Ці два, три, чотири. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Таким чином, після однієї ітерації ми вже є чотири порівнянь. 1189 00:49:55,050 --> 00:49:58,230 Коли я говорю про час виконання і п. 1190 00:49:58,230 --> 00:50:04,680 N є кількістю порівнянь як функція від того, скільки елементів 1191 00:50:04,680 --> 00:50:05,570 у нас є. 1192 00:50:05,570 --> 00:50:06,430 Добре? 1193 00:50:06,430 --> 00:50:08,860 >> Так ми йдемо до кінця, у нас є чотири. 1194 00:50:08,860 --> 00:50:11,780 Наступного разу, ви знаєте, ми не повинні подбати про це. 1195 00:50:11,780 --> 00:50:15,140 Ми порівнюємо ці два, ці двоє, ці двоє, 1196 00:50:15,140 --> 00:50:20,050 і якщо у нас не було, що оптимізація з чотирма петлі, що я написав, 1197 00:50:20,050 --> 00:50:22,750 Ви б порівнювати тут в будь-якому випадку. 1198 00:50:22,750 --> 00:50:26,170 Таким чином, ви повинні були б запустити через масив 1199 00:50:26,170 --> 00:50:34,380 і зробити п порівнянь н раз, бо щоразу, коли ми 1200 00:50:34,380 --> 00:50:36,670 запустити через це ми начебто одне. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> І кожен раз, коли ми стикаємося з допомогою масив, ми робимо п порівнянь. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Таким чином, наша середу для цього насправді н квадрат, який 1205 00:50:46,330 --> 00:50:48,400 набагато гірше, в нашому увійти кінці, бо, що 1206 00:50:48,400 --> 00:50:51,965 значить, якщо у нас було чотири мільярд елементи, це 1207 00:50:51,965 --> 00:50:55,260 збирається взяти нас чотири мільярди квадрат замість 32. 1208 00:50:55,260 --> 00:51:01,240 То чи не краще середу, але для деяких речей, 1209 00:51:01,240 --> 00:51:04,610 Ви знаєте, якщо ви протягом певний діапазон елементів 1210 00:51:04,610 --> 00:51:06,540 бульбашкова сортування може бути штраф, щоб використовувати. 1211 00:51:06,540 --> 00:51:07,530 >> Добре. 1212 00:51:07,530 --> 00:51:12,290 Так що тепер, що це найкращий випадок виконання? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 СТУДЕНТ: Нуль? 1215 00:51:14,940 --> 00:51:16,420 Або 1? 1216 00:51:16,420 --> 00:51:18,140 >> ВИКЛАДАЧ: Так 1 буде одним порівняння. 1217 00:51:18,140 --> 00:51:19,114 Право. 1218 00:51:19,114 --> 00:51:20,002 >> СТУДЕНТ: N мінус 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> ВИКЛАДАЧ: Так що, так. 1221 00:51:22,320 --> 00:51:22,990 Так н мінус 1. 1222 00:51:22,990 --> 00:51:26,510 Всякий раз, коли у вас є таке поняття, як п мінус 1, ми, як правило, просто висадити його 1223 00:51:26,510 --> 00:51:31,680 і ми просто скажемо, п, тому що ви є порівняти кожен з these-- кожної пари. 1224 00:51:31,680 --> 00:51:36,470 Тому було б н мінус 1, який ми ми просто скажемо, приблизно н. 1225 00:51:36,470 --> 00:51:39,280 Коли ви маєте справу з виконання, все в наближає. 1226 00:51:39,280 --> 00:51:43,860 До тих пір, як експонента правильно, ви дуже добре. 1227 00:51:43,860 --> 00:51:45,700 >> Ось як ми з нею боремося. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Так що в кращому випадку це п, означає, що список вже відсортований, 1230 00:51:51,780 --> 00:51:54,320 і все, що ми зробити, це запустити через і переконайтеся, що це сортуються. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Прохолодний. 1233 00:51:56,855 --> 00:51:57,355 Добре. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Отже, як ви бачите тут, ми просто є ще кілька графіків. 1236 00:52:01,920 --> 00:52:02,660 Так п квадрат. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Набагато гірше, ніж п, як ми бачимо, і набагато, набагато гірше, ніж журналу 2n. 1240 00:52:09,730 --> 00:52:12,060 І тоді ви також отримуєте в журналах журналів. 1241 00:52:12,060 --> 00:52:18,020 І ви берете 124, ви отримаєте в як лог зірки, яка, як божевільний. 1242 00:52:18,020 --> 00:52:20,172 Так що якщо ви зацікавлені, пошук журналу зірка. 1243 00:52:20,172 --> 00:52:20,880 Це забавно. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Тому у нас є цей великий графік. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Просто голови, це чудовий графік, щоб мати 1248 00:52:28,720 --> 00:52:31,350 для середньостроковій перспективі, тому що ми довго б задати вам ці рідшає. 1249 00:52:31,350 --> 00:52:36,090 Так просто голови, тобто це на Середньостроковий на хорошому шпаргалку 1250 00:52:36,090 --> 00:52:36,616 є. 1251 00:52:36,616 --> 00:52:37,990 Таким чином, ми просто дивилися на бульбашкового сортування. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 В гіршому випадку, п квадрат, кращий випадок, п. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 І ми збираємося дивитися на інших. 1256 00:52:44,950 --> 00:52:47,940 >> І як ви можете бачити, тільки той, який дійсно добре 1257 00:52:47,940 --> 00:52:50,910 є сортування злиттям, які ми отримаємо в чому. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Отже, ми збираємося піти в Наступний here-- вибір роду. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Чи пам'ятає хтось, як Вибір роду працював? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Піти на це. 1264 00:53:05,700 --> 00:53:08,210 >> СТУДЕНТ: В основному йдуть через Порядок і створити новий список. 1265 00:53:08,210 --> 00:53:11,001 І так само, як ви кладете елементи в, покласти їх в правильному місці 1266 00:53:11,001 --> 00:53:11,750 в новому списку. 1267 00:53:11,750 --> 00:53:14,040 >> ВИКЛАДАЧ: Так що звуки більше схоже вставки роду. 1268 00:53:14,040 --> 00:53:15,040 Але ви дійсно близькі. 1269 00:53:15,040 --> 00:53:15,915 Вони дуже схожі. 1270 00:53:15,915 --> 00:53:17,440 Навіть я плутаю іноді. 1271 00:53:17,440 --> 00:53:18,981 Перед цій частині я був як, чекати. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 Добре. 1274 00:53:20,630 --> 00:53:24,141 Так що ви хочете зробити вибір роду, 1275 00:53:24,141 --> 00:53:25,890 як ви можете думати, про це і шляхи 1276 00:53:25,890 --> 00:53:30,140 Я переконуюся, що намагаюся не отримати плутаю, це проходить через 1277 00:53:30,140 --> 00:53:33,280 і він вибирає найменше число, і це 1278 00:53:33,280 --> 00:53:36,070 ставить, що на початку списку. 1279 00:53:36,070 --> 00:53:37,730 Це змінює його з тієї першої місці. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Вони насправді є приклад для мене. 1282 00:53:45,370 --> 00:53:46,540 Дивовижний. 1283 00:53:46,540 --> 00:53:50,130 Так просто спосіб думати про it-- вибору роду, виберіть найменше значення. 1284 00:53:50,130 --> 00:53:51,940 І ми збираємося проходять через прикладу 1285 00:53:51,940 --> 00:53:55,320 що я думаю, що допоможе, бо Я думаю, що візуальні завжди допомогти. 1286 00:53:55,320 --> 00:53:58,510 Отже, ми починаємо з чимось що повністю без сортування. 1287 00:53:58,510 --> 00:54:00,730 Червоний буде несортовані, зелений будуть відсортовані. 1288 00:54:00,730 --> 00:54:02,190 Це все буде мати сенс в секунду. 1289 00:54:02,190 --> 00:54:08,950 >> Таким чином, ми пройти і ми ітерації від початку і до кінця. 1290 00:54:08,950 --> 00:54:12,320 І ми говоримо: ОК, 2 наш маленький номер. 1291 00:54:12,320 --> 00:54:15,680 Таким чином, ми збираємося взяти 2, і ми збираємося щоб перемістити його на фронт нашого масиву 1292 00:54:15,680 --> 00:54:17,734 бо це Найменше число у нас є. 1293 00:54:17,734 --> 00:54:19,150 Так ось що це робить тут. 1294 00:54:19,150 --> 00:54:20,820 Це просто буде поміняти ці два. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Так що тепер ми сортуються частину і несортоване частину. 1297 00:54:25,450 --> 00:54:27,810 І те, що добре пам'ятати про вибір роду 1298 00:54:27,810 --> 00:54:30,690 це ми тільки вибору від невідсортованої частини. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> Відсортований частину ви просто залишити в спокої. 1301 00:54:34,527 --> 00:54:35,660 Мм-хм? 1302 00:54:35,660 --> 00:54:38,452 >> СТУДЕНТ: Як це знаю, що це найменший, чи не порівнюючи його 1303 00:54:38,452 --> 00:54:39,868 до кожного іншому значенню в масиві. 1304 00:54:39,868 --> 00:54:41,250 ВИКЛАДАЧ: Він робить порівняти його. 1305 00:54:41,250 --> 00:54:42,041 Нам подобається пропустив його. 1306 00:54:42,041 --> 00:54:43,850 Це просто взагалі в цілому. 1307 00:54:43,850 --> 00:54:44,831 Так. 1308 00:54:44,831 --> 00:54:47,205 Коли ми пишемо код, я що ви будете більш задоволені. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Але ви зберігаєте цей перший Елемент як найменше. 1311 00:54:53,030 --> 00:54:56,110 Ви порівняйте, і ви сказати, в порядку, це менше? 1312 00:54:56,110 --> 00:54:56,660 Так. 1313 00:54:56,660 --> 00:54:57,460 Тримайте його. 1314 00:54:57,460 --> 00:54:58,640 Ось це менше? 1315 00:54:58,640 --> 00:54:59,660 Ні? 1316 00:54:59,660 --> 00:55:02,510 >> Це ваш маленький, перепризначити його на значення. 1317 00:55:02,510 --> 00:55:06,340 І ви будете набагато щасливішими коли ми йдемо через код. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Так ми йдемо до кінця, ми поміняти його, так то ми дивимося на цей несортоване частини. 1320 00:55:13,970 --> 00:55:15,810 Отже, ми збираємося, щоб вибрати три від'їзді. 1321 00:55:15,810 --> 00:55:18,890 Ми збираємося поставити його на на кінець відсортованого нашій частині. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 І ми просто будемо продовжувати робити що, роблячи це, і робити це. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Так що це наш вид псевдокоде тут. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Ми закодувати його тут в секунду. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Але тільки щось ходити через на високому рівні. 1330 00:55:37,270 --> 00:55:40,275 Ви збираєтеся перейти від я дорівнює від 0 до н мінус 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Це ще одна оптимізація. 1333 00:55:43,530 --> 00:55:45,020 Не хвилюйтеся про це занадто багато. 1334 00:55:45,020 --> 00:55:46,620 Отже, як ви говорили. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Як казав Яків, як ми відслідковувати те, що наш мінімум? 1337 00:55:54,406 --> 00:55:55,030 Як ми знаємо? 1338 00:55:55,030 --> 00:55:57,060 Ми повинні порівняти все в нашому списку. 1339 00:55:57,060 --> 00:55:59,600 >> Так мінімальна дорівнює я. 1340 00:55:59,600 --> 00:56:03,870 Це просто говорю в даному випадку Індекс нашої мінімального значення. 1341 00:56:03,870 --> 00:56:07,660 Отже, що це збирається перебору і вона йде від J дорівнює я плюс 1. 1342 00:56:07,660 --> 00:56:11,420 Таким чином, ми вже знаємо, що це наш перший елемент. 1343 00:56:11,420 --> 00:56:13,240 Нам не потрібно, щоб порівняти його з себе. 1344 00:56:13,240 --> 00:56:16,970 Таким чином, ми починаємо порівнювати його з рядом один, який є, чому це я плюс 1 до п 1345 00:56:16,970 --> 00:56:20,110 мінус 1, яке є кінець масиву там. 1346 00:56:20,110 --> 00:56:25,090 І ми сказали, що якщо масив на J є менш масиву хв, 1347 00:56:25,090 --> 00:56:29,200 Потім ми перепризначити де наші мінімальні показники є. 1348 00:56:29,200 --> 00:56:37,470 >> І якщо хв не дорівнює I, як в якому ми вже були тут. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Так як коли ми вперше зробили це. 1351 00:56:41,790 --> 00:56:49,310 В цьому випадку, було б почати з нулю, це буде в кінцевому підсумку два. 1352 00:56:49,310 --> 00:56:53,010 Так хв не дорівнюватиме я, в кінці кінців. 1353 00:56:53,010 --> 00:56:55,720 Це дозволяє нам знати, що ми повинні поміняти їх місцями. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Я відчуваю, що на конкретному прикладі допоможе набагато більше, ніж це. 1356 00:57:00,470 --> 00:57:04,970 Так що я буду кодувати це з вами, хлоп'ята прямо зараз, і я думаю, що це буде краще. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Сорти, як правило, працює таким чином у тому, що це часто краще просто побачити їх. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Отже, що ми хочемо зробити, це спочатку ми хотіли найменша 1361 00:57:17,280 --> 00:57:19,890 елемент в його позиції в масиві. 1362 00:57:19,890 --> 00:57:21,280 Саме те, що Яків говорив. 1363 00:57:21,280 --> 00:57:23,090 Ви повинні зберегти щось. 1364 00:57:23,090 --> 00:57:25,900 Таким чином, ми збираємося розпочати тут ітерації по масиву. 1365 00:57:25,900 --> 00:57:28,970 Ми збираємося сказати, що це наш Перший раз, щоб почати с. 1366 00:57:28,970 --> 00:57:38,308 Таким чином, ми будемо мати Int маленький дорівнює масиву в I. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Так що, одне зауважити, кожен Час це цикл виконується, 1369 00:57:45,050 --> 00:57:48,550 ми починаємо ще один крок вперед разом. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Коли ми починаємо дивитися на цей. 1372 00:57:57,440 --> 00:58:00,840 Наступного разу ми перебору, ми починаємо в цьому 1373 00:58:00,840 --> 00:58:02,680 і присвоєння його нашим найменше значення. 1374 00:58:02,680 --> 00:58:10,450 Так що це дуже схоже на бульбашкового сортування де ми знаємо, що після одного проходу, 1375 00:58:10,450 --> 00:58:11,700 це останній елемент сортується. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 З вибору роду, це якраз навпаки. 1378 00:58:15,120 --> 00:58:18,950 >> На кожному проході, ми знаємо, що Перший сортується. 1379 00:58:18,950 --> 00:58:21,360 Після другого проходу, Друга будуть відсортовані. 1380 00:58:21,360 --> 00:58:26,470 І, як ви бачили на прикладах слайд, наша упорядковано частину просто продовжує зростати. 1381 00:58:26,470 --> 00:58:34,020 Так, встановивши наш маленький друг для масивів я, все, що він робить 1382 00:58:34,020 --> 00:58:37,340 є стискаючи що ми дивимося на того, 1383 00:58:37,340 --> 00:58:40,164 щоб звести до мінімуму кількість порівнянь ми робимо. 1384 00:58:40,164 --> 00:58:41,770 Чи має це сенс для всіх? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Вам потрібен мені, щоб пробігти, що знову повільніше або різними словами? 1387 00:58:46,380 --> 00:58:47,180 Я щасливий. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 Добре. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Таким чином, ми зберігання Значення в цьому пункті, 1392 00:58:55,540 --> 00:58:57,840 але ми також хочемо, щоб зберігати індекс. 1393 00:58:57,840 --> 00:59:01,010 Отже, ми збираємося зберігати Положення найменша 1394 00:59:01,010 --> 00:59:02,770 один, який тільки збирається бути, я. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Так що тепер Яків задоволений. 1397 00:59:05,440 --> 00:59:06,870 У нас є речі, що зберігаються. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 І тепер ми повинні дивитися через без сортування частина масиву. 1400 00:59:11,870 --> 00:59:18,170 Таким чином, в даному випадку це буде наша несортоване. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Це я. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 Добре. 1405 00:59:26,210 --> 00:59:30,040 >> Отже, що ми збираємося зробити буде для петлі. 1406 00:59:30,040 --> 00:59:32,066 Всякий раз, коли вам потрібно перебору масиву, 1407 00:59:32,066 --> 00:59:33,440 Ваш розум може піти для петлі. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Таким чином, для деяких Int до equals-- що ми думаємо 1410 00:59:38,090 --> 00:59:39,700 До збирається рівнятися почати? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Це те, що ми поставили як наша маленька цінність, і ми хочемо, щоб порівняти його. 1413 00:59:44,766 --> 00:59:47,090 Що ми хочемо, щоб порівняти його з? 1414 00:59:47,090 --> 00:59:48,730 Це збирається бути це наступний, чи не так? 1415 00:59:48,730 --> 00:59:53,200 Тому ми хочемо, K, щоб ініціалізувати щоб я плюс 1, щоб почати. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> І ми хочемо, щоб до цього випадку ми вже розмір зберігаються тут, 1418 01:00:02,800 --> 01:00:03,930 так що ми можемо просто використовувати розмір. 1419 01:00:03,930 --> 01:00:06,240 Розмір будучи розмір масиву. 1420 01:00:06,240 --> 01:00:09,620 І ми просто хочемо, щоб оновити K на одиницю кожного разу. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Прохолодний. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Так що тепер ми повинні знайти найменший елемент тут. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Так що, якщо ми перебору, ми хочу сказати, якщо масив на к 1427 01:00:31,380 --> 01:00:37,080 менше нашого маленького value-- це де ми насправді 1428 01:00:37,080 --> 01:00:42,950 відстежування того, що це найменший here-- 1429 01:00:42,950 --> 01:00:47,740 Потім ми хочемо передати що наша маленька величина. 1430 01:00:47,740 --> 01:00:50,645 >> Це означає, що, ну, ми перебору тут. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Незалежно від значення тут не наш маленький річ. 1433 01:00:53,740 --> 01:00:54,448 Ми не хочемо його. 1434 01:00:54,448 --> 01:00:56,100 Ми хочемо, щоб перепризначити його. 1435 01:00:56,100 --> 01:01:02,050 Так що, якщо ми перепризначення його, що робити Ви думаєте, може бути в цьому коді тут? 1436 01:01:02,050 --> 01:01:04,160 Ми хочемо, щоб перепризначити маленький і положення. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Так що це найменший в даний час? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 СТУДЕНТ: Array к. 1441 01:01:09,130 --> 01:01:09,963 ВИКЛАДАЧ: Array к. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 І те, що це положення зараз? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Що індекси наша найменше значення? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Це просто к. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Так масиву К, К, вони збігаються. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Таким чином, ми хотіли передати це. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 А потім, коли ми виявили, що наш маленький, так в кінці цього для петлі 1454 01:01:39,950 --> 01:01:45,100 Тут ми знайшли те, що наш маленький значення, так що ми просто поміняти його. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 В цьому випадку, як кажуть наші Найменше значення тут. 1457 01:01:50,816 --> 01:01:51,940 Це наша найменше значення. 1458 01:01:51,940 --> 01:01:57,690 >> Ми просто хочемо, щоб поміняти його тут, який є що це функція підкачки на дні 1459 01:01:57,690 --> 01:02:01,270 зробив, який ми щойно написали разом пару хвилин тому. 1460 01:02:01,270 --> 01:02:02,775 Так воно і має виглядати знайомим. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 І тоді це буде просто перебирати через поки він не досягне упору 1463 01:02:08,030 --> 01:02:13,100 до кінця, а це означає, що вас мають нульові елементи, які без сортування 1464 01:02:13,100 --> 01:02:14,800 а все інше було розібратися. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Зробити сенс? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Трохи більше конкретно? 1469 01:02:19,280 --> 01:02:19,990 Код допомога? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> не студенти: Для розміру, ви ніколи дійсно визначити або змінити його, 1472 01:02:26,410 --> 01:02:27,340 як це дізнатися? 1473 01:02:27,340 --> 01:02:32,380 >> ВИКЛАДАЧ: Так одна справа помітити тут є розмір внутр. 1474 01:02:32,380 --> 01:02:35,680 Так ми говоримо в цьому sort-- роду є функція в цьому case-- це 1475 01:02:35,680 --> 01:02:40,770 Вибір роду, він пройшов В з функцією. 1476 01:02:40,770 --> 01:02:43,460 Так що, якщо він не був прийнятий в, ви могли б зробити щось 1477 01:02:43,460 --> 01:02:47,840 як з довжиною масиву або ви б перебору 1478 01:02:47,840 --> 01:02:49,390 щоб знайти довжину. 1479 01:02:49,390 --> 01:02:52,680 Але тому що це пройшло в, ми можемо просто використовувати його. 1480 01:02:52,680 --> 01:02:55,720 Ви просто припустимо, що користувач дав вам правильний розмір, що 1481 01:02:55,720 --> 01:02:57,698 насправді являє розмір вашого масиву. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Прохолодний? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Якщо ви, хлопці, є які-небудь проблеми з цим або хочете більше практики кодування види 1486 01:03:05,870 --> 01:03:08,050 на свій розсуд, ви повинні перейти до study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Це інструмент. 1489 01:03:12,670 --> 01:03:15,040 У них є перевірки, що Ви можете фактично писати. 1490 01:03:15,040 --> 01:03:16,180 Вони роблять псевдокод. 1491 01:03:16,180 --> 01:03:19,310 Вони мають більше відео та слайди в тому числі і я використовую тут. 1492 01:03:19,310 --> 01:03:23,150 Так що якщо ви все ще відчуваєте трохи нечіткої, спробуйте це. 1493 01:03:23,150 --> 01:03:25,670 Як завжди, прийшов поговорити зі мною, теж. 1494 01:03:25,670 --> 01:03:26,320 Питання? 1495 01:03:26,320 --> 01:03:28,611 >> СТУДЕНТ: Ви хочете сказати, розмір визначено раніше? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 ВИКЛАДАЧ: Так. 1498 01:03:29,900 --> 01:03:35,570 Розмір попередньо визначена з точністю тут в оголошенні функції. 1499 01:03:35,570 --> 01:03:39,060 Таким чином, ви припустити, що це було прийнято в користувачем, і для простоти, 1500 01:03:39,060 --> 01:03:41,896 ми будемо вважати, що Користувач дав нам правильний розмір. 1501 01:03:41,896 --> 01:03:43,240 Прохолодний. 1502 01:03:43,240 --> 01:03:44,390 Так от вибір роду. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Хлопці, я знаю, сьогодні ми дізналися багато. 1505 01:03:47,640 --> 01:03:49,710 Це щільна дані для розділу. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Так з цим, ми збираємося піти в сортування вставками. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> Добре. 1510 01:04:02,510 --> 01:04:06,100 Тому, перш ніж, що ми повинні зробити, наш аналіз виконання тут. 1511 01:04:06,100 --> 01:04:10,190 Таким чином, в кращому випадку, надається, так як я показав вам, 1512 01:04:10,190 --> 01:04:11,960 таблиця я вже вид віддав його. 1513 01:04:11,960 --> 01:04:15,430 Але найкраще справа часу виконання, що ми думаємо? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Все відсортовано. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N в квадраті. 1518 01:04:22,070 --> 01:04:24,780 Будь, є пояснення чому ви думаєте? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> СТУДЕНТ: ви порівнюєте through-- 1521 01:04:30,519 --> 01:04:31,268 ВИКЛАДАЧ: справа. 1522 01:04:31,268 --> 01:04:32,540 Ти порівняння через. 1523 01:04:32,540 --> 01:04:35,630 На кожній ітерації, незважаючи на те, ми зменшуючи це один, 1524 01:04:35,630 --> 01:04:38,950 Ви все ще шукаєте через все, щоб знайти самі маленькі. 1525 01:04:38,950 --> 01:04:42,390 Таким чином, навіть якщо ваша найменше значення Тут на початку, 1526 01:04:42,390 --> 01:04:44,710 Ви все ще порівнюючи його проти всього іншого 1527 01:04:44,710 --> 01:04:46,550 щоб переконатися, що це найменше. 1528 01:04:46,550 --> 01:04:49,820 Таким чином, ви будете в кінцевому підсумку працює через приблизно н квадраті разів. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Добре. 1531 01:04:51,590 --> 01:04:52,785 І те, що в гіршому випадку? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Також п квадраті, бо ви збираєтеся щоб робити ту ж саму процедуру. 1534 01:04:57,980 --> 01:05:01,670 Так, в даному випадку, вибір зразок є щось 1535 01:05:01,670 --> 01:05:04,010 що ми називаємо очікуваний час виконання. 1536 01:05:04,010 --> 01:05:07,400 Таким чином, в інших, ми просто знаємо, верхні та нижні межі. 1537 01:05:07,400 --> 01:05:11,180 Залежно від того, як з розуму нашого Список або як несортоване це, 1538 01:05:11,180 --> 01:05:15,350 вони різняться між п або п квадрата. 1539 01:05:15,350 --> 01:05:16,550 Ми не знаємо. 1540 01:05:16,550 --> 01:05:22,820 >> Але через вибору роду має те ж саме найгірше і найкраще справу, що говорить нам, що 1541 01:05:22,820 --> 01:05:25,880 незалежно від того, який тип введення ми Тобто, чи є це повністю 1542 01:05:25,880 --> 01:05:29,130 упорядковано або повністю зворотна сортуються, це 1543 01:05:29,130 --> 01:05:30,740 збирається взяти таку ж кількість часу. 1544 01:05:30,740 --> 01:05:33,760 Так що в цьому випадку, якщо ви пам'ятаєте з нашої таблиці, 1545 01:05:33,760 --> 01:05:38,610 він насправді має значення, що ці два види не мають, 1546 01:05:38,610 --> 01:05:40,390 який, як очікується, під час виконання. 1547 01:05:40,390 --> 01:05:43,350 Отже, ми знаємо, що всякий раз, коли ми біжимо вибору роду, 1548 01:05:43,350 --> 01:05:45,380 це гарантовано запустити н квадраті час. 1549 01:05:45,380 --> 01:05:46,630 Там немає мінливість є. 1550 01:05:46,630 --> 01:05:47,630 Це просто очікував. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 І, знову ж таки, якщо ви хочете дізнатися, Більш того, прийняти CS 124 навесні. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Добре. 1555 01:05:56,712 --> 01:05:57,545 Ми бачили це. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Прохолодний. 1558 01:05:59,030 --> 01:06:00,930 Так вставок. 1559 01:06:00,930 --> 01:06:03,330 І я, ймовірно, прокласти через це. 1560 01:06:03,330 --> 01:06:05,440 Я не дозволю тобі хлопці кодувати його. 1561 01:06:05,440 --> 01:06:06,580 Ми просто пройти через це. 1562 01:06:06,580 --> 01:06:10,500 Так вставок добр з схожий на вибір роду 1563 01:06:10,500 --> 01:06:14,460 в тому, що у нас є і несортоване і сортують частина масиву. 1564 01:06:14,460 --> 01:06:20,260 >> Але те, що відрізняється тим, що як ми проходимо через один за іншим, 1565 01:06:20,260 --> 01:06:24,210 ми просто взяти будь-який номер є наступним у наш несортовані, 1566 01:06:24,210 --> 01:06:28,507 і правильно сортувати його в нашому масиві. 1567 01:06:28,507 --> 01:06:30,090 Це матиме більше сенсу з прикладу. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Так що все починається як несортовані, точно так само як з вибору сорту. 1570 01:06:35,430 --> 01:06:38,740 І ми збираємося, щоб залагодити це в порядку зростання, як ми були. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Так на нашому першому проході ми беремо перше значення 1573 01:06:43,340 --> 01:06:46,700 і ми говоримо, добре, ви Тепер в списку по собі. 1574 01:06:46,700 --> 01:06:49,150 >> Тому що ви перебуваєте в списку самостійно, ви сортуються. 1575 01:06:49,150 --> 01:06:52,460 Вітаємо бути Перший елемент в цьому масиві. 1576 01:06:52,460 --> 01:06:54,800 Ви вже відсортовані все на свій розсуд. 1577 01:06:54,800 --> 01:06:58,900 Так що тепер ми сортуються і несортоване масив. 1578 01:06:58,900 --> 01:07:01,760 Так що тепер ми візьмемо перший. 1579 01:07:01,760 --> 01:07:05,600 Що відбувається між здесь і в тому, що ми говоримо: 1580 01:07:05,600 --> 01:07:08,890 Добре, ми будемо дивитися на Перше значення нашої несортоване масиву 1581 01:07:08,890 --> 01:07:13,270 і ми збираємося ввести його в своїй правильне місце в масиві. 1582 01:07:13,270 --> 01:07:21,460 >> Отже, що ми робимо, ми беремо 5 і ми говоримо, добре, 5 більше 3, 1583 01:07:21,460 --> 01:07:24,630 так що ми просто вставте його право праворуч, що. 1584 01:07:24,630 --> 01:07:25,130 Ми добре. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Отже ми переходимо до нашої наступної. 1587 01:07:28,420 --> 01:07:29,720 І ми беремо 2. 1588 01:07:29,720 --> 01:07:34,330 Ми говоримо, добре, 2 менше ніж 3, так що ми знаємо, що це 1589 01:07:34,330 --> 01:07:36,220 повинен бути в Фронт нашому списку тепер. 1590 01:07:36,220 --> 01:07:41,800 Так що ми робимо, ми натискаємо 3 і 5 вниз і ми рухаємося 2 в той перший слот. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Таким чином, ми просто вставивши його в правильне місце це повинно бути. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Тоді ми подивимося на наш Наступний, і ми говоримо, 6. 1595 01:07:49,470 --> 01:07:53,620 ОК, 6 більше, ніж все в нашому масиві, 1596 01:07:53,620 --> 01:07:56,000 так що ми просто помітити його до кінця. 1597 01:07:56,000 --> 01:07:56,960 А потім ми дивимося на 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 менше, ніж 6, це менше, ніж 5, але це більше, ніж 3. 1600 01:08:03,020 --> 01:08:06,270 Так що ми просто вставити його прямо в посередині між 3 і 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Таким чином, щоб зробити що трохи трохи більш конкретними, 1603 01:08:10,530 --> 01:08:12,280 ось ніби Ідея про те, що сталося. 1604 01:08:12,280 --> 01:08:16,430 Таким чином, для кожного несортоване елемента, ми визначити, де в відсортованому частини 1605 01:08:16,430 --> 01:08:17,090 це. 1606 01:08:17,090 --> 01:08:20,680 >> Так маючи на увазі, в сортуються і несортовані, 1607 01:08:20,680 --> 01:08:26,080 ми повинні пройти через і фігура , Де вона вписується в масиві. 1608 01:08:26,080 --> 01:08:31,460 І ми вставляємо його, зрушуючи елементи праворуч від нього вниз. 1609 01:08:31,460 --> 01:08:34,910 А потім ми просто тримати НЕ перебір, поки ми 1610 01:08:34,910 --> 01:08:39,270 є повністю відсортований список де несортоване тепер дорівнює нулю 1611 01:08:39,270 --> 01:08:41,720 і відсортоване займає Сукупність нашому списку. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Так, знову ж таки, щоб зробити речі ще більш конкретне, у нас є псевдокода. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Тому в основному для я це дорівнює 0 до п мінус 1, 1616 01:08:52,410 --> 01:08:54,790 от тільки довжина нашого масиву. 1617 01:08:54,790 --> 01:09:00,979 Ми маємо певний елемент, який дорівнює Перший масив або перші показники. 1618 01:09:00,979 --> 01:09:03,200 Ми ставимо J, рівну. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Таким чином, хоча J більше нулю, а масив, J мінус 1 1621 01:09:09,210 --> 01:09:11,660 більше, ніж елемент, так що все, що робить 1622 01:09:11,660 --> 01:09:17,479 переконавшись, що Ваше J дійсно являє 1623 01:09:17,479 --> 01:09:20,010 без сортування частина масиву. 1624 01:09:20,010 --> 01:09:30,745 >> Так, поки ще є речі, сортувати і J мінус один is-- що 1625 01:09:30,745 --> 01:09:31,840 є елементом її? 1626 01:09:31,840 --> 01:09:34,760 J ніколи не визначається тут. 1627 01:09:34,760 --> 01:09:35,677 Це свого роду дратує. 1628 01:09:35,677 --> 01:09:36,176 Добре. 1629 01:09:36,176 --> 01:09:36,689 В кожному разі. 1630 01:09:36,689 --> 01:09:39,899 Так J мінус 1, ви перевіряєте елемент перед ним. 1631 01:09:39,899 --> 01:09:46,460 Ви хочете сказати, що, в порядку, це елемент до куди б я не am-- давайте 1632 01:09:46,460 --> 01:09:47,540 насправді зробити це. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Так скажімо, це як на нашому другому проході. 1635 01:09:56,830 --> 01:09:59,525 Так що я дорівнюватиме 1, яка знаходиться тут. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Таким чином, я маю намір бути рівний 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Це було б 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Добре. 1642 01:10:16,750 --> 01:10:20,945 Таким чином, наш елемент в даному випадку буде дорівнює 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 І у нас є деякий J Ось буде дорівнює 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 О, J є зменшуючи. 1647 01:10:30,971 --> 01:10:31,720 Ось що це таке. 1648 01:10:31,720 --> 01:10:35,680 Так J дорівнює I, так що це говориться, що, як ми рухаємося вперед, 1649 01:10:35,680 --> 01:10:37,530 ми тільки переконавшись, що ми не більш 1650 01:10:37,530 --> 01:10:43,520 індексації цей шлях, коли ми намагаємося вставити речі в нашому упорядкованому списку. 1651 01:10:43,520 --> 01:10:49,850 >> Тому, коли J дорівнює 1, в цьому випадку і Масив J мінус одно-- так масив J мінус 1 1652 01:10:49,850 --> 01:10:54,610 2 в цьому case-- якщо це більше, ніж елемент, 1653 01:10:54,610 --> 01:10:57,700 Потім все це робить зміщується речі вниз. 1654 01:10:57,700 --> 01:11:04,790 Так, в даному випадку, масив J мінус один Масив буде нульовим, який є 2. 1655 01:11:04,790 --> 01:11:08,430 2 максимум, ніж 4, так що це не виконується. 1656 01:11:08,430 --> 01:11:11,460 Так зрушення не з'їжджати. 1657 01:11:11,460 --> 01:11:18,790 Що це робить тут просто переміщення відсортований масив вниз. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 В цьому випадку, насправді, ми може do-- давайте зробимо це 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Так що, якщо ми хочемо йти через с цей приклад, ми зараз тут. 1662 01:11:31,970 --> 01:11:32,740 Це сортується. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Це несортоване. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Прохолодний? 1667 01:11:39,860 --> 01:11:46,620 Так я дорівнює 2, так наш елемент дорівнює 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 І наша J дорівнює 2. 1670 01:11:52,270 --> 01:12:00,620 Таким чином, ми з нетерпінням через і ми сказати, в порядку, це масив J мінус один 1671 01:12:00,620 --> 01:12:03,470 більше, ніж елемента що ми дивимося? 1672 01:12:03,470 --> 01:12:05,540 І так, чи не так? 1673 01:12:05,540 --> 01:12:11,275 4 більше, ніж 3 і J 2, так що цей код виконується. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Так що тепер, що ми робимо масив на 2, так прямо тут, ми поміняти їх місцями. 1676 01:12:18,550 --> 01:12:25,620 Таким чином, ми просто сказати: ОК, масив на 2 тепер буде 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 І J збирається рівнятися J мінус 1, який дорівнює 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Це жахливо, але ви, хлопці, отримаєте цю ідею. 1681 01:12:37,200 --> 01:12:38,360 J тепер дорівнює 1. 1682 01:12:38,360 --> 01:12:44,360 І масив J тільки збирається бути дорівнює нашого елемента, який був 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Я стер щось я не повинен є або miswrote-то, 1685 01:12:48,570 --> 01:12:49,910 але ви, хлопці, отримаєте цю ідею. 1686 01:12:49,910 --> 01:12:50,640 >> Це рухатися в п. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 І потім, якби це було, це було б петля знову, і це було б сказати, в порядку, J = 1 тепер. 1689 01:12:57,960 --> 01:13:00,665 І масив J мінус 1 тепер 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Є 2 менше, ніж наші елемента? 1692 01:13:03,760 --> 01:13:04,540 Ні? 1693 01:13:04,540 --> 01:13:07,970 Це означає, що ми в вставляється цей елемент 1694 01:13:07,970 --> 01:13:10,110 в правильному місці в нашому масиві. 1695 01:13:10,110 --> 01:13:14,400 Тоді ми можемо взяти це, і ми говоримо, ОК, наш упорядкований масив тут. 1696 01:13:14,400 --> 01:13:19,940 І це було б взяти цей номер 6 і бути як, в порядку, становить 6 менше, ніж це число? 1697 01:13:19,940 --> 01:13:20,480 Ні? 1698 01:13:20,480 --> 01:13:21,080 Прохолодний. 1699 01:13:21,080 --> 01:13:22,680 У нас все добре. 1700 01:13:22,680 --> 01:13:23,530 >> Зробіть це знову. 1701 01:13:23,530 --> 01:13:24,740 Ми говоримо, 7. 1702 01:13:24,740 --> 01:13:29,010 Є 7 менше, ніж наприкінці нашої масиві? 1703 01:13:29,010 --> 01:13:29,520 Ні. 1704 01:13:29,520 --> 01:13:30,430 Так що ми в порядку. 1705 01:13:30,430 --> 01:13:32,760 Так що це буде відсортований. 1706 01:13:32,760 --> 01:13:38,610 В основному все це робить Хіба це говорить дубль 1707 01:13:38,610 --> 01:13:42,060 Перший елемент Ваш несортоване масив, 1708 01:13:42,060 --> 01:13:46,010 з'ясувати, де він йде в масиві. 1709 01:13:46,010 --> 01:13:48,780 І це тільки дбає свопів, щоб зробити це. 1710 01:13:48,780 --> 01:13:51,300 Ви в основному просто помінявши поки це не в потрібному місці. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 Візуальний образ, що ви рухається все вниз, роблячи це. 1713 01:13:56,990 --> 01:13:59,420 >> Так що це як половина бульбашкового сортування в стилі. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Перевірте дослідження 50. 1716 01:14:03,420 --> 01:14:06,000 Я дуже рекомендую спробу закодувати це на свій власний. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Якщо у вас є які-небудь питання або ви хочете см приклад коду для вставки роду, 1719 01:14:12,450 --> 01:14:13,750 будь ласка, дай мені знати. 1720 01:14:13,750 --> 01:14:14,500 Я завжди навколо. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Так гіршому випадку виконання і кращий випадок виконання. 1723 01:14:20,200 --> 01:14:30,700 Як ви хлопець побачив з-за столу, я вже показав вам, що це як н в квадрат і н. 1724 01:14:30,700 --> 01:14:35,590 >> Так начебто йти від того, що ми говорили про наших попередніх пологах, найгірше 1725 01:14:35,590 --> 01:14:38,760 Справа в тому, що під час виконання, якщо це повністю Unsorted, 1726 01:14:38,760 --> 01:14:42,530 ми повинні порівняти всі ці п раз. 1727 01:14:42,530 --> 01:14:47,020 Ми робимо купу порівнянь тому що, якщо це в зворотному порядку, 1728 01:14:47,020 --> 01:14:50,360 ми збираємося сказати, в порядку, це це те ж саме, це добре, 1729 01:14:50,360 --> 01:14:54,650 і цей повинен буде порівнюватися проти першого перенести назад. 1730 01:14:54,650 --> 01:14:56,710 І, як ми отримаємо до кінець хвоста, у нас є 1731 01:14:56,710 --> 01:14:59,440 порівнювати, зіставляти, та порівняти проти всього. 1732 01:14:59,440 --> 01:15:03,030 >> Так він опинився приблизно н квадрат. 1733 01:15:03,030 --> 01:15:09,510 Якщо це правильно, то ви сказати, в порядку, 2, ви добре. 1734 01:15:09,510 --> 01:15:11,330 3, ви порівняно з 2. 1735 01:15:11,330 --> 01:15:12,310 Ти хороший. 1736 01:15:12,310 --> 01:15:14,150 4, ви просто порівняйте з хвостом. 1737 01:15:14,150 --> 01:15:14,990 Ти хороший. 1738 01:15:14,990 --> 01:15:17,140 6, в порівнянні з хвоста, ви прекрасні. 1739 01:15:17,140 --> 01:15:20,870 Таким чином, для кожного місця, якщо це вже сортуються, ви робите одне порівняння. 1740 01:15:20,870 --> 01:15:22,320 Так що це просто п. 1741 01:15:22,320 --> 01:15:26,840 І тому, що у нас є кращий випадок виконання п і гіршому разі виконання п 1742 01:15:26,840 --> 01:15:28,680 квадрат, у нас немає ніякої очікуваного виконання. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Все залежить від хаос нашому списку немає. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 І знову, другий Графік та інший стіл. 1747 01:15:39,530 --> 01:15:41,170 Так відмінностей між видами. 1748 01:15:41,170 --> 01:15:44,180 Я просто хочу, щоб вітер через, я відчуваю, що ми говорили докладно 1749 01:15:44,180 --> 01:15:46,570 про те, як вони всіх видів з змінюватися і зв'язати разом. 1750 01:15:46,570 --> 01:15:50,564 Так сортування злиттям є останнім Я буду втомлювати вас, хлопці с. 1751 01:15:50,564 --> 01:15:52,105 У нас є досить барвисту картину. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Так зливаються роду є рекурсивний алгоритм. 1754 01:15:56,040 --> 01:15:59,910 Так що ви, хлопці, знаєте, що рекурсивна функція? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Хто-небудь хоче сказати? 1757 01:16:03,320 --> 01:16:04,739 Ви хочете спробувати? 1758 01:16:04,739 --> 01:16:07,280 Так рекурсивна функція є просто функція, яка називає себе. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Так що, якщо ви, хлопці, знайомі з послідовністю Фібоначчі, 1761 01:16:11,590 --> 01:16:15,670 який вважається рекурсивним тому ви берете дві попередні 1762 01:16:15,670 --> 01:16:17,530 і додати їх разом щоб отримати наступний. 1763 01:16:17,530 --> 01:16:21,440 Так рекурсивної, я завжди думаю, рекурсії як як спіраль 1764 01:16:21,440 --> 01:16:24,430 так що ви, як по спіралі вниз в нього. 1765 01:16:24,430 --> 01:16:27,150 Але це всього лише функція яка називає себе. 1766 01:16:27,150 --> 01:16:32,660 >> І, насправді, дуже швидко я може показати вам, як це виглядає. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Так рекурсивний тут, якщо ми подивимося, що це рекурсивний спосіб підсумовувати масив. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Так що все, що ми робимо, у нас є функція суми 1771 01:16:47,880 --> 01:16:52,210 Сума, яка приймає розмір і масив. 1772 01:16:52,210 --> 01:16:55,210 І якщо ви помітили, розмір зменшується на одиницю кожного разу. 1773 01:16:55,210 --> 01:17:00,365 І все це робить, якщо х одно zero-- так що якщо розмір масиву 1774 01:17:00,365 --> 01:17:02,710 дорівнює zero-- повертається нуль. 1775 01:17:02,710 --> 01:17:10,440 >> В іншому випадку це підводить це Останній елемент масиву, 1776 01:17:10,440 --> 01:17:14,790 а потім приймає суму інша частина масиву. 1777 01:17:14,790 --> 01:17:17,555 Так що це просто розбити його на все більш дрібні проблеми. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Коротше кажучи, рекурсія, Функція, яка називає себе. 1780 01:17:21,890 --> 01:17:25,740 Якщо це все, що ви вийшли з цього, це те, що рекурсивна функція. 1781 01:17:25,740 --> 01:17:29,870 Якщо взяти 51, ви отримаєте дуже, дуже зручно за допомогою рекурсії. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Це дійсно здорово. 1784 01:17:32,370 --> 01:17:34,660 Це мало сенс в подібному 3 ранку одного разу вночі. 1785 01:17:34,660 --> 01:17:37,900 І я подумала: чому Не я не використовую це? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Таким чином, для сортування злиттям, в основному що він збирається зробити, це це 1788 01:17:42,430 --> 01:17:45,620 збираюся розбити його і розбити його вниз, поки це не просто окремі елементи. 1789 01:17:45,620 --> 01:17:47,570 Окремі елементи легко відсортувати. 1790 01:17:47,570 --> 01:17:48,070 Ми бачимо, що. 1791 01:17:48,070 --> 01:17:50,760 Якщо у вас є один елемент, це вже вважається відсортований. 1792 01:17:50,760 --> 01:17:53,800 Так на вході п елементів, якщо п менше, ніж 2, 1793 01:17:53,800 --> 01:17:58,120 просто повернути, тому що це означає, що це або 0, або 1, як ми вже бачили. 1794 01:17:58,120 --> 01:18:00,050 Ті, вважаються відсортовані елементи. 1795 01:18:00,050 --> 01:18:02,170 >> В іншому випадку розірвати його навпіл. 1796 01:18:02,170 --> 01:18:06,336 Сортувати першу половину, відсортувати другий половина, а потім об'єднати їх разом. 1797 01:18:06,336 --> 01:18:07,460 Чому це називається сортування злиттям. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Таким чином, ми маємо тут ми будемо сортувати ці. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Так ми продовжуємо мати їх доти, поки розмір масиву дорівнює 1. 1802 01:18:17,210 --> 01:18:20,790 Тому, коли це 1, ми просто повернутися бо це упорядкований масив, 1803 01:18:20,790 --> 01:18:23,940 і це упорядкований масив, і це упорядкований масив, ми все розібралися. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Отже, що ми робимо, ми почати злиття їх разом. 1806 01:18:29,420 --> 01:18:31,820 >> Так як ви можете думати про злиття 1807 01:18:31,820 --> 01:18:36,240 Ви просто видаліть менше Кількість кожного з масивів суб 1808 01:18:36,240 --> 01:18:38,330 і просто додати його в сформованій масиву. 1809 01:18:38,330 --> 01:18:44,290 Так що, якщо ви подивіться тут, коли у нас є ці набори у нас є 4, 6 і 1. 1810 01:18:44,290 --> 01:18:47,280 Коли ми хочемо об'єднати ці, ми дивимося на цих перших двох 1811 01:18:47,280 --> 01:18:50,730 і ми говоримо, добре, 1 менше, він іде на фронт. 1812 01:18:50,730 --> 01:18:54,330 4 і 6, немає нічого, щоб порівняти це, просто помітити його до кінця. 1813 01:18:54,330 --> 01:18:58,020 >> Коли ми об'єднуємо ці два, ми просто взяти менший один з цих двох, 1814 01:18:58,020 --> 01:18:59,310 так що це 1. 1815 01:18:59,310 --> 01:19:01,690 А тепер візьмемо Менше з цих двох, так 2. 1816 01:19:01,690 --> 01:19:03,330 Менше цих двох, 3. 1817 01:19:03,330 --> 01:19:06,260 Менше цих двох, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 Таким чином, ви просто стягуючи їх. 1819 01:19:08,630 --> 01:19:11,210 І тому, що у них є відсортовані раніше, 1820 01:19:11,210 --> 01:19:14,300 Ви тільки один з них Порівняння щоразу там. 1821 01:19:14,300 --> 01:19:19,610 Так більше коду тут, просто уявлення. 1822 01:19:19,610 --> 01:19:24,410 Таким чином, ви починаєте в середині і ви як би лівий і правий 1823 01:19:24,410 --> 01:19:26,180 а потім ви просто об'єднати тих. 1824 01:19:26,180 --> 01:19:30,080 >> І ми не маємо код для злиття прямо тут. 1825 01:19:30,080 --> 01:19:34,110 Але, знову ж таки, якщо ви йдете на вчитися 50, він буде там. 1826 01:19:34,110 --> 01:19:36,860 В іншому випадку прийшов поговорити зі мною якщо ви досі плутають. 1827 01:19:36,860 --> 01:19:42,340 Так здорово, що тут є те, що найкраще так, в гіршому випадку, і очікується, середа 1828 01:19:42,340 --> 01:19:46,250 все в журналі п, набагато краще, ніж ми 1829 01:19:46,250 --> 01:19:48,000 видно для іншої частини наших сортів. 1830 01:19:48,000 --> 01:19:51,840 Ми бачили н квадраті і те, що ми насправді 1831 01:19:51,840 --> 01:19:54,380 отримати тут п увійти н, який є великим. 1832 01:19:54,380 --> 01:19:55,830 >> Подивіться, як багато краще, що є. 1833 01:19:55,830 --> 01:19:56,780 Такий хороший крива. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Так набагато більш ефективним. 1836 01:20:00,120 --> 01:20:03,510 Якщо ви коли-небудь може, використання сортування злиттям. 1837 01:20:03,510 --> 01:20:04,810 Це допоможе вам заощадити час. 1838 01:20:04,810 --> 01:20:07,670 З іншого боку, як ми вже говорили, якщо ви вниз в цій нижній області, 1839 01:20:07,670 --> 01:20:09,480 це не робить, що особливої ​​різниці. 1840 01:20:09,480 --> 01:20:11,360 Ви отримуєте до тисячі і тисячі входів, 1841 01:20:11,360 --> 01:20:13,318 ви безумовно хочете більш ефективний алгоритм. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 І, знову ж таки, наша прекрасна таблиця всіх види, що ви, хлопці дізналися сьогодні. 1844 01:20:19,400 --> 01:20:21,157 >> Так що я знаю, це був щільний день. 1845 01:20:21,157 --> 01:20:23,490 Це не обов'язково відбувається щоб допомогти вам з вашою PSET. 1846 01:20:23,490 --> 01:20:28,250 Але я просто хочу зробити застереження що ця частина не тільки про psets. 1847 01:20:28,250 --> 01:20:31,240 Весь цей матеріал є справедливим гра для ваших проміжних виборах. 1848 01:20:31,240 --> 01:20:35,430 А також, якщо ви продовжувати з CS, це дійсно важливі засади 1849 01:20:35,430 --> 01:20:37,870 що ви повинні були б знати. 1850 01:20:37,870 --> 01:20:41,700 Так кілька днів буде трохи більше PSET допомогу, 1851 01:20:41,700 --> 01:20:44,600 але через кілька тижнів буде набагато більш реальний зміст 1852 01:20:44,600 --> 01:20:46,600 що може здатися не супер корисною для вас прямо зараз, 1853 01:20:46,600 --> 01:20:51,215 але я обіцяю, якщо ви будете продовжувати на буде дуже, дуже корисно. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Так ось саме для розділу. 1856 01:20:54,250 --> 01:20:55,250 Вниз до дроту. 1857 01:20:55,250 --> 01:20:56,570 Я зробив це протягом однієї хвилини. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Але там ви йдете. 1860 01:20:58,970 --> 01:21:01,240 І в мене буде пончики або цукерки. 1861 01:21:01,240 --> 01:21:03,464 Хто-небудь алергія на що-небудь, до речі? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Яйця і молоко. 1864 01:21:05,890 --> 01:21:08,120 Так що пончики нє? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 Добре. 1867 01:21:10,160 --> 01:21:10,770 Добре. 1868 01:21:10,770 --> 01:21:12,120 Шоколад ні? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts хороші. 1872 01:21:14,670 --> 01:21:15,170 Добре. 1873 01:21:15,170 --> 01:21:17,045 Ми збираємося мати Starburst на наступному тижні, то. 1874 01:21:17,045 --> 01:21:18,240 Це те, що я отримаю. 1875 01:21:18,240 --> 01:21:19,690 Ви, хлопці, є велика тиждень. 1876 01:21:19,690 --> 01:21:20,460 Прочитайте специфікацію. 1877 01:21:20,460 --> 01:21:22,130 >> Дайте мені знати, якщо у вас є які-небудь питання. 1878 01:21:22,130 --> 01:21:25,300 Pset два сорти повинні бути до вас на четвер. 1879 01:21:25,300 --> 01:21:28,320 Якщо у вас є які-небудь питання про те, як я класифікуються щось 1880 01:21:28,320 --> 01:21:32,250 або чому я класифікуються щось, як я так, будь ласка, напишіть мені, приходять поговорити зі мною. 1881 01:21:32,250 --> 01:21:34,210 Я ледве з розуму в цьому тиждень, але я обіцяю, 1882 01:21:34,210 --> 01:21:36,340 Я до сих пір відповісти протягом 24 годин. 1883 01:21:36,340 --> 01:21:38,240 Так є великий тиждень, все. 1884 01:21:38,240 --> 01:21:40,090 Удачи на PSET. 1885 01:21:40,090 --> 01:21:41,248