[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]