>> [За възпроизвеждане на музика]
DAVID Malan: Добре.
Добре, добре дошъл отново.
Така че това е седмица 4, началото от него, вече.
И вие си спомняте, че миналата седмица, ще се постави код отмени само малко
и започнахме да говорим малко по- на високо равнище, за такива неща
търсене и сортиране, които макар и малко прости идеи, са
представител на даден клас проблеми вие ще започнете да се реши по-специално
като започнем да мислим за финал проекти и интересни решения ви
Може би трябва да проблемите на реалния свят.
Сега балон вид е един от най-простите такива алгоритми, и то
работил като от тези малки числа в списък или в масив вид
балон пътя си до върха, и големите цифри премести своя път надолу, за да
В края на този списък.
>> И припомни, че бихме могли да се визуализира балон подреди малко
нещо като това.
Така че нека да вървим напред и щракнете върху Старт.
Аз бях избрана предварително балон подреди.
И ако си спомняте, че по-високият синьо Линиите представляват големите цифри, малки
Сините линии представляват малки номера, като ние преминаваме през това отново и отново, и
отново, като се сравняват два бара до всеки други в червено, отиваме да сменяте
най-голямата и най-малката, ако те са в ред.
>> Така че това ще продължи и продължи и да се на, и ще видите, че по-голямата
елементи са си проправяха път към право, и по-малките елементи са
вземане на пътя си наляво.
Но ние започнахме да се определи количествено на ефективност,
Качеството на този алгоритъм.
И ние казахме, че в най-лошия случай, този алгоритъм се
приблизително колко стъпки?
>> Така п квадрат.
И това, което е п?
>> Публика: Брой елементи.
>> DAVID Malan: Значи п е броя на елементите.
И така, ние ще направим това често.
Всеки път, когато искам да говоря за размера на даден проблем или размера на
вход, или размера на времето, необходимо да произвеждат продукция, ние просто ще
генерализирана каквото на входа е като п.
Така че обратно в Седмица 0, броя страници в телефонния указател е п.
Броят на учениците в стаята беше п.
Така че и тук, ние сме след този модел.
>> Сега п квадрат не е особено бързо, така че ние се опитахме да направим по-добре.
И така, разгледахме няколко други алгоритми, сред които
бяха селекция вид.
Така че избора е вид малко по-различна.
Беше почти опростена, смея да кажа, при което I започва в началото на
списък на нашите доброволци и аз просто отново и отново, и отново премина през
списъка, скубане от най-малките елемент в даден момент и пускането му или
я в началото на списъка.
>> Но това също, след като започнах да мисля чрез математиката и по-голяма
картина, помисли си колко пъти Щях назад и напред и назад
и напред, ние се казва в най-лошия случай, избор подреди също беше какво?
N на квадрат.
Сега в реалния свят, може да действително да бъде малко по-бързо.
Защото отново, аз не трябва да се запази връщане назад, след като бях подредени на
най-малките елементи.
Но ако се замислим много голяма п и ако нещо се направи по математика като
Направих на дъската, с N на квадрат минус нещо, всичко останало
Освен N квадрат, след п стане наистина голям, не
значение толкова много.
Така че като компютърни специалисти, ние някак си затварят очите за по-малките
фактори и се съсредоточи само върху фактор в израз, който ще ви накара
най-голямата разлика.
>> Е, накрая, погледнахме при поставяне подреди.
И това е сходна по дух, но вместо да мине през итеративно и
изберете най-малкия елемент един по един път I вместо пое ръката, че
успя да се справи, и аз реших, всички Добре, ти е мястото тук.
След това се преместих към следващия елемент и реши, че той или
тя принадлежи тук.
И след това се преместих на и на.
И аз може да, по протежение на пътя, смени тези момчета, за да се
направи място за тях.
Така че това е нещо като психическо възстановяване избор на вида, който ние
нарича вмъкване вид.
>> Така че, тези теми да се появят в реалния свят.
Само преди няколко години, когато определен Сенаторът се кандидатира за президент,
Eric Schmidt, по времето, когато изпълнителен директор на Google, имал действително възможност
да го интервюират.
И ние смятахме, че ще споделя това YouTube клип за теб, ако можем да се появи
силата на звука.
>> [VIDEO PLAYBACK]
>> -Сега, Senator, ти си тук в Google, и аз предпочитам да мисля за президентския пост
като интервю за работа.
>> [СМЯХ]
>> -Сега е трудно да се получи работа като президент.
И, което става чрез тръпки предприятието.
То също е трудно да се намери работа в Google.
Ние имаме въпроси и искаме нашите кандидати въпроси.
И това е една от Larry Швимер.
>> [СМЯХ]
-Мислите, че се шегувам?
Това е точно тук.
Какво е най-ефективният начин да се сортирате един милион две-битови цели числа?
>> [СМЯХ]
>> -Ами, ъ-ъ -
>> -Съжалявам.
Може би трябва -
>> -Не, не, не, не, не.
>> -Това не е -
OK.
>> -Мисля, че балонът ще подреди бъде по грешен начин да отида.
>> [СМЯХ]
>> [Аплодисменти и аплодисменти]
>> -Хайде, кой му е казал?
OK.
>> [END възпроизвеждане на видео]
>> DAVID Malan: Така че има ли го.
Така че ние започнахме да се определи количествено тези текущи пъти, така да се каже, с нещо
нарича асимптотичната нотация, която е просто се позовава на нашия вид на завъртане
си затварят очите за тези по-малки фактори и само гледа на времето за работа,
изпълнението на тези алгоритми, като н стане наистина голяма с течение на времето.
И така, ние въведохме голям O. И голяма O представлява нещо, което си мислехме
на като горна граница.
И всъщност, Бари, може ли да намали от микрофона за малко?
>> Ние решихме, че това е горна граница.
Така че голяма O от квадратите на средства п, че в най-лошия случай, нещо като
подреди подбор ще се п квадрат стъпки.
Или нещо подобно вмъкване сортиране би н идеален стъпки.
Сега за нещо като вмъкване вид, това, което беше най-лошия случай?
Като се има предвид масив, това, което е най-лошото възможно сценарий, който може да откриете
се сблъскват с?
>> Това е напълно назад, нали?
Защото, ако е напълно назад, което трябва да направите един куп работа.
Защото, ако ти си напълно назад, вие ще намерите
най-големият елемент тук, въпреки че принадлежи там.
Така че ти започваш да се каже, добре, най- настоящия момент, ти е мястото тук,
така ли да го оставят на мира.
>> Тогава осъзнаваш, о, по дяволите, трябва да преместите тази малко по-малък елемент, който да
вляво от вас.
Тогава аз трябва да го направя отново и отново и отново.
И ако аз тръгна напред и назад, вие би някак да се чувстват изпълнението на
че алгоритъм, защото постоянно съм размесването на всички останали надолу в
масив за да направи място за него.
Така че това е най-лошия случай.
>> От друга страна -
и това е Катерачът последен път -
казахме, че поставянето сортиране е омегата на какво?
Какъв е най-добрия случай работа поставянето им вид?
Така че това е всъщност п.
Това беше празен, че си тръгнахме на борда последен път.
>> И това е омега на N, защото защо?
Е, в най-добрия случай, това, което е вмъкване вид ще бъде предаден?
Е, списък, който е напълно сортирани вече, минимална работа за вършене.
Но това, което е чист за вмъкване сортиране е, че тъй като започва тук
реши, о, ти си номер едно, ти е мястото тук.
О, какъв късмет.
>> Ти си номер две.
Можете също е тук.
Номер три, още по-добре, ти е мястото тук.
Веднага след като стигне до края на списък, за вмъкване вид на pseudocode
че вървяхме устно Последният път, това е направено.
Но избора сортиране, от друга страна, съхраняват какво?
>> Продължих през списъка отново и отново и отново.
Тъй като ключовата поглед има само след като погледна по целия път до
края на списъка може да бъде определен че елементът, който сте избрали е
В действителност в момента малкият елемент.
Така че тези различни умствени края модели до което се получават някои много реалния свят
разлики за нас, както и тези теоретични асимптотичната различия.
>> Така че просто да обобщим, след това, голяма O на п квадрат, видяхме няколко такива
алгоритми, до този момент.
Big O на п?
Какво е алгоритъм, който може да се казва, че е голяма О п?
В най-лошия случай, е необходимо линейна редица стъпки.
>> OK, линейно търсене.
И в най-лошия случай, когато е елемент, което търсите, когато
прилагане на линейно търсене?
>> OK, в най-лошия случай, дори не е там.
Или на втория най-лошия случай, че е чак в края, което е
плюс или минус една стъпка разлика.
Така в края на деня, можем да кажем, че е линейна.
Big O на N ще бъде линейна търсене, тъй като в най-лошия случай,
елемент дори не е там или че е чак в края.
>> Е, голяма O на дневника на п.
Не говорихме много подробно за това, но сме виждали и преди.
Това, което работи в така наречената логаритмична време, в най-лошия случай?
>> Да, така двоично търсене.
И двоично търсене в най-лошия случай може да има елемент някъде в
средата, или някъде във вътрешността на масива.
Но само да го намерите, след като разделят списък на половина, в
половина на половина, на половина.
И тогава готово, че е там.
Или пък най-лошия случай, дори не е там.
Но ти не знаеш, че не е там докато вид достигне до това последно
отдолу повечето елементи от намаляване наполовина и намаляване наполовина и намаляване наполовина.
>> Big O от 1.
Така че бихме могли голям от 2 O, O голяма от 3.
Всеки път, когато искате просто постоянно число, ние просто някак от само опростяване
, че по-голям от 1 Н.
Въпреки че, ако реалистично, е необходимо 2 или дори 100 стъпки, ако това е
постоянен брой стъпки, ние само да кажа голямо O от 1.
Какво е алгоритъм, който е в голяма О от 1?
>> Публика: Намирането на дължина на променлива.
>> DAVID Malan: Намирането на дължина на променлива?
>> Публика: Не, дължината ако той вече е сортиран.
>> DAVID Malan: Добре.
ОК, така че намирането на дължината на нещо Ако дължината на, че нещо, като
масив, се съхранява в някои променлива.
Защото може просто да прочетете променлива, или отпечатване на променлива, или
Просто обикновено достъп до тази променлива.
И готово, че отнема константно време.
>> От друга страна, мисля, обратно към нулата.
Спомни си за първата седмица на C, призовава просто ФОРМАТ и печат
нещо на екрана, е може би константно време, защото това просто отнема
някои броя на процесорните цикли, за да покаже че текста на екрана.
Или чакаме - нали?
Как иначе може да се моделира изпълнение на ФОРМАТ?
Някой би ли искал да не се съглася, че може би това не е наистина константно време?
В какъв смисъл може ФОРМАТ бяга време, да я отпечатате в низ от
на екрана, е нещо различни от постоянна.
>> Публиката: [недоловим].
>> DAVID Malan: Да.
Така че зависи от наша гледна точка.
Ако ние всъщност мислим за приноса към ФОРМАТ като низ, и
Затова ние измерваме размера на това въвеждане на данни от своята дължина - така да го наречем
тази дължина N, както и -
може би, ФОРМАТ себе си е голяма O на п защото тя ще ви отведе п стъпки
да отпечатате всяка от тези п герои, най-вероятно.
Най-малко до степен, че да поеме че може би това е използване за линия
под предния капак.
>> Но ние ще трябва да погледнете, че код, за да разберат по-добре.
И наистина, след като вие започнете анализира вашите собствени алгоритми, ще
буквално направи точно това.
Сортиране на очната ябълка кода си и мисля, за - Добре, аз имам този цикъл
тук или имам вложени цикъла тук, че ще направи н неща п пъти,
и можете да сортирате на разума си път чрез кода, дори ако това е
pseudocode а не действителният код.
>> Така че какво да кажем за омегата на п квадрат?
Какво е алгоритъм, който по най-добрия случай, все още се п квадрат стъпки?
Да?
>> Публиката: [недоловим].
>> DAVID Malan: Така че избор подреди.
Поради това, че проблемът наистина намалява на факта, че отново, аз не знам
Аз открих текущата най-малката до Аз направих всички дяволски елементи.
Така че омега на, да речем, п, ние Просто дойде с една.
Insertion вид.
Ако списъкът се случва да се сортират вече, в най-добрия случай ние просто трябва
да се направи една атака през него, в който момент сме сигурни.
И след това, че може да се каже да бъде линейна, със сигурност.
>> Ами омегата на един?
Какво, в най-добрия случай може да отнеме постоянен брой стъпки?
Така линейно търсене, ако просто се късметлия и елемента, което търсите
е точно в началото на списъка, ако това е, когато сте се започне вашата
линейна прекосявам на този списък.
>> И това е вярно на редица неща.
Например, дори двоичен търсене е омега на 1.
Защото какво, ако получите наистина дяволски късмет и да пляскам-DAB в средата на
си масив е броят , което търсите?
Така че можете да получите късмет там, както добре.
>> Това, на последно място, омега на п дневник п.
Така п дневник N, всъщност не говори за още, но -
>> Публика: Обединяване вид?
>> DAVID Malan: Merge вид.
Това беше Катерачът от последния път, когато ние предложихме, и ние показахме,
визуално, че има алгоритми.
И се сливат вид само един такъв алгоритъм, който е фундаментално по-бързо
, отколкото някои от другите момчета.
В действителност, слива кратко е не само в най-добрия случай н н лог, в най-лошия
Дело N N лог.
И когато имате това съвпадение на омега и големи O е едно и също нещо?
Ние всъщност може да опише, че това, което е нарича тета, въпреки че това е
малко по-рядко.
Но това означава само на два скока, В този случай, са едни и същи.
>> Така се слеят вид, това, което прави това наистина се свеждат до за нас?
Е, припомни мотивация.
Позволете ми да спра друга анимация, която ние не погледна за последен път.
Това, същата идея, но това е малко по-голям.
И аз ще отида напред и да се отбележи, първо - имаме вмъкване вид на
горния ляв ъгъл, след това избор на вид, балон вид, няколко други видове -
черупката и бързо - че не сме говорили за, и куп и се сливат вид.
>> Така поне се опита да се съсредоточи очите си челната тройка в ляво и след това
сливат подреди когато щракнете тази зелена стрелка.
Но ще ти дам всички от тях тече, само за да ще ви даде усещане за разнообразието на
алгоритми, които съществуват в света.
Аз няма да позволя този план само за няколко секунди.
И ако се съсредоточи очите си - изберете по- алгоритъм, се фокусира върху него само за
секунда - ще започнем да виждаме модел, че това е изпълнение.
>> Обединяване вид, забележка, е направено.
Heap вид, бързо сортиране, черупки -
така че изглежда, ние въведохме три лошите алгоритми миналата седмица.
Но това е добре, че сме тук днес, за да Посетете вид сливане, което е една от
по-лесно тези, е да погледнете, дори въпреки че вероятно ще огъне ума си
само малко.
Тук можем да видим точно колко избор подреди гадно.
>> Но от друга страна, това е много лесно за изпълнение.
И може би за Set P 3, това е един от най- алгоритми, които сте избрали да прилагат
за стандартното издание.
Съвършено глоба, съвсем верен.
>> Но отново, като п получава голям, ако да изберат да изпълняват по-бърз алгоритъм
като се слеят вид, шансовете са по-големи и по-големи входове, кода си е просто
ще работи по-бързо.
Вашият сайт ще работи по-добре.
Вашите потребители ще бъде по-щастлив.
И така, там са тези ефекти на всъщност дава
ни малко по-дълбоко и мислех.
>> Така че нека да погледнем какво се слеят Сортът е всъщност всичко.
В готино нещо е, че се слеят Сортът е точно това.
Това е, отново, това, което сме нарича pseudocode, pseudocode същество
English-подобен синтаксис.
И простотата е нещо очарователно.
>> Така че на входа на наш елементи - така че просто означава, ето един масив.
Той има п неща в него.
Това е всичко, което казваме там.
>> Ако п е по-малко от 2, се върне.
Така че това е просто тривиално случай.
Ако п е по-малко от 2, а след това очевидно е 1 или 0, като в този случай нещо
вече подредени или несъществуващи, Така че просто се върнете.
Няма какво да направя.
Така че това е обикновен случай да скубя.
>> Иначе, имаме три стъпки.
Пъзел с лявата половина на елементите, сортиране дясната половина на елементите,
и след сливане на сортирани половини.
Интересното тук е, че Аз съм един вид на плоскодънни лодки, нали?
Има вид на кръгов определение за този алгоритъм.
В какъв смисъл е този алгоритъм е определение кръгла?
>> Публиката: [недоловим].
>> DAVID Malan: Да, моя алгоритъм за сортиране, двама от неговите стъпки са "вид
нещо. "И така, това повдига въпрос, добре, аз какво ще използвате
да се справи със лявата половина и дясната половина?
А най-хубавото тук е, че въпреки че Отново, това е оказващ влияние
част потенциално, можете да използвате същия алгоритъм, за да се справи със лявата половина.
>> Но почакайте.
Когато ти се казва да се справи със лявата половина, какви са два
стъпки ще е следващия?
Ще се справи със лявата половина на лявата половина и правото
половина на лявата половина.
По дяволите, как мога да сортирате тези две половинки или четвъртинки, сега?
>> Но това е ОК.
Ние имаме алгоритъм за сортиране тук.
И въпреки, че може да се тревожи в първо това е нещо безкрайно
линия, това е цикъл, който никога не е ще свърши - това ще
приключва, след това, което се случва?
След като п е по-малко от 2.
Което в крайна сметка ще се случи, защото ако продължаваш да се намали наполовина и
намаляване наполовина в намаляване наполовина тези половинки, със сигурност в крайна сметка, което ще свърши
нагоре само с 1 или 0 елементи.
В този момент, този алгоритъм казва, сте готови.
>> Така че истинската магия в тази алгоритъм изглежда да е в
че последната стъпка, сливане.
Тази проста идея просто сливане две неща, че това, което е в крайна сметка ще
да ни позволи да сортирате множество, да речем, осем елементи.
Така че аз имам още осем топки стрес нагоре Оттук осем парчета хартия и един
Google Glass -
които съм се да запазите.
>> [СМЯХ]
>> DAVID Malan: Ако можем да вземем осем доброволци, и да видим дали можем да
играят това, така.
Wow, OK.
Компютърни науки става забавно.
Добре.
Е, как за теб три, голямата ръка там.
Четири в гърба.
А какво ще кажеш, че ще правиш три в този ред?
И четири в предната част.
Така че осем, качвай се.
>> [СМЯХ]
>> DAVID Malan: Всъщност съм Не съм сигурен какво е то.
Дали е стрес топки?
Бюрото лампи?
Материалът?
Интернет?
>> OK.
Така че качвай се.
Кой би искал -
продължаваме да правим.
Нека да видим.
И това ви поставя в населено място -
сте в населено място един.
Опа, чакай малко.
1, 2, 3, 4, 5, 6, 7 - Добре.
Добре, всичко е наред.
Добре, така че всеки да има място, но не и по Glass Google.
Нека да си вадя тези нагоре.
Как се казваш?
>> Мишел: Мишел.
>> DAVID Malan: Мишел?
Добре, вие получавате да изглежда като онази, ако това е ОК.
Е, аз правя прекалено, предполагам, само за миг.
Добре, режим на готовност.
Опитваме се да излезе с използват случая за Google Glass, и ние
Мислех, че ще е забавно да правя просто това, когато хората са на сцената.
Ние ще запише света от тяхна гледна точка.
Добре.
Не е вероятно това, което Google предназначен.
Добре, ако нямате нищо против носенето това за следващите неудобни-та минута,
това би било чудесно.
>> Добре, така че ние имаме тук един набор от елементи, както и че на масиви, според
хартийки в тези хора " ръцете, в момента е в несортиран.
>> Мишел: О, това е толкова странно.
>> DAVID Malan: Това е почти случайна.
И в един момент, ние ще се опитаме за изпълнение се слеят подреди заедно
и да видим къде е този ключ прозрение.
И този трик тук с вид сливане е нещо, което не са поели още.
Ние действително се нуждаят от допълнително пространство.
Така че това, което ще бъде особено интересно за това е, че тези
момчета ще се придвижват малко малко, защото аз отивам да се предположи, че
има допълнителен набор от пространство, да речем, точно зад тях.
>> Така че, ако те са зад стола си, това е вторичен масив.
Ако те са седнали тук, това е първичния масив.
Но това е ресурс, който трябва не използват ливъридж до този момент с балон
вид, с избор сортиране, с вмъкване вид.
Спомнете си миналата седмица, всеки просто вид прокара на място.
Те не са използвали нито допълнителна памет.
Направихме стая за хора с придвижване на хора наоколо.
>> Така че това е ключово прозрение, също.
Има един компромис, като цяло в компютърни науки, на ресурсите.
Ако искате да се ускори нещо като време, започваш да
трябва да платят цената.
И един от тези цени е много често пространство, обема памет или твърд
дисково пространство, че използвате.
Или, честно казано, сумата на програмист време.
Колко време ви отнема, човешкото, действително да се приложат някои повече
сложен алгоритъм.
Но за днес, на компромис е времето и пространството.
>> Така че, ако вие може просто да задържите Вашия числа, така че ние можем да видим, че си
Всъщност съвпадение 4, 2, 6, 1, 3, 7, 8.
Excellent.
Така че аз ще се опитам да организирам неща, ако вие може просто да
следвай тук.
>> Така че аз отивам да се прилага, от една страна, Първата стъпка на pseudocode, който е
за въвеждане на елементи N, ако п е по-малко от два, след това се върнете.
Очевидно е, че не се прилагат, за да можем да продължат напред.
Така сортирате лявата половина на елементите.
Така че това означава, че аз ще се фокусирам внимание само за момент за тези
четири момчета тук.
Добре, какво да направя следващия?
>> Публика: Пъзел в лявата половина.
>> DAVID Malan: Така че сега трябва да се справи лявата половина на тези момчета.
Защото отново, да предположим, да си на Целта е да се справи със лявата половина.
Как се прави това?
Просто следвайте инструкциите, дори въпреки че го правим отново.
Така сортирате лявата половина.
Сега съм сортиране тези две момчета.
Какво следва?
>> Публика: Пъзел в лявата половина.
>> DAVID Malan: Пъзел в лявата половина.
Така че сега това, това място тук, е даден списък на площ 1.
И какво ти беше името?
>> PRINCESS DAISY: Принцеса Дейзи.
>> DAVID Malan: Принцеса Дейзи е тук.
И така, тя е вече сортирана, защото списъкът е с размер 1.
Какво да правя следващия?
OK, върни се, защото това е списък на размер 1, което е по-малко от 2.
Тогава каква е следващата стъпка?
И сега трябва да се вид изляза от ситуацията в ума си.
>> Пъзел с дясната половина, което е -
как ти е името?
>> LINDA: Linda.
>> DAVID Malan: Linda.
И така, какво ще правим сега, че Имаме списък с размер 1?
>> Публика: Върни.
>> DAVID Malan: Внимателно.
Връщаме първи, а сега трети етап - и ако аз един вид го изобразяват с
обхващащ две места сега, сега трябва да се слеят тези два елемента.
Така че сега, за съжаление, елементите не са в ред.
Но това е, когато процеса на сливане започва да се непреодолими.
>> Така че, ако вие може да се изправи само за миг, че ще ви трябва, в
момент, да се оттегли зад стола си.
И ако Linda, защото 2 е по-малък от 4, защо не
когато си наоколо първи?
Стой там.
Така че Линда, когато си наоколо първи.
>> Сега в действителност, ако това е просто масив бихме могли просто да я преместим в реално време
от този стол до това място.
Така че представете си, че отне известно постоянно брой стъпки 1.
И сега -
но ние трябва да ви постави в първото място тук.
>> И сега, ако можете да си наоколо, , както и, ние ще
да бъде в населено място два.
И въпреки, че това се чувства като тя е като известно време, това, което е хубаво в момента е
че лявата половина на лявата половина е вече подредени.
И така, какво е следващата стъпка, ако сега назад по-нататък в историята?
>> Публика: дясната половина.
>> DAVID Malan: Пъзел в дясната половина.
Така че вие ​​трябва да направите това, както добре.
Така че, ако можех да се изправя само за миг?
И как ти е името?
>> ДЖЕС: Джес.
>> DAVID Malan: Джес.
ОК, така че Джес е сега в ляво половина на дясната половина.
И така, тя е списъка с размер 1.
Тя очевидно подредени.
И ти беше името?
>> Мишел: Мишел.
>> DAVID Malan: Michelle е очевидно списък с размер 1.
Тя вече подредени.
Така че сега се случва магията, процеса на сливане.
Така че кой ще дойде?
Очевидно Мишел.
Така че, ако може да дойде отзад.
Пространството, което имате на разположение за нея сега е точно зад този стол тук.
И сега, ако може да се върне, както и, сега ние имаме, да бъде ясна, две
половини, всяка от които с размер 2 -
и само заради изобразяването му, ако може да направи малко място -
един лявата половина тук, един дясната половина тук.
>> Пренавиване напред в историята.
Каква е следващата стъпка?
>> Публика: Обединяване.
>> DAVID Malan: Така че сега трябва да се слеят.
Така че, ОК, така че сега, за щастие, ние просто освободени четири стола.
Така че ние сме използвали два пъти повече памет, но можем да дадем флип-флоп между
на два масива.
Така че кой номер е да са на първо място?
Така Мишел, очевидно.
Така дойде и поеми мястото си тук.
И след това номер 2 е очевидно следващия, така че ела тук.
Номер 4, номер 6.
И отново, въпреки че има малко ходене участва,
Наистина, това може да се случи незабавно, чрез преместване на един -
OK, добре играе.
>> [СМЯХ]
>> DAVID Malan: И сега сме в доста добра форма.
В лявата половина на цялата вход вече е сортиран.
Добре, така че тези момчета трябваше предимството си -
как е в крайна сметка всички момичета на наляво и всички момчета от дясно?
>> ОК, така че момчета "до сега.
Така че аз няма да ви преведе през тези стъпки.
Ще видим дали можем да кандидатства отново същото pseudocode.
Ако искате да отидете напред и да се изправя, и момчета, нека да ви дам микрофона.
Виж, ако не може да се реплицира какво ние що го направих тук, на
другия край на списъка.
Кой трябва да говори първо, въз основа на алгоритъм?
Така обясни това, което правите, преди да да извършите каквито и крака движения.
>> SPEAKER 1: Добре, тъй като Аз съм на лявата половина на
лявата половина, се върна.
Така ли е?
>> DAVID Malan: Добре.
>> SPEAKER 1: И след това -
>> DAVID Malan: Кой прави микрофона преминете към следващата?
>> SPEAKER 1: Next номер.
>> SPEAKER 2: Така че аз съм в дясната половина на лявата половина на
лявата половина, и се върна.
>> DAVID Malan: Добре.
Ще се върнете.
Така че сега, каква е следващата за вас двамата?
>> SPEAKER 2: Искаме да видим кой е по-малък.
>> DAVID Malan: Точно така.
Ние искаме да се слеят.
Мястото, ние ще използваме, за да се слеят ти в, въпреки че те са
очевидно подредени вече, ние ще да следват същия алгоритъм.
Така че, който отива в гърба първо?
Така 3, и след това 7.
И сега микрофона отива за тези момчета, OK?
>> SPEAKER 3: Така че аз съм на дясната половина на лявата половина, и ми н е по-малко от
1, така че аз съм просто ще мине -
>> DAVID Malan: Добре.
>> SPEAKER 4: Аз съм дясната половина на дясната половина на дясната половина, а аз съм
Също така един човек, така че аз съм ще се върне.
Така че сега ние се слеят.
>> SPEAKER 3: Така че да се върнем.
>> DAVID Malan: Така че отидете в гърба.
Така 5 отива, а след това 8.
И сега аудитория, която е стъпка, която трябва да сега назад
архивирате в нашите умове?
>> Публика: Обединяване.
>> DAVID Malan: Сливане на лявата половина и дясната половината от първоначалния лявата половина.
Така че сега -
и само за да направи това ясно, направи малко пространство
между вас двамата.
Така че сега е на два списъка, наляво и надясно.
Е, как сега да се слеят момчета в на предния ред седалки отново?
>> 3 отива на първо място.
След 5, очевидно.
След 7, а сега 8.
OK, а сега сме ние?
>> Публика: Не е направено.
>> DAVID Malan: Не е направено, тъй като Очевидно е, че има един етап преди края.
Но отново, причината, аз съм с този жаргон като "назад в ума си"
това е, защото това е наистина какво се случва.
Преминаваме през всички тези стъпки, но ние сме нещо като пауза за
момент, гмуркане дълбоко в алгоритъм, спирайки за момент,
гмуркане дълбоко в алгоритъм, и сега трябва да се справи на назад в нашата
умовете и връщане на всички тези слоеве , че сме нещо като задържа.
>> Така че сега имаме два списъка с размер 4.
Ако вие може да се изправи за последен път и да направи малко място тук, за да
стане ясно, че това е най-ляво половината от оригинала,
дясната половина на оригинала.
Кой е първият номер, който ние трябва да дръпнете в гърба?
Michelle, разбира се.
>> Затова ние Michelle тук.
И кой е номер 2?
Номер 2 е по гръб, както добре.
Номер 3?
Excellent.
Номер 4, номер 5, № 6, номер 7 и номер 8.
>> ОК, така че се чувствах като много от стъпки, със сигурност.
Но сега нека да видим дали не можем да потвърдим нещо интуитивно, че това
алгоритъм фундаментално, по-специално като п стане наистина голям, тъй като сме виждали
с анимации, е основно по-бързо.
Така че аз твърдя, този алгоритъм, в най-лошия случай и дори в най-добрия случай,
е голям O на п пъти дневник п.
Това означава, че има някои аспекти на настоящото алгоритъм, който взема п стъпки, но
има и друг аспект някъде в че итерация, че примка, че
се лог н стъпки.
Можем ли да постави пръста си върху това, което тези две числа се отнасят до това?
Е, къде -
откъде микрофона отидете?
>> SPEAKER 1: Бихте дневника п бъде счупи ни на две -
разделяне на две, по същество.
>> DAVID Malan: Точно така.
Всеки път, когато виждаме във всеки алгоритъм, като по този начин Досега е имало този модел на
разделяне, разделяне, разделяне.
И това обикновено намалява за нещо, което е
логаритмична, влезте основата 2.
Но тя наистина може да бъде всичко, но влезте основата 2.
>> Сега какво ще кажете за п?
Виждам, че ние любезно от ваша страна разделена момчета - те разделят, те разделят,
ви разделят, те разделят.
Откъде идва краят идва?
>> Така че това е сливане.
Защото мисля за това.
Когато обединявате осем души заедно, при която половината от тях са набор от четири
, а другата половина са друг комплект от четири, как да отида
за правене на сливането?
Е, вие го е направил доста интуитивно.
>> Но ако вместо да го направи малко по- методично, може би щях да посочи
най-лявата лице за първи път с лявата си ръка и посочи към най-лявата лице
на, че половината с дясната си ръка, и Просто впоследствие мина през
списък и посочи най-малкия елемент всеки път, движейки пръста си отново и
повече, ако е необходимо в рамките на списъка.
Но това, което е ключова за това сливане Процесът е аз съм сравняване на тези двойки
елементи.
От дясната половина и отляво половина, аз никога не съм веднъж връщане назад.
>> Така че самото сливане е като не повече от п стъпки.
И колко пъти трябва да направи това сливане?
Е, не повече от N, и ние просто видя, че с окончателното сливане.
И така, ако направите нещо, което се влезте п стъпки п пъти, или обратното,
това ще ни даде п пъти дневник п.
>> И защо това е по-добре?
Е, ако ние вече знаем, че дневника п е по-добре от N - нали?
Видяхме в двоично търсене, телефонния указател Например, дневник п определено беше
по-добре от линейни.
Така че това означава, че N пъти дневник п е определено по-добре от време п друга
N, N AKA квадрат.
И това е, което в крайна сметка се чувстват.
>> Така аплодисменти, ако можем, за тези момчета.
>> [APPLAUSE]
>> DAVID Malan: И вашите прощални подаръци - може да запази номера,
ако искате.
И си прощален подарък, както обикновено.
О, и ние ще Ви изпратим кадри, Мишел.
Благодаря.
Добре.
Помощ за себе си до стрес топката.
>> И нека да спра, междувременно, нашият приятел Rob Bowden да предложи
малко по-различна гледна точка по този въпрос, тъй като можете да мислите за тях
стъпки, които се случват в малко различен начин.
В действителност, настройка за това, което е около Rob да ни покаже предполага, че ние сме
вече е направено на разделяне на голям списък на осем малки списъци,
всяка с размер 1.
>> Така че промяна на pseudocode на малко по-просто някак да стигнат до
Основната идея на това как работи сливане.
Но времето на работа на това, което той е на път да направите, е все още
ще бъде един и същ.
И отново, за настройка тук е, че той е започна с осем списъци с размер 1.
Така че не сте пропуснали тази част, където той е всъщност направи дневника N, N дневник, дневник п
разделяне на входа.
>> [VIDEO PLAYBACK]
>> -Това е всичко за една стъпка.
За втора стъпка, многократно сливат чифта списъци.
>> DAVID Malan: Hm.
Само аудио идва от моя компютър.
Нека да опитаме отново.
>> -Просто произволно подбирате кои - сега имаме четири списъка.
Научете преди.
>> DAVID Malan: Ето.
>> -Обединяване на 108 и 15, ние в крайна с списъка 15, 108.
Сливане на 50 и 4, ние свърши с 4, 50.
Сливане на 8 и 42, ние свърши с 8, 42.
И сливане 23 и 16, ние в крайна сметка с 16, 23.
>> Сега всички наши списъци са с размер 2.
Забележете, че всяка четири списъка е сортиран.
Така че можем да започнем обединяване чифта списъци отново.
Сливане на 15 и 108 и 4 и 50 години, ние първо извади 4, а след това на 15, а след това
50, след това 108.
Сливане на 8, 42 и 16, 23, за първи път се 8, а след това на 16, а след това на 23,
след това на 42.
>> Така че сега ние имаме само два списъка с размер 4, всеки от които е сортирани.
Така че сега ние се слеят тези два списъка.
На първо място, ние се на 4, а след това вземем 8, след това вземем 15, след това 16, след това
23, след това 42, след това 50, след това 108.
>> [END възпроизвеждане на видео]
>> DAVID Malan: Отново, бележка, той никога докосна дадена чашата повече от един път
след напредък отвъд него.
Така че той никога не е повтаряне.
Така че той винаги се премести в страна, и това е, когато имаме нашата п.
>> Защо не нека да спра един анимация които видяхме по-рано, но този път
съсредоточи само върху подреди сливат.
Позволете ми да отида напред и да я увеличите в на този тук.
Нека първо да изберете произволен вход, подчертае това, и ще можете да сортирате виж
това, което сме смятали за даденост, по-рано, сливат подреди всъщност прави.
>> Така забележите, че получавате тези половинки или тези квартали или те отдават на
Проблемът, който изведнъж започнете да приемате добра форма.
И накрая, ще се видим в самия край, че бам,
всичко се слива заедно.
>> Така че това са само три различни се на същата идея.
Но ключът прозрение, точно като разделение и владей в първия клас,
е, че ние решихме да се разделят по някакъв начин на проблема в нещо по-голямо, в
нещо, нещо като еднакви по дух, но по-малки и по-малки и по-малки
и по-малки.
>> Сега още един забавен начин да сортирате мисля за тях, въпреки че това не е
ще ви дам същия интуитивен разбиране, е
следното анимация.
Така че това е видео някой, взети заедно този, свързан различен
звуци с различни операции за вмъкване вид, за сортиране сливане, и
за няколко други.
Така че в един момент, аз отивам да се удари игра.
Това е около една минута време.
И въпреки че все още можете да видите модели случва, този път може да
също така да изслушат как тези алгоритми са изпълнение по различен начин и с
малко по-различни модели.
>> Това е вмъкване вид.
>> [ТОНОВЕ ЗВУЧИ]
>> DAVID Malan: Той отново се опитва да вмъкнете всеки елемент
в която той принадлежи.
Това е балон подреди.
>> [ТОНОВЕ ЗВУЧИ]
>> DAVID Malan: И можете да сортирате на усещане как сравнително малко работа, тя прави
на всяка стъпка.
Това е, което tediousness звучи.
>> [ТОНОВЕ ЗВУЧИ]
>> DAVID Malan: Това е избор на вид, където изберете елемент искаме от
преживява отново и отново и отново и да я постави в началото.
>> [ТОНОВЕ ЗВУЧИ]
>> DAVID Malan: Това е сливат вид, които наистина може да започнете да се чувствате.
>> [ТОНОВЕ ЗВУЧИ]
>> [СМЯХ]
>> DAVID Malan: нещо, наречено GNOME вид, които не сме разглеждали.
>> [ТОНОВЕ ЗВУЧИ]
>> DAVID Malan: Така че нека да видя, сега, разсеян, колкото се надяваме, са от
музика, ако мога да се измъкне малко малко математика тук.
Така че има и четвърти начин, по който можем да мисля за това, какво означава това
функции, за да бъде по-бързо, отколкото тези, че сме виждали преди.
И ако идваш на курса от математика фон, можете
всъщност знаят, може би вече, че може да шамар срок на тази техника -
а именно рекурсия, функция че по някакъв начин се призовава.
>> И отново припомни, че подреди сливат pseudocode е рекурсивно в смисъл,
че една от стъпките сливат подреди на беше да се обадя вид -
т.е. себе си.
Но слава Богу, защото ние продължавахме призовава вид, или да се слеят вид,
специално, по-малък и по-малки и по-малък списък, ние в крайна сметка
стигна дъното, благодарение на това, което ние ще се обадя база случай, трудно кодирани случай, че
каза, че ако в списъка е малък, по-малко от 2 В този случай, просто се върнете веднага.
Ако ние не разполагаме с този специален случай алгоритъм никога няма да намерят дъно,
и вие наистина ще влязат в един безкраен цикъл наистина завинаги.
>> Но да предположим, че искаме да сложи сега някои номера на този, отново, като се използва п
като размера на входа.
И аз исках да ви попитам, какво е общото време участва в
работи сливат вид?
Или по-общо, това, което е стойността на това във времето?
>> Ами това е доста лесно да се измери това.
Ако п е по-малко от 2, времето, необходимо в сортирането на н елементи,
където п е 2, е 0.
Защото ние просто се върнете.
Не е работа да се свърши.
Сега може би, може би това е една стъпка или две стъпки, за да разбера размера на
работи, но това е достатъчно близо до 0, че Аз съм просто ще кажа, няма такава работа
изисква, ако списъкът е толкова малка, да бъде безинтересно.
>> Но този случай е интересен.
The рекурсивни случай е клон на на pseudocode че каза друго, нещо
лявата половина, сортирате правото половина, слее двете половини.
Сега защо този израз представляват тази сметка?
Е, T на п просто означава време, за да сортирате н елементи.
И след това в дясната страна на знак за равенство там, T п разделени
с 2 се отнася за цената на какво?
Сортиране лявата половина.
Другият T п разделена на 2 е предполага, че се отнасят до разходи за
сортирате дясната половина.
>> И тогава п плюс?
Дали сливане.
Защото, ако имате два списъка, единият от размер н над 2 или подобен на размера н
над 2, трябва да се докосват по същество всеки от тези елементи, също като Rob
докосна всяка от чашите, а само както отбелязахме по всяка от
доброволци на сцената.
Така че п е за сметка на сливане.
>> Сега за съжаление, тази формула е също така да се рекурсивно.
Така че, ако зададе въпроса, ако п е, да речем, 16, ако има 16 души на сцената
или 16 чаши във видеото, колко общо стъпки отнема да ги сортирате
с вид сливане?
То всъщност не е очевиден отговор, защото сега ще трябва да се справи с
рекурсивно отговори на тази формула.
>> Но това е ОК, защото нека да предложи което правим следното.
В момента участват 16 души, за да сортирате или 16 чаши ще бъдат представени
обикновено като Т от 16.
Но това се равнява, според нашите предишна формула, 2 пъти количеството
на времето, необходимо, за да сортирате 8 чаши плюс 16.
И отново, плюс 16 е времето да се слеят, и два пъти по-T на 8 е
време, за да сортирате лявата половина и дясната половина.
>> Но пак, това не е достатъчно.
Трябва да се потопите още по-дълбоко.
Това означава, че трябва да отговорим на въпрос, какво е Т на 8?
Е T на 8 е само на 2 T пъти на 4 плюс 8.
Е, това, което е на 4 T?
T на 4 е само на два пъти T от 2 плюс 4.
Е, какво е T на две?
T на 2 е само на два пъти T на 1 плюс 2.
>> И пак, ние сме вид се остана в този цикъл.
Но това е на път да удари, че така наречената база случай.
Защото това, което е на T 1, се твърди?
0.
Така че сега най-накрая можем да работим назад.
>> Ако T на 1 е 0, сега мога да се върна с още един ред в този човек тук, и мога да
включете 0 за T на 1.
Така че това означава, че то се равнява на два пъти нула, иначе известни като 0, плюс 2.
И така, че целият израз е 2.
>> Сега, ако съм на T на две, чийто отговор е 2, го включете в средната линия, T
на 4, че ми дава 2 пъти 2 плюс 4, така че 8.
Ако след това включете в 8 с предходната ред, че ми дава 2 пъти 8, 16.
И ако след това продължи, че с 24, добавяйки в 16, ние най-накрая се получи
стойност на 64.
>> Сега, само по себе си вид говори нищо означението М, на
голям О, омега, че сме говорим за.
Но се оказва, че 64 е наистина 16, размерът на входа,
влезте база 2 от 16.
И ако това е малко непознат, просто мисля обратно, и то ще се върне
да в крайна сметка.
Ако това е регистър на база 2, това е като две издигнат до това, което ви дава 16?
О, това е 4, така че е 16 пъти по четири.
>> И пак, това не е голяма работа, ако това е нещо като неясен спомен сега.
Но за сега, да вземе на вярата че 16 дневник 16 е 64.
И така, наистина, с този прост здрав разум проверите, като потвърдим -
но не се оказа официално -
че времето за работа на обединяването Сортът е наистина N влезте п.
>> Така че не е зле.
Определено е по-добре от алгоритми, които сме виждали до този момент, и
това е, защото сме ливъридж, един, техника, наречена рекурсия.
Но по-интересно от това, че идеята за разделяне и завладяване.
Отново, наистина седмици 0 неща, които дори и сега се повтаря в
по-убедителен начин.
>> Сега забавно малко упражнения, ако сте никога не е правил това - и най-вероятно
няма да има, защото нещо нормално хора не мислят за това.
Но ако отидете на google.com и ако Аз искам да науча нещо за
рекурсия, Enter.
>> [СМЯХ]
[Смях]
DAVID Malan: Bad шега бавно разпространение.
[СМЯХ]
DAVID Malan: Само в случай, че е там.
Аз не пише правилно, и там е шега.
Добре.
Обяснете го на хората до вас, ако това не е съвсем кликнали, просто все още.
Но рекурсия, по-общо, се отнася в процеса на функции за извикване
себе си, или по-общо, се раздели Проблемът в нещо, което може да бъде
решен парче чрез решаване на идентични представителни проблеми.
>> Е, нека смяна на предавките само за миг.
Ние обичаме да приключи на някои cliffhangers, така че нека започнем да настроите
на етапа, в продължение на няколко минути, по една много проста идея -
че на смяна на два елемента, нали?
Всички тези алгоритми, ние сме били говорим за последните няколко
Лекциите включват някои вид на дискове.
Днес се визуализират чрез повдигайки нагоре от столовете и
разхождате, но в кода, бихме просто да е елемент от един масив
и цоп го на друг.
>> И как ще го направим?
Е, нека да вървим напред и пишат бърза програма тук.
Аз ще отида напред и да направим това като следното.
Нека наречем това -
какво искаме да се обадя на този?
>> Всъщност, не.
Нека назад.
Аз не искам да правя това Катерачът още.
Тя ще развали забавно.
Да го направим вместо това.
>> Да предположим, че искам да напиша малко програма и че сега обхваща тази
Идеята на рекурсия.
Някак си имам избързвам там.
Отивам да направите следното.
>> Първо, един бърз включва стандартен io.h, както и включват на cs50.h.
И тогава аз ще вървим напред и декларира Int основната невалидни
по обичайния начин.
Разбрах, че съм сполучлив термин на файл, така че нека само да се добави. в разширяването тук, така че
че можем да го компилирате правилно.
Започнете тази функция изключване.
>> И функцията искам да пиша, доста просто, е тази, която изисква от
ръководство за броя и след това добавя всички числа, между които
номер и, да речем, 0.
Така че първо аз ще вървим напред и декларира вътр п.
След това копирате някакъв код, че сме използвали за известно време.
Докато нещо не е вярно.
Аз ще се върна на това след малко.
>> Какво искате да направите?
Искам да кажа, ФОРМАТ положителна цяло число, моля.
И тогава аз ще казват п получава получите вътр.
Така че отново, някои стереотипния код че сме използвали преди.
И аз ще го направя а п е по-малко от 1.
Така че това ще гарантира, че на потребителя ми дава положително число.
>> И сега ще направя следното.
Искам да добавите до всички номера между 1 и и п, или 0 и п,
което е същото, за да получите общата сума.
Така че големият символ сигма че може да изземат.
Така че аз ще направя това, като първо призвание функция, наречена Sigma,
минаваща го в N, а след това аз ще казват ФОРМАТ, отговорът е точно там.
>> Така че в кратко, да получа и INT от потребителя.
Аз се гарантира, че е положителна.
Декларирам, променлива наречена отговор на тип Int и се съхранява в него на връщане
стойност на сигма, преминавайки в п като вход.
И тогава аз разпечатате този отговор.
>> За съжаление, въпреки че сигма звучи като нещо, което може да бъде в
на math.h файл, декларацията си, това всъщност не е така.
Така че това е ОК.
I може да реализира това сам.
Отивам да се приложи нарича функция сигма, и това ще отнеме
параметър -
нека просто го наречем m, само така че е по-различно.
И след това тук, аз ще кажа, Е, ако М е по-малко от 1 - това е
много безинтересно програма.
Така че аз ще отида напред и незабавно да върне 0.
Просто няма смисъл да добавите до всички на числа между 1 и М, ако т
е самата 0 или отрицателни.
>> И тогава аз ще вървим напред и направите това много итеративно.
Аз ще направя този вид на старата школа, и аз отивам да вървим напред
и да кажа, че аз ще обяви сумата да бъде 0.
Тогава ще се наложи за линия на Int -
и ме остави да го направя и нашето разпространение на кодове, така че имате копие
у дома. Int I получава 1 на до I е по-малко от или равно на m.
Аз плюс плюс.
И тогава вътре в този за линия -
ние сме почти там -
Сумата получава сума плюс 1.
И тогава аз ще върне сумата.
>> Така и направих това бързо, съвсем естествено.
Но отново, чиято основна функция е доста ясно, на базата на код, ние сме
дадени до този момент.
Използва двойна линия, за да получите положителен INT от потребителя.
След това така, че средно за нова функция наречена Sigma, като го нарече, отново, п.
И аз се съхранява на върнатата стойност, отговорът от черна кутия в момента
известен като сигма, в променлива наречен отговор.
Тогава аз го отпечатате.
>> Ако сега продължава историята, как се сигма приложени?
Аз предлагам да се прилага, както следва.
Първо, малко за проверка на грешки за да се уверите, че потребителят не е
каша с мен и минаваща през някои отрицателни или стойност 0.
Тогава обяви нарича променлива обобщение и това трябва да е 0.
>> И сега започват да се движат от и равен 1 по целия път до и включително m,
защото искам да се включи цялата числа от едно до m включително.
И вътре в този за линия, аз просто правя Сумата получава каквото и да е сега, плюс
стойността на I.
Плюс стойността на I.
>> Като настрана, ако не сте виждали това преди, има някаква синтактична захар
за тази линия.
Мога да пренапише това като плюс и равни, само за да си спестя няколко натискания на клавиши
и да изглежда малко по-хладно.
Но това е всичко.
Това е функционално и също нещо.
>> За съжаление, този код е Няма да съставят все още.
Ако аз тичам да сигма 0, как съм Аз ще се развика?
Какво ще да не харесваш?
>> Публиката: [недоловим].
>> DAVID Malan: Да, не е декларирал функцията на върха, нали?
C е много глупаво, по това, че само прави това, което му казвате да прави, и вие
трябва да го направим в този ред.
И така, ако аз хит Въведете тук, аз отивам да получите предупреждение за сигма имплицитно
декларация.
>> О, не е проблем.
I може да стигнат до върха, и мога да казват, добре, чакай малко.
Sigma е функция, която връща едно цяло число и да го очаква
Int като вход, точка и запетая.
Или би могло да постави цялата функция над основната, но като цяло, бих
Препоръчваме срещу това, защото това е хубаво винаги да има основна през тавана, така
можете да се потопите в правото и да знае какво е Програмата прави с четене основната първи.
>> Така че сега нека да изчистите екрана.
Римейк сигма 0.
Всичко изглежда да се провери.
Нека да тече сигма 0.
Положителен наред.
Аз ще го дам номера 3 да го прости.
Така, че трябва да ми даде 3 плюс две плюс едно, така че 6.
Въведете и наистина да получа 6.
>> Мога да направя нещо по-голямо -
50, 12, 75.
Точно както допирателната, аз ще направя нещо нелепо като наистина голяма
номер, О, това действително отработени изход -
а, аз не мисля, че е прав.
Нека да видим.
Нека наистина се забъркваш с него.
>> Това е проблем.
Какво става?
Кодът не е толкова зле.
Тя все още е линейна.
Свирене е добър ефект, все пак.
Какво става?
>> Не съм сигурен дали съм го чувал.
Така се оказва - и това е като настрана.
Това не е в основата на Идеята на рекурсия.
Оказва се, защото се опитвам да представляват такъв голям брой, най-
вероятно това е погрешно да се от C като не положително число,
но отрицателно число.
>> Ние не сме говорили за това, но то Оказва се, че са отрицателни числа
в света в допълнение до положителни числа.
И начините, по които можете да представлява отрицателно число
по същество е, като използвате един специален малко, за да показват,
положително върху отрицателни.
Това е малко по-сложно, но това е основната идея.
>> Така че, за съжаление, ако C е объркващо един на тези битове като всъщност означава,
О, това е отрицателно число, моята линия тук, например, всъщност никога не е
ще се прекрати.
Така че, ако са били действително отпечатване нещо отново и отново, ние ще
виж цяло много.
Но отново, това е освен точка.
Това е наистина само един вид интелектуалното любопитство, че ще дойдем
обратно към евентуално.
Но за сега, това е правилно изпълнението, ако приемем, че
потребителят ще осигури целочислени които се побират в цели числа.
>> Но аз твърдя, че този код, честно казано, може да се направи много по-просто.
Ако целта на ръка е да се предприемат редица като m и добавете цялото количество
номера между него и един, или обратното между 1 и, смея да твърдя
че мога да взема това идеята, че се слеят подреди имаше, което беше като проблем
с този размер и разделянето на в нещо по-малко.
Може би не половината, но по-малки, но представителен същото.
Същата идея, но по-малък проблем.
>> Така че аз съм всъщност - да ме спаси този файл с различен брой версия.
Ще се обадя тази версия 1 вместо 0.
И аз твърдя, че всъщност мога да reimplement това в този вид
оказващ влияние начин.
>> Отивам да оставите част от него сам.
Аз ще кажа, ако m е по-малко от или дори равни на 0 -
Аз съм просто ще бъде малко по това време анален
с моята проверка за грешки -
Аз ще отида напред и да се върне 0.
Това е произволно.
Аз съм просто реши, ако потребителят ми дава отрицателно число, аз съм
връща 0, и те е трябвало да прочетете документацията по-отблизо.
>> Друго -
забележите това, което аз ще направя.
Друго аз отивам да се върне m плюс -
това, което е сигма на т?
Е, сигма на m плюс минус 1 m, m плюс минус 2, плюс минус 3 m.
Аз не искам да пиша всичко това.
Защо не правя просто шута?
Рекурсивно се наричам с леко по-малък проблем, точка и запетая,
и го наричат ​​на ден?
>> Така ли е?
Сега тук също може да се чувстват или тревожи че това е един безкраен цикъл, че съм
предизвикване, което аз съм за прилагане сигма като се обадите на сигма.
Но това е подсъдно, защото мислех напред добавена кои редове?
>> Публиката: [недоловим].
>> DAVID Malan: от 23 до 26, които е ми ако състояние.
Защото това, което е хубаво за изваждане тук, защото аз държа
раздават сигма-малки проблеми, по-малки проблеми, по-малък - това не е
половината от размера.
Това е само една малка стъпка бебе, но това е ОК.
Защото в крайна сметка, ние ще работим нашия път до 1 или 0.
И след като ударихме 0, сигма е не ще се обади повече.
Ще се върнете незабавно 0.
>> Така че ефектът, ако нещо вятър тази в ума си, е да се добави m плюс
m минус 1, плюс m минус 2, плюс минус m 3, плюс точка, точка, точка, m минус
m, в крайна сметка ти дава 0, и Ефектът е в крайна сметка да се добавят всички
тези неща заедно.
Така че ние не трябва, с рекурсия, решен проблемът, че ние
не може да реши преди.
В действителност, версия 0 на това, и всяка проблем към днешна дата, е решими
само с помощта на вериги или по време на вериги или подобни конструкции.
>> Но рекурсия, смея да кажа, ни дава различен начин на мислене за
проблеми, при което, ако можем да вземе проблем, тя се разделя от нещо
малко голям в нещо малко по- по-малки, аз твърдя, че ние можем да го решим
може би малко по-елегантно от гледна точка на проекта, с по-малко код,
и може би дори и решаване на проблеми, които биха бъде по-трудно, тъй като ние в крайна сметка ще
виж, решаване на чисто итеративно.
>> Но Катерачът, че го направих искат да ни оставят на това беше.
Нека да вървим напред и да се отворят създаване на файл от -
Всъщност, нека отида и направите това много бързо.
Нека да вървим напред и да предложи следното.
Сред днешния закон е този файл тук.
Този тук, noswap.
>> Така че това е една глупава програма, която I шибна, която претендира да направя
следното.
В главната, тя първо декларира Int нарича х и е възложила
стойността на 1.
След това го декларира Int Y и възлага това на стойност 2.
Тогава той печата какво х и у е.
Тогава казва: смяна, точка точка точка.
>> След това той твърди, че се обажда функция наречен суап, минаваща през X и
Y, идеята за което е, че се надяваме х и у ще се върне
различни, точно обратното.
След това го твърдят разменят!
с удивителен знак.
След това го отпечатва х и у.
>> Но се оказва, че това много проста демонстрация надолу
тук е всъщност бъги.
Въпреки, че аз съм за обявяване на временна променлива и временно удар в
това, тогава аз съм пренасочване а стойността на б -
който се чувства разумно, защото съм спаси копие на в темп.
Тогава актуализира б на равно каквото е в темп.
Този вид на черупката игра на преместване на в Б и В, а с помощта на тази
средна температура се чувства човек на име напълно разумна.
>> Но аз твърдя, че когато пускам това код, като ще правим сега -
нека да вървим напред и да го добавите тук.
Ще се обадя на този noswap.c.
И както подсказва и името, това не е Ще бъде правилната програма.
Направи noswap. / Не суап.
х е 1, у е 2, размяна, разменят.
х е 1, у е 2.
Това е фундаментално погрешно, дори че това изглежда перфектно
разумен за мен.
И има причина, но не сме ще разкрие причината, просто все още.
>> За сега втората Катерачът исках да ви оставя с е този, на
обявяването на видове за купон кодове.
Нашата иновациите с късни дни тази година предизвика нетривиален брой
на въпроса, който беше не нашето намерение.
Намерението на тези купони, при което, ако го направите част от проблема
определени по-рано, като по този начин става един допълнителен ден, Беше наистина да ви помогна да помогне
се започне рано, сортиране на стимулите от вас.
Ни помага да разпространявате натоварване в работно време по-добре, така че
Това е нещо печеливша.
>> За съжаление, мисля, че моите инструкции не са били, към днешна дата, много ясно, така че
Върнах се този уикенд и се актуализира спец. в по-големи, по-смели текст
обясни куршуми като тези.
И за да го кажа по-публично, чрез подразбиране, проблемни групи се дължат четвъртък
по обед на учебната програма.
Ако започне рано, за довършителни работи част от на проблема, определен от сряда в 12:00
PM, частта, която се отнася за купон код, идеята е, че можете да удължите
си крайният срок за P зададете до петък.
Това е, отхапа малка част от P настроите спрямо това, което обикновено е
по-голям проблем, и да купите себе си един допълнителен ден.
Отново, това стане ли мисли за проблема набор, получава възможност да
работно време по-рано.
Но проблемът купон кодекс е все още длъжни, дори и ако не го представя.
>> Но по-убедително е това.
(Настрана) и тези хора напускане рано са ще съжаляваш.
Както са хората на балкона.
Извиняваме предварително на хора на балкона поради причини, които ще бъдат
ясно в един момент.
>> Така че ние сме щастливи, че имаме една от Бивши CS50 си събратя главата преподаване в
една компания, наречена dropbox.com.
Те са много щедро дарява купон код тук за тази много място,
което е нагоре от обичайните 2 гигабайта.
Така си и мислех, че ще направим по този последна бележка е да направи малко на награди,
при което в един момент, ние ще разкрие победителят и кой има купон
код, който можете да преминете към тяхното сайт, го въведете, и готово, може да получи
много повече Dropbox пространство за Вашия уреда и за личните си файлове.
>> И първото, които биха искали да участват в тази рисунка?
Добре, сега, че го прави още по-забавно.
Човекът, който получава тази 25-гигабайтов купон код - което е далеч
по-наложителна от края на ден сега, може би -
е този, който е седнал на върха на седалката, под който има
че купон код.
Сега можете да погледнете под си седалката.
>> [VIDEO PLAYBACK]
>> -Едно, две, три.
>> [Крещи]
>> -Можете да получите колата!
Можете да получите колата!
>> DAVID Malan: Ще видим ти в сряда.
>> -Можете да получите колата!
Можете да получите колата!
>> DAVID Malan: Балкон хора, хайде тук на фронта,
където имаме екстри.
>> -Всеки получава една кола!
Всеки получава една кола!
>> [END възпроизвеждане на видео]
>> Разказвач: На следващото CS50 -
>> SPEAKER 5: О, Боже мой, Боже, Боже, Боже Боже, Боже, Боже, Боже, Боже, Боже -
>> [UKELELE ПИЕСИ]