[Powered by Google Translate] [Розділ 3 - більш комфортною]
[Rob Боуден - Гарвардський університет]
>> [Це CS50. - CS50.TV]
>> Отже, перше питання сформульовано дивно.
GDB дозволяє вам "налагодження" програми, але, більш конкретно, що це дозволить вам робити?
Я відповім, що один, і я не знаю, що саме очікував,
таким чином, я припускаю, що це щось подібне вона дозволяє крок за кроком
йти через програми, взаємодіяти з ним, змінювати перемінні, робити всі ці речі -
в основному повністю контролювати виконання програми
і перевіряти будь-якій частині виконання програми.
Таким чином, ці функції дозволяють відлагоджувати речі.
Добре.
Чому бінарний пошук вимагає, щоб масив буде відсортований?
Хто хоче відповісти?
[Студент] Тому що він не працює, якщо він не сортуються. >> Да. [Сміх]
Якщо це не відсортований, то неможливо розділити його навпіл
і знаю, що все, що лівіше менше і все, що правіше
більше середнього значення.
Таким чином, він повинен бути відсортований.
Добре.
Чому бульбашкового сортування в O п квадратів?
Хто-небудь спочатку хочу дати дуже швидкий високому рівні огляд того, що міхур сортування?
[Студент] Ви в основному йдуть через кожен елемент, і ви перевірити декілька перших елементів.
Якщо вони з того, де ви поміняти їх місцями, то перевірте наступні кілька елементів і так далі.
Коли ви дійдете до кінця, то ви знаєте, що найбільший елемент міститься в кінці,
так що ви ігноруєте, що один, то ви продовжуйте йти до кінця,
і кожного разу ви повинні перевірити один елемент менше, поки ви не вносити ніяких змін. >> Да.
Це називається бульбашкового сортування, тому що якщо перевернути масив на бік, так це вгору і вниз по вертикалі,
Потім великих значеннях буде опускатися на дно і малих значень буде пузиритися до самого верху.
Ось як він отримав свою назву.
І так, ви просто проходите.
Ви продовжуєте через масив, помінявши більшого значення
Для отримання найбільших значень на дно.
>> Чому це O п квадратів?
По-перше, хто-небудь хочу сказати, чому це O п квадратів?
[Студент] Тому що для кожного прогону він йде п раз.
Ви можете бути впевнені, що Ви зробили найважливіший елемент весь шлях вниз,
Потім вам доведеться повторити, що для, як багато елементів. >> Да.
Так що майте на увазі, що велика O означає і те, що великі кошти Omega.
The Big O, як верхня межа про те, як повільно він може реально працювати.
Так, кажучи, що це O п квадрат, це не про п інакше вона була б в змозі управляти
У лінійному часу, але це O п кубі
тому що вона обмежена O п куб.
Якщо це обмежена O п квадрат, то це обмежена також на п куб.
Так що п в квадраті, а в абсолютній гіршому випадку він не може робити краще, ніж N в квадраті,
Саме тому це O п квадрат.
Таким чином, щоб побачити невелике математиці, як вона виходить, щоб бути вказаний в квадраті,
якщо у нас є п'ять речей в нашому списку, в перший раз, скільки свопів ми могли б потенційно потрібно зробити
для того, щоб отримати? Давайте насправді просто -
Скільки свопи ми будемо мати, щоб зробити в першому запуску бульбашкового сортування в масиві?
[Студент] п - 1. >> Да.
>> Якщо є 5 елементів, ми збираємося потрібно зробити п - 1.
Тоді на другому скільки свопів ми будемо мати, щоб зробити?
[Студент] п - 2. >> Да.
І третій буде п - 3, а потім для зручності я буду писати в останні два
як і тоді, ми збираємося потрібно зробити 2 перестановок і 1 підкачки.
Я припускаю, що остання може або не може фактично повинні відбутися.
Це своп? Я не знаю.
Так що це загальна сума свопів або принаймні порівнянь ви повинні зробити.
Навіть якщо ви не поміняти, вам все ще потрібно порівняти значення.
Таким чином, існує п - 1 порівнянь в перші проходять через масив.
Якщо переставити ці речі, давайте насправді зробити це шість речей, так що все складається добре,
і тоді я зроблю 3, 2, 1.
Так що просто переставляючи ці суми, ми хочемо, щоб бачити, як багато порівнянь ми робимо
у всьому алгоритмом.
Таким чином, якщо ми принесемо ці хлопці тут,
Потім ми ще раз підбиваючи проте багато порівнянь було.
Але якщо ми підсумовуємо ці та підсумувати ці та підсумувати ці,
вона як і раніше така ж проблема. Ми просто підвести тих конкретних груп.
>> Отже, тепер ми підбиваючи N 3 в. Це не тільки 3 N.
Це завжди буде п / 2 N.
І ось ми, трапляється, є 6.
Якби ми мали 10 речей, то ми могли б зробити це угруповання на 5 різних пар речі
і в кінцевому підсумку з N + N + N + N + N.
Таким чином, ви завжди будете отримувати п / 2 п, і так це ми будемо записувати його на п квадрат / 2.
І хоча це фактор половини, які, трапляється, приходять в
у зв'язку з тим, що через кожну ітерацію по масиву ми порівняємо 1 менше
так що, як ми отримаємо понад 2, але він як і раніше п квадрат.
Ми не турбуємося про постійне факторі половини.
Так багато великих речей O, як це годиться тільки на вигляд робити такого роду математика,
арифметичних сум і геометричні матеріал серії,
але більшість з них в цьому курсі досить проста.
Добре.
Чому сортування вставкою в Omega п? Що омега значить?
[Двох студентів говорити відразу - нерозбірливо] >> Да.
Omega ви можете думати про якість нижньої межі.
>> Тому незалежно від того, наскільки ефективно ваша вставки Алгоритм сортування,
незалежно від того, список, який передається, він завжди має порівняти принаймні п речей
або воно має для перебору п речей.
Чому це відбувається?
[Студент] Тому що, якщо список вже відсортований, то через першу ітерацію
Ви можете гарантувати, що найперший елемент є принаймні,
і другої ітерації можна гарантувати тільки перші два
тому що ви не знаєте, що решті список відсортований. >> Да.
Якщо ви передаєте в повністю відсортований список, принаймні, ви повинні йти по всіх елементах
бачити, що нічого не потрібно переміщати.
Таким чином, що проходять за списком і говорять про, це вже відсортовані,
це неможливо, щоб ви знали, що це впорядковані, поки ви перевірити кожен елемент
, Щоб побачити, що вони в певному порядку.
Таким чином, нижня межа вставки сортування Omega н.
Те, що в гіршому випадку час роботи сортування злиттям,
гіршому випадку бути великим O знову?
Таким чином, в гіршому випадку, як же сортування злиттям бігти?
[Студент] N журнал п. >> Да.
Найшвидший загальні алгоритми сортування є п § п. Ви не можете зробити краще.
>> Існують особливі випадки, і якщо у нас є час сьогодні, - але ми, ймовірно won't -
ми могли бачити той, який робить краще, ніж п § п.
Але в загальному випадку, ви не можете зробити краще, ніж п § п.
І сортування злиттям, трапляється, яку ви повинні знати, для цього, звичайно, що п § п.
І тому ми фактично здійсненні цього сьогодні.
І, нарешті, не більше ніж у трьох реченнях, як працює вибору роду?
Хіба хтось хоче, щоб відповісти, і я буду вважати ваші пропозиції
тому що якщо ви йдете в протягом 3 -
Хтось пам'ятає вибір роду?
Вибір роду, як правило, досить легко запам'ятати, просто з назви.
Ви просто перебір масиву, знайти те, що найбільше значення є чи маленький -
незалежно від того, ви сортування дюйма
Так скажемо ми сортування від меншого до більшого.
Ви ітерації по масиву, дивлячись на все, що мінімальний елемент,
, Виділіть її, а потім просто замінити його те, що на перше місце.
І тоді на другому проході по масиву, зверніть увагу на мінімальний елемент знову,
, Виділіть її, а потім поміняти його з тим, що на другій позиції.
Так що ми просто вибираючи, мінімальні значення
і вставляючи їх в передній частині масиву, поки не буде відсортований.
Питань з цього приводу?
>> Це неминуче з'являються у формах ви повинні заповнити, коли ви відправляєте PSET.
Це в основному відповіді на них.
Отже, тепер проблеми з кодуванням.
Я вже розіслав по електронній пошті - Хто-небудь не отримаєте цей лист? Добре.
Я вже розіслав по електронній пошті простір, який ми збираємося використовувати,
і якщо ви клацніть на моє ім'я, - так що я думаю, що я збираюся бути на дні
через назад г - але якщо ви натиснете на моє ім'я, ви побачите 2 ревізії.
1-а редакція збирається бути я вже скопіювали і вставили код в просторах
для пошуку, що вам доведеться виконувати.
І Перегляд 2 буде сортувати речі, які ми реалізуємо після цього.
Таким чином, ви можете натиснути на мій Перегляд 1 і працювати там.
А тепер ми хочемо реалізувати бінарний пошук.
>> Хто-небудь хоче, щоб просто дати псевдокод високого рівня пояснення
про те, що ми збираємося потрібно зробити для пошуку? Так.
[Студент] Ви просто берете середині масиву і подивитися, якщо те, що ви шукаєте
менше, ніж або більше.
І якщо це менше, ви йдете в половину, що це менше,
а якщо більше, ви йдете в половину більше, і ви повторити, що, поки ви не просто отримаєте одну річ.
[Боуден] Так.
Зверніть увагу, що наші номери масив вже відсортований,
і так це означає, що ми можемо скористатися тим, що і ми могли б спочатку перевірити,
Добре, я шукаю номер 50.
Таким чином, я можу піти в середину.
Близький важко визначити, коли це парне число речей,
але давайте просто сказати, що ми завжди будемо обрізати до середини.
Так що тут у нас є 8 речей, так що середня буде 16.
Я шукаю 50, так 50 це більше, ніж 16.
Так що тепер я в принципі може ставитися до моїх масив цих елементів.
Я можу викинути все з 16 більш.
Тепер мій масив саме ці 4 елементи, і я повторю.
Так от я хочу знайти середину знову, що буде 42.
42 менше 50, так що я можу викинути ці два елементи.
Це моя залишилася масиву.
Я збираюся знайти середину знову.
Я думаю, 50 був поганий приклад, тому що я завжди викидати речі вліво,
але по тій же мірою, якщо я шукав щось
і це менше, ніж елемент В даний час я дивлюся,
Потім я збираюся викинути все, що правіше.
Отже, тепер ми повинні реалізувати це.
Зверніть увагу, що ми повинні передати в розмірах.
Ми можемо також не потрібно жорстко розмір коду.
Тому, якщо ми позбудемося # визначити -
Добре.
Як я можу добре зрозуміти, що розмір масиву номерів у даний час?
>> Скільки елементів у масиві чисел?
[Студент] Цифри, кронштейни,. Довжина?
[Боуден], якого не існує в C.
Вам потрібно. Довжини.
Масиви не мають властивості, тому немає Довжина властивість масивів
що буде просто дати вам як би довго воно відбудеться, буде.
[Студент] Див, скільки пам'яті вона має і розділити на скільки - >> Да.
Так як ми можемо подивитися, скільки пам'яті вона має? >> [Студент] Sizeof. >> Да, SizeOf.
Sizeof є оператором, який збирається повернути розмір масиву чисел.
І це буде, однак багато цілі Є моменти, розмір цілого
так це те, скільки пам'яті вона насправді займають.
Так що, якщо я хочу, щоб кількість речей в масиві,
Потім я збираюся хочуть розділити на розмір цілого числа.
Добре. Так, що дозволяє мені пройти в розмірі тут.
Чому я повинен пройти в розмірі взагалі?
Чому я не можу просто зробити тут Int розмір = SizeOf (копиці сіна) / SizeOf (INT)?
Чому це не працює?
[Студент] Це не глобальна змінна.
[Боуден] Haystack існує, і ми передаємо в цифрах, як копиця сіна,
і це начебто ознаку того, що має прийти. Так.
[Студент] Haystack це тільки посилання на нього, так що він повернеться, наскільки великий, що посилання.
Так.
Я сумніваюся, що в лекції, що ви бачили в стек ще насправді, чи не так?
Ми тільки що говорили про це.
Таким чином, стек, де всі ваші змінні будуть збережені.
>> Будь пам'ять яка виділяється для локальних змінних йде в стек,
і кожна функція отримує свій власний простір в стеку, його власний кадр стека, як це називається.
Таким чином, основна має свій стек, а всередині нього буде існувати цей номер масиву,
і вона буде розміром SizeOf (номера).
Це буде мати розмір чисел, розділених за розміром елементів,
але, що все живе в кадрі стека основного автора.
Коли ми викликаємо пошук, пошук отримує власний фрейм стеку,
свій власний простір для зберігання всіх своїх локальних змінних.
Але ці аргументи - так стозі сіна не є копією цього весь масив.
Ми не передаємо у всьому масиві у вигляді копії в пошуку.
Він просто передає посилання на цей масив.
Таким чином, пошук може отримати доступ до ці цифри через це посилання.
Він як і раніше доступ до речах, які живуть усередині стека основного автора,
але в основному, коли ми доберемося до покажчиків, які повинні бути найближчим часом,
це те, що покажчики.
Покажчики є просто посиланнями на речі, і ви можете використовувати покажчики для доступу до речі
, Які в рамках інших речей »стека.
Тому, навіть якщо номер є локальним для основного, ми все ще можемо отримати до нього доступ через цей покажчик.
Але так як це просто покажчик, і це просто посилання,
SizeOf (копиці сіна) просто повертає розмір самої посилання.
Він не повертає розмір річ, це вказує.
Він не повертає реальний розмір номерів.
І таким чином, це не буде працювати, як ми хочемо.
>> Питань з цього приводу?
Покажчики вже не буде в значно більш докладно в гори тижні.
І саме тому багато речей, які ви бачите, більшість речей, пошуку і сортування речей,
вони майже всі будете потребувати, щоб прийняти реальний розмір масиву,
тому що в C, ми поняття не маємо, що розмір масиву.
Вам потрібно вручну передати його дюйма
І ви не можете вручну передати у всьому масиві, тому що ви просто проходили у заслання
і він не може отримати розмір із заслання.
Добре.
Отже, тепер ми хочемо, щоб здійснити те, що було пояснено раніше.
Ви можете працювати на ньому протягом хвилини,
і вам не доведеться турбуватися про те, щоб всі прекрасно 100% робочий.
Просто напишіть до половини псевдокод, як ви думаєте, вона повинна працювати.
Добре.
Не потрібно бути повністю зробити з цим поки немає.
Але хто-небудь відчувати себе комфортно з тим, що вони до цих пір,
як те, що ми можемо працювати з разом?
Хто-небудь хоче стати волонтером? Або я випадково вибрати.
Це не повинно бути право на будь-які заходи, але дещо ми можемо змінити в робочому стані.
[Студент] Звичайно. >> Добре.
Таким чином, ви можете заощадити перегляду, натиснувши на маленьку іконку Зберегти.
Ти Ramya, вірно? >> [Студент] Так. >> [Боуден] Добре.
Так що тепер я можу переглядати перегляду і кожен може потягнути перегляду.
І тут ми маємо - Добре.
Так Ramya пішов з рекурсивне рішення, яке, безумовно, правильне рішення.
Є два шляхи ви можете зробити з цією проблемою.
Ви можете зробити це итеративно або рекурсивно.
Більшість проблем, ви виявите, що можна зробити рекурсивно також може бути зроблено итеративно.
Так от ми зробили це рекурсивно.
>> У кого-небудь хочу, щоб визначити, що означає зробити функцію рекурсивної?
[Студент] Якщо у вас є функція викликає сама себе
, А потім називати себе, поки він вийде з істинним та вірним. >> Да.
Рекурсивна функція це просто функція, яка називає себе.
Є три великих речей, які рекурсивна функція повинна бути.
По-перше, очевидно, це викликає сама себе.
Другий базовий варіант.
Так що в якийсь момент функція повинна припинити називати себе,
і це те, що базовий варіант призначений для.
Отже, ми знаємо, що ми повинні зупинитися, ми повинні відмовитися від нашої пошуку
при запуску дорівнює кінця - і ми підемо по тому, що це значить.
Але, нарешті, остання річ, яка важлива для рекурсивних функцій:
Функції повинні якось наблизитися до базовим сценарієм.
Подібно до цього, якщо ви насправді не всі оновлення, коли ви робити другий рекурсивний виклик,
якщо ви буквально тільки викликом функції знову з тими ж аргументами
і ніяких глобальних змінних були змінені або нічого,
ви ніколи не досягнете базовий варіант, в цьому випадку, що це погано.
Це буде нескінченна рекурсія і переповнення стека.
Але тут ми бачимо, що оновлення відбувається, оскільки ми оновлюємо початок кінця + / 2,
ми оновлюємо кінці аргументом тут, ми оновлюємо початку аргументом тут.
Отже, у всіх рекурсивних викликів ми оновлюємо щось. Добре.
Ви хочете йти з нами через ваше рішення? >> Звичайно.
Я використовую SearchHelp так, що кожен раз, коли я роблю виклик цієї функції
У мене є початок, де я шукаю в масиві і в кінці
, Де я шукаю масиву.
>> На кожному кроці, де він говорить, що це середній елемент, який є початком кінця + / 2,
, Що дорівнює тому, що ми шукаємо?
І якщо це так, то ми його знайшли, і я думаю, що передається до рівня рекурсії.
І якщо це не так, то ми перевіряємо, що середнє значення масиву занадто великий,
У цьому випадку ми дивимося на лівій половині масиву, йдучи від початку і до середини індексу.
А в іншому випадку ми робимо в кінці тайму.
[Боуден] Добре.
Звучить непогано.
Отже, пару речей, а насправді, це дуже високому рівні річ
що ви ніколи не повинні знати, для цього, звичайно, але це правда.
Рекурсивні функції, ви завжди чуєте, що вони погано справу
тому що якщо ви рекурсивно називати себе занадто багато разів, ви отримаєте переповнення стека
, Оскільки, як я вже говорив, кожна функція отримує власний фрейм стеку.
Таким чином, кожен виклик рекурсивної функції одержує власний фрейм стеку.
Так що якщо ви зробите 1000 рекурсивних викликів, ви отримуєте 1000 кадрів стека,
і швидко ви привести до того, занадто багато кадрів стека і речі просто зламати.
Так ось чому рекурсивні функції, як правило, погано.
Але є і хороші підмножина рекурсивних функцій називається хвостом рекурсивних функцій,
і це трапляється, наприклад, однієї, де, якщо компілятор помічає це
і він повинен, я думаю, - в Clang, якщо ви передаєте його прапор-O2
то помітите, що це хвіст рекурсивні та зробити все добре.
>> Він буде використовувати той же кадр стека знову і знову для кожного рекурсивного виклику.
І так як ви використовуєте той же кадр стека, вам не потрібно турбуватися про
ніколи стек переповнений, і в той же час, як ви казали,
, Де колись ви повернетеся так, то він повинен повернути всі ці кадри стека
і 10-й виклик SearchHelp повинен повернутися в 9-му, повинен повернутися в 8-м.
Так що не потрібно статися, коли функції хвіст рекурсивної.
І тому те, що робить ця функція є рекурсивною хвіст зверніть увагу, що для будь-якого виклику searchHelp
рекурсивний виклик, що він робить те, що він повертається.
Таким чином, у першому зверненні до SearchHelp, ми або негайно повернутися помилковим,
негайно повернути істинний, або ми робимо рекурсивний виклик SearchHelp
де те, що ми повертаємося какой то виклик повертається.
І ми не могли це зробити, якщо ми зробили щось подібне Int х = SearchHelp, повернення х * 2,
лише деякі випадкові зміни.
>> Так що тепер це рекурсивний виклик, це Int х = SearchHelp рекурсивного виклику,
більше не є хвостовою рекурсією, тому що насправді доведеться повернутися
повернутися до попереднього кадру стека, так що, що попередній виклик функції
може щось робити з повертаним значенням.
Так що це не хвіст рекурсивної, але те, що було раніше це красиво хвіст рекурсивної. Так.
[Студент] не повинні другому випадку база буде в першу чергу перевіряється
тому що не може бути ситуації, коли, коли ви передаєте його аргумент
Ви почати = кінець, але вони голка значення.
Це питання ми не можемо працювати в тому випадку, коли кінець голки значення
або почати = кінець, відповідно, початок = кінець
і ви насправді не перевірив, що особливе значення тим не менш,
Потім починайте + кінця / 2 просто буде мати те ж значення.
Але ми вже повернулися помилковим, і ми ніколи не перевіряли значення.
Так, принаймні, в перший виклик, якщо розмір дорівнює 0, то ми хочемо повернутися помилковим.
Але якщо розмір дорівнює 1, то запуск не буде рівних кінця,
і ми принаймні перевірити один елемент.
Але я думаю, ви маєте рацію в тому, що ми можемо в кінцевому підсумку у разі, коли почати кінця + / 2,
Початок закінчує тим, що так само, як початок кінця + / 2,
але ми ніколи насправді перевірити, що елемент.
>> Таким чином, якщо ми спочатку перевіряємо, є середнім значенням елемента ми шукаємо,
то ми можемо негайно повернути істинний.
Інакше, якщо вони рівні, то немає ніякого сенсу в продовженні
так як ми тільки збираємося оновити випадку, коли ми знаходимося на одного елемента масиву.
Якщо один елемент не той, якого ми шукаємо,
то все не так. Так.
[Студент] Справа в тому, що, оскільки розмір насправді більше, ніж число елементів у масиві,
вже є зсув - >> Так буде розмір -
[Студент] Скажімо, якщо масив був розміром 0, то SearchHelp буде насправді перевірити копиці сіна з 0
за першим покликом.
Масив має розмір 0, тому 0 є - >> Да.
Там Інша справа, що - це може бути хорошим. Давайте подумаємо.
Таким чином, якщо масив був 10 елементів, а середній ми збираємося перевірити, є індексом 5,
так ми перевіряємо 5, і давайте скажемо, що значення менше.
Таким чином, ми кидали всі, від 5 і далі.
Так що почніть з кінця + / 2 буде нашою новою мети
так що так, вона завжди залишиться за межами масиву.
Якщо мова йде про випадок, якщо воно було парних або непарних, то ми б перевірити, скажімо, 4,
але ми все ще викидають -
Так що так, кінець завжди буде за фактичний кінець масиву.
Таким чином, елементи, які ми зосередилися на, кінець завжди буде після цього.
І тому, якщо почати робить всі рівні Зрештою, ми знаходимося в масив розміром 0.
>> Інша річ, я думав, що ми оновлюємо починають почати + кінця / 2,
так що це той випадок, коли у мене виникають проблеми з, де починаються + кінця / 2
є елементом, ми перевіряємо.
Скажімо, у нас був цей 10-елементний масив. Неважливо.
Так що почніть з кінця + / 2 буде щось на зразок цього,
і якщо це не значення, що ми хочемо оновити.
Значення більше, тому ми хочемо подивитися на цю половину масиву.
Отже, як ми оновлюємо початку, ми оновлюємо початку тепер цей елемент.
Але це все ще може працювати, або, принаймні, ви можете зробити старт + кінця / 2 + 1.
[Студент] Вам не потрібно буде почати + кінця [нерозбірливо] >> Да.
Ми вже перевірили цей елемент і знаю, що це не той, який ми шукаємо.
Таким чином, нам не потрібно оновлювати починають цим елементом.
Ми можемо просто пропустити його і оновлювати починають бути цей елемент.
І є чи коли-небудь випадок, скажемо, що це був кінець,
так, то почала було б цього, почніть кінці + / 2 буде таким,
початок + кінець - Так, я думаю, що це може в кінцевому підсумку в нескінченну рекурсію.
Скажімо, це просто масив розміром 2 або масив розміром 1. Я думаю, що це буде працювати.
Таким чином, в даний час, є те, що початок і кінець елемента дорівнює 1 за його межами.
Таким чином, елемент, який ми збираємося перевірити це одне,
а потім, коли ми оновлюємо початку, ми оновлюємо починають 0 + 1/2,
який закінчиться нас з початку буття цього елемента.
>> Таким чином, ми перевіряємо і той же елемент знову і знову.
Так що це той випадок, коли кожен рекурсивний виклик повинен насправді щось оновлювати.
Так що нам потрібно зробити, початок + кінець / 2 + 1, або є випадок
, Де ми насправді не оновленням початку.
Все це бачили?
Добре.
Хто-небудь є питання по цьому рішенню або більше коментарів?
Добре. Хто-небудь є ітераційного рішення, що ми всі можемо дивитися?
Хіба ми все це робимо рекурсивно?
А також, я думаю, якщо ви відкрили її, то вам, можливо, доведеться перевизначити вашу попередню.
Чи означає це автоматично зберігати? Я не впевнений.
Хто-небудь є ітераційний?
Ми можемо пройти через це разом, якщо немає.
Ідея буде те ж саме.
Ітераційні рішення.
Ми збираємося хочуть в основному, роблять ту ж ідею
, Де ми хочемо бути в курсі нових кінці масиву і нові початку масиву
і робити це знову і знову.
І якщо те, що ми відстежують, як початок і кінець ніколи не перетинаються,
тоді ми не знайшли його і ми можемо повернутися помилковим.
Так як я можу це зробити? Будь є пропозиції або код для мене, щоб підтягти?
[Студент] Чи подобається час циклу. >> Да.
Ви збираєтеся хочете зробити петлю.
>> У вас є код, я міг би підтягнути, чи те, що ви збиралися запропонувати?
[Студент] Я так думаю. >> Все правильно. Це робить речі простіше. Яке було ваше ім'я?
[Студент] Лукас.
Перегляд 1. Добре.
Низька те, що ми називали розпочати раніше.
До це не зовсім те, що ми називали до кінця.
Насправді, в кінці Зараз всередині масиву. Це елемент, який ми повинні розглянути.
Таким чином, низьке значення 0, до це розмір масиву - 1,
і тепер ми циклів, і ми перевіряємо -
Я думаю, ви можете пройти через це.
Яке було ваше мислення через це? Йдіть з нами через код.
[Студент] Звичайно. Подивіться на стозі сіна значення в середніх і порівняти його з голки.
Так що, якщо це більше, ніж ваша голка, то ви хочете, щоб - ой, насправді, що повинно бути навпаки.
Ви збираєтеся хочете, щоб викинути правої половини, і так да, це повинен бути шлях.
[Боуден] Таким чином, це повинно бути менше? Це те, що ви сказали? >> [Студент] Так.
[Боуден] Добре. Поменше.
Так що якщо ми дивимося на це менше, ніж те, що ми хочемо,
то так, ми хочемо, щоб викинути ліву половину,
яка означає, що ми оновлюємо всі ми розглядаємо
шляхом переміщення низькою праворуч від масиву.
Це виглядає добре.
Я думаю, що це має те ж питання, що ми говорили на попередньому,
де, якщо низьке значення 0 і вище дорівнює 1, то низько + до / 2 буде налаштований на одне і те ж знову.
>> І навіть якщо це не так, то це ще більш ефективною, принаймні
просто викинути елемент, ми просто дивилися на яких ми знаємо не так.
Так низько + вгору / 2 + 1 - >> [студент] Це повинно бути по-іншому.
[Боуден] Або це має бути - 1, а інша повинна бути + 1.
[Студент] І не повинно бути подвійний знак рівності. >> [Боуден] Так.
[Студент] Так.
Добре.
І, нарешті, тепер, коли у нас є це + 1 - 1 штука,
це - вона не може бути - це взагалі можливо для низькою, щоб у підсумку значення більше, ніж нагорі?
Я думаю, що єдиний спосіб, який може статися - Хіба це можливо? >> [Студент] я не знаю.
Але якщо він отримує усічений, а потім отримує мінус, що 1, а потім - >> Да.
[Студент] Було б, можливо, отримати переплуталися.
Я думаю, що це має бути добре тільки тому, що
для того, щоб в кінцевому підсумку нижче вони повинні бути рівні, я думаю.
Але якщо вони рівні, то ми б не зробили той час як цикл з самого початку
і ми просто повернулися б значення. Так що я думаю, що ми добре зараз.
Зверніть увагу, що, хоча ця проблема більше не є рекурсивною,
такі ж ідеї застосовні, де ми можемо побачити, як це так легко піддається
на рекурсивне рішення тим, що ми просто оновлення індексів знову і знову,
ми робимо проблемою менше і менше, ми фокусуємося на підмножину масиву.
[Студент] Якщо низький дорівнює 0 і вище 1, вони як би 0 + 1/2, який піде на 0,
а то можна було б + 1, можна було б бути - 1.
[Студент] Куди ми перевірка рівності?
Подібно до цього, якщо середній насправді голку?
Ми в даний час не робить цього? О!
Якщо it's -
Так. Ми не можемо просто зробити тест тут, тому що скажімо першій середній -
[Студент] Це насправді хотів не викидайте кордону.
Таким чином, якщо Ви хочете позбутися пов'язаного, ви повинні перевірити його першим або будь-який інший.
Ah. Так. >> [Студент] Так.
Отже, ми викинули, яку ми в даний час дивилися,
яка означає, що ми тепер повинні також мати
якщо (копиці сіна [(низький + вгору) / 2] == голкою), то ми можемо повернутися вірно.
І чи можу я покласти ще або просто якщо це означає буквально те ж саме
тому що це повернувся б правдою.
Так що я поклав ще, якщо, але це не має значення.
>> Так ще, якщо це, ще це, і це є загальним, що я роблю
де, навіть якщо це випадок, коли все тут добре,
як низький ніколи не може бути більше, ніж вгору, не варто міркувань про те, що це правда.
Таким чином, ви можете також сказати, в той час як низьке, менше або дорівнює
або при низькому менше
так що якщо вони коли-небудь рівною або низької відбувається, щоб пройти мимо,
то ми можемо вирватися з цього циклу.
Питання, проблеми, коментарі?
Добре. Це виглядає добре.
Тепер ми хочемо зробити сортування.
Якщо ми підемо до мого другого перегляду, ми бачимо ті ж числа,
але тепер вони більше не в порядку сортування.
І ми хочемо реалізувати за допомогою будь-якого роду алгоритм O п § п.
Отже, який алгоритм ви думаєте, ми повинні реалізувати тут? >> [Студент] Злиття роду.
[Боуден] Так. Злиття сортування O (п § п), так це те, що ми збираємося робити.
І проблема буде досить схожі,
, Де він легко піддається рекурсивне рішення.
Ми також можемо придумати ітераційного рішення, якщо ми хочемо,
але рекурсія буде легше тут, і ми повинні зробити рекурсію.
Я думаю, ми будемо ходити через сортування злиттям перше,
хоча є прекрасні відео на сортування злиттям вже. [Сміх]
Так сортування злиттям є - я витрачати так багато роботи.
О, є тільки один зліва.
Таким чином, злиття.
О, 1, 3, 5.
Добре.
Злиття має два окремих масивів.
Індивідуально цих двох масивів і сортуються.
Таким чином, цей масив, 1, 3, 5, відсортовані. Цей масив, 0, 2, 4, відсортовані.
Тепер те, що злиття повинні зробити, це об'єднати їх в один масив, який сам відсортовані.
Тому ми хочемо масив розміром 6, який буде мати ці елементи всередині нього
в певному порядку.
>> І тому ми можемо скористатися тим, що ці два масиви сортуються
Для цього в лінійному часу,
лінійні сенс часу, якщо цей масив розміром х, і це розмір у,
то загальний алгоритм повинен бути O (х + у). Добре.
Таким чином, пропозиції.
[Студент] Чи можемо ми почати з лівої?
Таким чином, ви будете ставити 0 вниз, а потім 1, а потім тут ви на 2.
Так що це ніби як у вас є вкладка, яка рухається вправо. >> [Боуден] Так.
Для обох цих масивів, якщо ми зосередимося тільки на лівий елемент.
Оскільки обидва масиви сортуються, ми знаємо, що ці 2 елементи
найменші елементи в будь-якому масиві.
Таким чином, це означає, що 1 з цих 2 елементи повинні бути найменший елемент в нашому об'єднаному масиві.
Просто так вийшло, що є найменшим один на цей раз.
Таким чином, ми візьмемо 0, вставте його на лівій, тому що 0 менше 1,
так візьміть 0, вставте її в нашу першу позицію, а потім оновлювати цей
в даний час зосереджена на перший елемент.
А тепер повторіть.
Отже, тепер ми порівняємо 2 і 1. 1 менше, тому ми вставимо 1.
Ми оновлюємо цей покажчик, щоб вказати на цього хлопця.
Зараз ми робимо це знову, так що 2. Це дозволить оновити, порівняти ці 2, 3.
Цей поновлення, то 4 і 5.
Так що це злиття.
>> Це повинно бути досить очевидно, що це лінійний час, так як ми просто йдемо по кожному елементу раз.
І це великий крок до реалізації сортування злиттям це робить.
І це не так складно.
Пара речей, щоб турбуватися про те, скажімо, ми зливалися 1, 2, 3, 4, 5, 6.
У цьому випадку ми в кінцевому підсумку в сценарії, де ця буде менше,
Потім ми оновлюємо цей покажчик, на цей раз буде менше, оновлювати,
цьому це менше, і тепер ви повинні визнати,
коли ви реально працювати з елементів з чим порівнювати.
Так як ми вже використали весь цей масив,
всі в цьому масиві тепер просто вставляється в тут.
Тому, якщо ми коли-небудь працювати в точку, де один з наших масивів повністю об'єднані вже,
Потім ми просто візьмемо всі елементи інших масивів і вставити їх в кінець масиву.
Таким чином, ми можемо просто вставити 4, 5, 6. Добре.
Тобто одна річ, щоб не упустити.
Реалізація, яка повинна бути кроком 1.
Сортування злиттям потім на основі цього, це 2 кроки, 2 дурних кроків.
Давайте просто дати цього масиву.
Таким чином, сортування злиттям, крок 1, щоб рекурсивно розбити масив на дві половини.
Таким чином розділити цей масив на дві половини.
Тепер у нас є 4, 15, 16, 50 і 8, 23, 42, 108.
І тепер ми робимо це знову, і ми розділити ці дві половини.
Я просто зроблю це на цьому боці.
Таким чином, 4, 15 і 16, 50.
Ми хотіли б зробити те ж саме тут.
І тепер ми розділили його на дві половинки знову.
І у нас є 4, 15, 16, 50.
Так що це наш базовий сценарій.
Після масиви розміром 1, то ми зупиняємо з розщепленням на дві половини.
>> Тепер те, що ми будемо робити з цим?
Ми в кінцевому підсумку це також буде розпадатися на 8, 23, 42 і 108.
Так що тепер ми перебуваємо в цій точці, тепер крок два роду злиття просто злиття пари в списках.
Тому ми хочемо, щоб об'єднати ці. Ми просто подзвонити злиття.
Ми знаємо, що злиття буде повернути їх у певному порядку.
4, 15.
Тепер ми хочемо, щоб об'єднати ці, і видасть список з тими, в певному порядку,
16, 50.
Ми об'єднати ці - я не можу написати - 8, 23 і 42, 108.
Отже, ми маємо об'єднану пар відразу.
Тепер ми просто об'єднати знову.
Зверніть увагу, що кожен з цих списків, відсортованих у собі,
і тоді ми можемо просто об'єднати ці списки, щоб отримати список розмірі 4, який сортується
і злиття цих двох списків, щоб отримати список розміром 4, відсортований.
І, нарешті, ми можемо об'єднати ці два списки розмір 4, щоб отримати один список розмірі 8, який сортується.
Таким чином, щоб зрозуміти, що це загальна п § п, ми вже бачили, що злиття є лінійною,
тому, коли ми маємо справу з злиття цих, так як загальна вартість злиття
для цих двох списків знаходиться всього в 2, тому що -
Або добре, це O п, п, але от тільки ці 2 елементи, так що 2.
І ці 2 буде 2 і ці 2 буде 2, і ці 2 буде 2,
так через все зливається, що ми повинні зробити, ми в кінцевому підсумку робить н.
Як 2 + 2 + 2 + 2 складає 8, який є п,
так що вартість злиття в цій безлічі N.
І те ж саме і тут.
Ми об'єднати ці 2, то ці 2 і індивідуально цього злиття займе чотири операції,
це злиття займе чотири операції, але знову ж таки, між усім цим,
ми в кінцевому підсумку злиття п загальна речі, і тому цей крок займає н.
І так кожен рівень має п елементів у злитті.
>> А скільки рівнів є?
На кожному рівні нашого масиву збільшується на розмір 2.
Тут наші масиви мають розмір 1, тут вони розміром 2, тут вони розміром 4,
І, нарешті, вони розміром 8.
Таким чином, оскільки воно подвоюється, там буде в загальній складності § п з цих рівнів.
Так що з § п рівнів, кожен рівень з п загальна операцій,
ми отримуємо § п п алгоритм.
Питання?
У людей, які вже домоглися прогресу на те, як здійснити це?
Хто-небудь вже в стані, коли я можу просто підтягти свій код?
Я можу дати хвилину.
Це одне буде більше.
Я настійно рекомендую повторюються -
Ви не повинні зробити рекурсію для злиття
тому що зробити рекурсію для злиття, ви будете мати, щоб пройти купу різних розмірів.
Можна, але це дратує.
Але рекурсії для сортування саме по собі досить легко.
Ви просто дзвоните роду буквально на лівій половині, сортувати по праву половину. Добре.
Будь-який, є все, що я можу потягнути ще?
Або я дам одну хвилину.
Добре.
Будь-який, є щось, що ми можемо працювати з?
Або ми будемо просто працювати з цим, а потім розгорніть звідти.
>> Будь-який, є більше, ніж це, що я можу потягнути?
[Студент] Так. Ви можете підтягти мої. >> Все правильно.
Так!
[Студент] Існували багато умов. >> О, чорт. Чи можете ви -
[Студент] У мене є для його збереження. >> Да.
Таким чином, ми дійсно робили злиття окремо.
Так, але це не так уже й погано.
Добре.
Таким чином, рід сама просто дзвоню mergeSortHelp.
Поясніть нам, що mergeSortHelp робить.
[Студент] MergeSortHelp в значній мірі робить два основних етапи,
яка є для сортування кожну половину масиву, а потім об'єднати їх обох.
[Боуден] Гаразд, дайте мені секунду.
Я думаю, що це - >> [студент] мені потрібно -
Так. Я чогось не вистачає.
У злитті, я розумію, що мені потрібно, щоб створити новий масив
тому що я не міг зробити це на місці. >> Да. Ви не можете. Виправте.
[Студент] Так я створюю новий масив.
Я забув в кінці злиття з повторною зміниться.
Добре. Ми потребуємо в новому масиві.
В сортування злиттям, це майже завжди так.
Частина витрат на кращий алгоритм часом мудрий
Майже завжди необхідності використовувати трохи більше пам'яті.
Так ось, незалежно від того, як ви це робите сортування злиттям,
Вам неминуче доведеться використовувати додаткову пам'ять.
Він або вона створює новий масив.
І тоді ви говорите в кінці ми просто потрібно скопіювати новий масив у вихідному масиві.
[Студент] Я так думаю, так.
Я не знаю, якщо це працює з точки зору рахунку по посиланню або що завгодно, -
Так, він буде працювати. >> [Студент] Добре.
Чи знаєте ви спробувати запустити це? >> [Студент] Ні, ще ні. >> Добре.
Спробуйте запустити його, і тоді я буду говорити про це на секунду.
[Студент] Мені потрібно, щоб всі прототипи функцій і все, хоча, правда?
Прототипи функцій. О, ти маєш на увазі - так.
Сортувати кличе mergeSortHelp.
>> Таким чином, для того, щоб сортувати подзвонити mergeSortHelp, mergeSortHelp повинні або були визначені
Перед сортування або нам просто необхідно прототипу. Просто скопіюйте та вставте цього.
І точно так само, mergeSortHelp викликає злиття,
але злиття не був визначений, тому ми можемо просто дайте знати mergeSortHelp
що це те, що злиття буде виглядати, ось і все.
Так mergeSortHelp.
У нас є проблема тут, де ми не маємо базовий варіант.
MergeSortHelp рекурсивно, так що будь рекурсивної функції
буде потрібно якусь підставу справа знати, коли зупинитися рекурсивно, що називає себе.
Те, що наша база випадку буде тут? Так.
[Студент] Якщо розмір 1? >> [Боуден] Так.
Так що, як ми бачили, саме там, ми зупинилися розщеплення масивів
як тільки ми отримали в масиви розміром 1, яка неминуче сортуються себе.
Таким чином, якщо розмір дорівнює 1, ми знаємо, що масив вже відсортований,
тому ми можемо просто повернутися.
>> Зверніть увагу, що це порожнеча, так що ми нічого не повертають Зокрема, ми просто повертаємо.
Добре. Так що це наш базовий сценарій.
Я думаю, наш базовий сценарій також може бути, якщо ми, трапляється, злиття масив розміром 0,
ми, ймовірно, хочете, щоб зупинити в якийсь момент,
так що ми можемо тільки сказати, розміром менше 2 або менше або дорівнює 1
так що це буде працювати для будь-якого масиву зараз.
Добре.
Так що це наш базовий сценарій.
Тепер ви хочете йти з нами через злиття?
Що означають всі ці випадки на увазі?
Тут, нагорі, ми просто робимо ту ж ідею, -
[Студент] Мені потрібно проходив розміру з усіма викликами mergeSortHelp.
Я додав розмірі якості додаткового початкового і його там немає, як і розмір / 2.
[Боуден] О, розмір / 2, розмір / 2. >> [Студент] Так, а також у наведеній вище функції, а також.
[Боуден] Тут? >> [Студент] Так же розміру. >> [Боуден] Ох. Розмір, розмір? >> [Студент] Так.
[Боуден] Добре.
Дозвольте мені думати ні на секунду.
Хіба ми зіткнулися з проблемою?
Ми завжди лікуванні лівому як 0. >> [Студент] Немає
Це неправильно теж. Вибачте. Це має бути початок. Так.
[Боуден] Добре. Мені подобається, що краще.
І кінця. Добре.
Так що тепер ви хочете йти з нами через злиття? >> [Студент] Добре.
Я просто йшов по цій новій масив, який я створив.
Її розмір є розміром частині масиву, який ми хочемо бути відсортовані
і намагається знайти елемент, який я повинен покласти в новий етап масиву.
Таким чином, щоб зробити це, спочатку я перевіряю, якщо в лівій половині масиву продовжує мати більше елементів,
і якщо це не так, то ви спускаєтеся до цього ще умова, яка просто говорить
Добре, вона повинна бути в правильному масиві, і ми покладемо, що в поточному індексі newArray.
>> А потім в іншому випадку, я перевіряю, якщо права частина масиву також закінчив,
У цьому випадку я просто поклав у лівий.
Це може і не бути необхідним. Я не впевнений.
Але в будь-якому випадку, дві інші перевірки, який з двох менших в ліву чи праву.
А також в кожному конкретному випадку, я збільшуючи залежності від того, заповнювач Я збільшуватися.
[Боуден] Добре.
Це виглядає добре.
Хто-небудь є зауваження або питання чи проблеми?
Таким чином, чотири випадки, що ми повинні принести речі в просто бути - чи це виглядає як п'ять -
але ми повинні розглянути питання про лівому масиві закінчилися, що нам потрібно об'єднатися,
Чи має право масиві закінчилися речі, які ми повинні об'єднати -
Я вказуючи на нічого.
Так чи лівий масив закінчилися речі або права масиві закінчилися речі.
Ці два випадки.
Ми також потребуємо тривіальному випадку, від того, що залишилося менше, ніж правильні речі.
Тоді ми хочемо вибрати ліву річ.
Ті випадки.
Так що це було правильно, так от що.
Масив залишилося. Це 1, 2, 3. Добре. Так що так, це ті чотири речі, які ми могли б зробити.
І ми не будемо переходити рішення ітераційним.
Я б не рекомендував -
Злиття роду є прикладом функції, яка є одночасно не хвіст рекурсивної,
це не так просто зробити його хвостовій рекурсією,
але і це не дуже легко зробити ітеративним.
Це дуже легко.
Ця реалізація сортування злиттям,
зливатися, що б ви не робили, ви збираєтеся побудувати злиття.
>> Таким чином, сортування злиттям побудований на злитті рекурсивно саме ці три лінії.
Итеративно, більш дратівливими і більш важко думати.
Але зверніть увагу, що це не хвіст рекурсивної, так як mergeSortHelp - коли він називає себе -
його ще потрібно робити речі, після цього повертається рекурсивних викликів.
Так що цей кадр стека повинна продовжувати існувати навіть після виклику цього.
А потім, коли ви називаєте це, стек повинен продовжувати існувати
тому що навіть після цього виклику, ми все ще повинні зливатися.
І це нетривіальна, щоб зробити цей хвіст рекурсивної.
Питання?
Добре.
Таким чином, повертаючись до сортування - ой, є дві речі, які я хочу показати. Добре.
Повертаючись до сортування, ми зробимо це швидко.
Або шукати. Сортування? Сортування. Так.
Повертаючись до витоків роду.
Ми хочемо створити алгоритм, який сортує масив з використанням будь-якого алгоритму
У O п.
Так, як це можливо? Хто-небудь є які-небудь роду -
Я натякнув, перш ніж на -
Якщо ми збираємося поліпшити з п § п к о п,
Ми поліпшили наш алгоритм часом мудрою,
це означає, що ми збираємося потрібно зробити, щоб надолужити це?
[Студент] простору. >> Да. Ми збираємося використовувати більше простору.
І навіть не просто більше місця, це експоненціально більше простору.
Так що я думаю, що цей тип алгоритму є те, псевдо, псевдо полінома -
псевдо - Я не можу пригадати. Псевдо щось.
Але це тому, що ми повинні використовувати так багато місця
що це досяжно, але не реалістично.
>> І як ми можемо цього досягти?
Ми можемо добитися цього, якщо ми гарантуємо, що будь-який конкретний елемент масиву
нижче певного розміру.
Так що давайте просто скажемо, що розміри 200,
будь-який елемент в масиві нижче розміру 200.
І це насправді дуже реалістично.
Ви можете дуже легко мати масив, що ви знаєте все, що в його
буде менше, ніж деяке число.
Подібно до цього, якщо у вас є абсолютно масивного векторного або щось
але ви знаєте, все, що буде між 0 і 5,
то це буде значно швидше це зробити.
І пов'язаний ні по одному з елементів 5,
так що ця оцінка, тобто, скільки пам'яті ви збираєтеся використовувати.
Таким чином, межа 200.
У теорії завжди є пов'язане, так як ціле може бути тільки до 4 млрд.
але це нереально, так як тоді ми будемо з використанням космічних
близько 4 млрд. доларів. Так що це нереально.
Але тут ми будемо говорити наша оцінка є 200.
Весь фокус у тому, щоб робити це в O п Тобто ми робимо ще один масив називається підрахунок розміру кордон.
Таким чином, насправді, це ярлик для - Я насправді не знаю, якщо Clang це робить.
Але в GCC, принаймні - я припускаючи, Clang робить це занадто -
це буде просто ініціалізувати весь масив буде 0s.
Так що, якщо я не хочу цього робити, то я міг би зробити окремо для (INT = 0;
я <BOUND, я + +) і розраховує [я] = 0;
Так що тепер все встановлюється на 0.
Я перебору мій масив,
і те, що я роблю, я розраховую числа кожного - давай сюди.
У нас є 4, 15, 16, 50, 8, 23, 42, 108.
Що я розраховую число входжень кожного з цих елементів.
Давайте насправді додати ще пару сюди з деякими повторюється.
Таким чином, значення ми маємо тут, значення, яке буде масив [I].
Таким чином, вал може бути 4 або 8 або будь-який інший.
І тепер я розраховую, скільки з цього значення, я бачив,
так вважає [значення] + +;
Після цього не буде зроблено, розраховує буде виглядати як 0001.
Давайте зробимо підрахунок [значення] - ДОТРИМУВАТИСЬ + 1.
>> Тепер це просто пояснити той факт, що ми, починаючи з 0.
Таким чином, якщо 200 буде наш найбільший номер,
Потім від 0 до 200 складає 201 речей.
Таким чином, вважається, це буде виглядати як 00001, тому що у нас є один 4.
Тоді ми будемо мати 0001, де ми будемо мати 1 у 8-му індекс кол.
Ми будемо мати 2 в 23-й показник кол.
Ми будемо мати 2 в індексі 42-й рахунок.
Таким чином, ми можемо використовувати рахунки.
Так num_of_item = імпульси [I].
І тому, якщо num_of_item дорівнює 2, це означає, що ми хочемо вставити 2 числа я
в нашому масиві.
Так що ми повинні відслідковувати, як далеко ми в масив.
Таким чином, індекс = 0.
Array - Я просто написати її.
Графи -
масив [індекс + +] = я;
Це те, що я хочу? Я думаю, що те, що я хочу.
Так, це добре виглядає. Добре.
Так само всі розуміють, що мета мого масиву вважається таке?
Це підрахунок числа входжень кожного з цих чисел.
Тоді я ітерація, що має значення масиву,
і ї позиції в масиві розраховує
це число я ось що має з'явитися в моєму масиві.
Ось чому пунктами 4, буде на 1
і налічує від 8 буде 1, пунктами 23, буде 2.
Так от, скільки з них я хочу вставити в мій масиві.
Тоді я просто це зробити.
Я вставка num_of_item я от в моєму масиві.
>> Питання?
І знову ж таки, це лінійний час, так як ми просто ітерації в цей раз,
але це також лінійні в тому, що це число виявиться,
і так в чому залежить від того, що ваша границя.
З пов'язане 200, що не так уже й погано.
Якщо межа буде 10000, то це трохи гірше,
але якщо ваша пов'язаних буде 4 млрд., що це абсолютно нереально
і цей масив буде мати, щоб бути розміром 4 мільярди доларів, що нереально.
Так ось що. Питання?
[Нерозбірливо відповідь студента] >> Гаразд.
Я зрозумів одну річ, коли ми переживаємо.
Я думаю, що проблема була в Лукаса і, напевно, кожен з нас бачив.
Я зовсім забув.
Єдине, що я хотів би прокоментувати, що, коли ви маєте справу з речами, як індекси,
Ви ніколи не бачать цього, коли ви пишете цикл,
але технічно, всякий раз, коли ви маєте справу з цими показниками,
Ви повинні майже завжди справу з цілими числами без знака.
Причина цього в тому, коли ви маєте справу з цілими числами,
так що якщо у вас є 2 цілих чисел, і ви складете їх разом
і вони в кінцевому підсумку занадто великий, то ви в кінцевому підсумку з негативним числом.
Так ось що ціле переповнення.
>> Якщо додати 2 млрд і 1 млрд, я в кінцевому підсумку з негативними 1 мільярд доларів.
Ось як цілі працювати на комп'ютерах.
Таким чином, проблема з використанням -
Це нормально, за винятком, якщо низько, трапляється, 2 млрд і вище, трапляється, 1 млрд,
то це буде негативний 1 млрд. і потім ми збираємося розділити це на 2
і в кінцевому підсумку з негативною 500 мільйонів доларів.
Так що це тільки питання, якщо вам трапиться бути пошук в масиві
мільярди речей.
Але якщо низько + до відбувається переповнювання, то це проблема.
Як тільки ми їх без знака, потім 2 млрд. плюс 1 млрд. 3 млрд. доларів.
3000000000 розділити на 2 становить 1,5 мільярда доларів.
Тому, як тільки вони підписаний, все ідеально.
І це теж проблема, коли ви пишете ваші цикли,
а насправді, це, ймовірно, робить це автоматично.
Це насправді просто кричати на вас.
Так що, якщо це число занадто великим, щоб бути всього лише ціле число, але це буде вписуватися в ціле число без знака,
вона буде кричати на вас, ось чому ви ніколи не зіштовхнетеся з проблемою.
Ви можете бачити, що індекс ніколи не буде негативним,
і тому, коли ви ітерації по масиву,
Ви можете майже завжди говорять непідписаних Int я, але ви дійсно не потрібно.
Справи йдуть працювати в значній мірі так само добре.
Добре. [Пошепки] Скільки зараз часу?
Останнє, що я хотів показати, - і я буду просто робити це дуже швидко.
Ви знаєте, як ми # визначити таким чином ми можемо визначити # MAX, як 5 або ще що-небудь?
Давайте не будемо робити MAX. # Визначити пов'язаний як 200. Це те, що ми робили раніше.
Це визначає постійне, яка тільки збирається бути скопійований і вставлений
де б ми не трапилося, щоб написати пов'язані.
>> Так що ми дійсно можемо зробити більше з # визначає.
Ми можемо визначити функції #.
Вони насправді не функції, але ми будемо називати їх функцій.
Прикладом може бути щось на зразок MAX (х, у) визначається як (х <у у: х). Добре.
Таким чином, ви повинні звикнути до потрійної синтаксис оператора,
але х менше, ніж у? Повернутися в, ще повернуться х.
Таким чином, ви можете бачити ви можете зробити це окремою функцією,
і функція може бути як BOOL MAX займає 2 аргументів, повернути це.
Це один з найбільш поширених з них я бачу, як це зробити. Ми називаємо їх макросів.
Це макрос.
Це тільки синтаксис для цього.
Ви можете написати макрос, щоб зробити все, що ви хочете.
Ви часто бачите макроси для налагодження printfs та інше.
Таким чином, тип Printf, існують спеціальні константи в C, як підкреслюють ЛІНІЯ підкреслення,
2 підкреслює ЛІНІЯ підкреслення,
і є також я думаю, що 2 підкреслення FUNC. Це могло б бути. Щось на зразок цього.
Ці речі будуть замінені на ім'я функції
або номер рядка, що ви перебуваєте.
Часто, ви пишете налагодження printfs, що тут я міг би просто написати
Налагодження і він буде друкувати номер рядка та функції, які я опинитися в
що вона зустрічається, що DEBUG заяві.
І ви також можете роздрукувати інших речей.
Таким чином, єдине, що ви повинні стежити за то, якщо я, трапляється, # визначити DOUBLE_MAX
як щось подібне до 2 * у і 2 * х.
Так з якої причини, ви, виявляється, зробити це багато.
Так що зробіть це макрос.
Це дійсно зламаний.
Я б назвав це, роблячи щось на зразок DOUBLE_MAX (3, 6).
Отже, що має бути повернуто?
[Студент] 12.
Так, 12 повинні бути повернуті, і 12 повертається.
3 замінюється на х, 6 замінюється на в, і ми повертаємося 2 * 6, що на 12.
А що з цього приводу? Що має бути повернуто?
[Студент] 14. >> В ідеалі, 14.
Справа в тому, що, як хеш визначає роботу, пам'ятайте, що це буквальне копіювання і вставка
в значній мірі все, так що це буде інтерпретуватися як
в 3 менше, ніж 1 плюс 6, 2 рази 1 плюс 6, 2 рази 3.
>> Таким чином, з цієї причини ви майже завжди обернути все в круглих дужках.
Будь-яка змінна, ви майже завжди обернути в дужки.
Є випадки, коли вам не доведеться, як я знаю, що мені не потрібно, щоб зробити це тут
тому, що менше, ніж в значній мірі завжди просто ходити на роботу,
Незважаючи на те, що може навіть не бути правдою.
Якщо є щось смішне, як DOUBLE_MAX (1 == 2),
те, що відбувається, щоб замінити 3 менше, ніж 1 дорівнює дорівнює 2,
і так, то це буде зробити 3 менше 1, чи означає це, що дорівнює 2,
які не те, що ми хочемо.
Таким чином, з метою запобігання будь-якого оператора пріоритет проблеми,
завжди обернути в дужки.
Добре. І ось воно, 5:30.
Якщо у вас є питання по PSET, дайте нам знати.
Це має бути весело, і хакером видання також є набагато більш реалістичним
ніж хакером видання минулого року, так що ми сподіваємося, що багато хто з вас спробувати.
У минулому році було дуже переважною.
>> [CS50.TV]