>> Даг Ллоид: Дакле, у ЦС50 смо научили о низ сортирање и претраживање
алгоритми.
А понекад може да буде мало незгодно да би
Трацк шта алгоритам шта ради.
Стварно смо само обрано превише површину,
постоје многе друге претраживање и сортирање алгоритама.
Дакле, у овом видеу идемо Само потрајати неколико минута
покушати да дестилирати сваки алгоритам до његових основних елемената
тако да можете да се сетите највише важне информације о њима
и бити у стању да артикулишу разлике, ако је потребно.
>> Први је избор врста.
Основна идеја иза избора врсте се наћи најмањи елемент несортираног
у низу и његово заменити са Први мусиц елемент тог низа.
Рекли смо да у најгорем случају рун време које је н квадрат.
А ако желите да се сетим зашто, узмите погледајте избор методу видео.
Време најбољи случај Рун је такође н квадрат.
>> Буббле сорт, идеја иза тога једна је да замени суседне парове.
Дакле, то је кључ који ће вам помоћи Сећам се разлика.
Избор врсте је, до сада, наћи смаллест-- мехур
сорта је замени суседне парове.
Ми свап суседне парове елемената ако
су од реда, што је практично бубблес веће елементе десно,
ау исто време такође креће за кретање мањих елемената на левој страни.
У најгорем случају време случај Рун од балон врсте је н квадрат.
Време најбољи случај Рун од балона врста је н.
Јер у тој ситуацији не стварно--
можда нећемо морати да било какве свопови уопште.
Имамо само да један пролазе кроз све н елемената.
>> У унесени врсте је Основна идеја овде се мења.
То је кључна реч за уметање врсте.
Идемо у једном корак кроз Низ од лева на десно.
И као што то чинимо, ми смо да пребаци елемената
смо већ видели би направили места за мање ти који морају да негде стане
назад у том делу сортира.
Тако градимо сортирану низ један елеменат у исто време, с лева на десно,
и пребацимо ствари да направи места.
У најгорем случају Рун време убацивање врста је н квадрат.
Време најбољи случај воде је н.
>> Мерге сорт-- кључне речи овде се дели и спојити.
Делимо пуну низ, без обзира да ли то је шест елемената, осам елемената,
10.000 елементс-- смо га поделили доле за половину, за половину, за половину,
док не будемо имали под низу од Н Оне низова елемената.
Скуп Н Оне низова елемената.
Тако смо почели са једним 1.000 елемената низ,
и дођемо до тачке где смо има 1.000 низове један елемент.
Онда смо почели да споји те под низова заједно у исправном редоследу.
Дакле, узмемо два низа један елемент и створити низ од два елемента.
Узимамо два низа два елемента и створити низ од четири елемента
и тако даље и тако даље све док имамо поново обновљена један Н елемент низа.
>> У најгорем случају Рун време спајање врсте је н пута лог н.
Ми имамо н елемената, али ово комбинујући процес
траје лог н кораци да се назад на пуну низ.
Најбољи случај рун тиме је такође Н дневник Н зато што овај процес не баш
занима ме да ли је низ била поредани или не у почетку.
Процес је исти, нема постоји начин да се кратког споја ствари.
Тако Н лог Н у најгорем случају, Н лог Н у најбољем случају.
>> Разговарали смо о два потрази алгоритама.
Дакле, линеарна претрага је око итератинг.
Настављамо преко низа Једном, с лева на десно,
покушавам да пронађем број да тражимо.
У најгорем случају рун тиме је велики о н.
Можда нам је потребно итератинг Сваки елемент преко
да пронађе елемент да тражите Јер, било у последњој позицији,
или уопште не.
Али не можемо потврдити да је до ми смо гледали све.
м најбољем случају, одмах наћи.
Најбољи-Случај Рун време линеарна претрага је омега 1.
>> На крају, било је бинарна претрага, што захтева ассортед низ.
Не заборавите да је веома важно разматрање
када радите са бинарном претрагу.
То је предуслов да користи то-- Низ да гледате кроз
мора да се сортирају.
У супротном, кључна реч је завади па владај.
Поделите низ на пола и елиминисати половина елемената
сваки пут као што наставите кроз.
Због овог завади па владај и резачи ствари у пола приступу,
у најгорем случају време наводњавања бинарних претрага је
лог н, што је значајно боље од линеарног Сеарцх је н.
Време најбољи случај воде је и даље један.
>> Могли бисмо га одмах наћи Први пут правимо поделу, али,
Опет, запамтите да Мада се бинарне претраге је
знатно боље него линеарно потрази самим тим што лог н наспрам н,
можда ћете морати да прође кроз рад од прва сортирање своју низ, који
Можда би се мање ефикасна у зависности о величини итератинг сортирана.
>> Ја сам Доуг Ллоид, ово је ЦС50.