>> Doug LLOYD: Taigi CS50 mes sužinojome apie iš rūšiavimo ir paieškos įvairovė
algoritmai.
Ir kartais ji gali būti šiek tiek sudėtinga išlaikyti
stebėti, kas algoritmas ką daro.
Mes tikrai tik nugriebto paviršių taip pat,
yra daug kitų paieška ir rūšiavimo algoritmų.
Taigi šio vaizdo tegul tiesiog užtrukti keletą minučių
išbandyti ir distiliuoti kiekvieną algoritmą iki jos pagrindinių elementų
todėl jūs galite prisiminti, labiausiai Svarbi informacija apie juos
ir gebėti formuluoti skirtumai, jei reikia.
>> Pirmasis pasirinkimas rūšiuoti.
Pagrindinė idėja atrankos rūšiuoti yra rasti mažiausią nerūšiuotas elementą
masyve ir sukeisti su Pirmasis nerūšiuotos elementas toje masyvo.
Mes sakė, kad blogiausio atvejo buvo n kvadratu paleisti laikas, kad.
Ir jei norite atšaukti, kodėl imtis Žvilgsnis atrankos rūšiavimo vaizdo.
Geriausiu atveju vykdymo metu taip pat n kvadrato.
>> Burbulas rūšiuoti, už idėja, kad viena yra apsikeitimo gretimų porų.
Štai raktas, kuris padeda jums prisiminti skirtumą čia.
Atrankos Rūšiuoti tai yra, kiek, rasti smallest-- burbulas
Rūšiuoti yra apsikeitimo gretimų porų.
Mes apsikeitimo gretimų porų elementų, jeigu jie
yra iš tam, kuris efektyviai bubbles didesnius elementus į dešinę,
ir tuo pačiu metu ji taip pat pradeda judėti mažesnius elementus į kairę.
Blogiausias atvejis atvejis vykdymo metu burbuliukų rūšiuoti yra N kvadratu.
Geriausiu atveju vykdymo metu Bubble Rūšiuoti yra n.
Kadangi tokioje situacijoje mes neturime actually--
mes galime nereikia jokių apsikeitimo ne visiems.
Mes tik turime padaryti vieną perduoti visoms n elementų.
>> Be įterpimo rūšiuoti, The Pagrindinė idėja čia keičiasi.
Štai dėl įterpimo rūšiuoti raktinį žodį.
Mes ketiname dėti vieną kartą per iš masyvo kairės į dešinę.
Ir kaip mes darome, mes ketina perkelti elementus
mes jau matėme, kad paliktume mažesni, kad reikia, kad tilptų kažkur
atgal į tą surūšiuoti dalį.
Taigi mes statome surūšiuoti masyvo vienas elementas vienu metu, iš kairės į dešinę,
ir mes pereiti dalykų padaryti kambarį.
Blogiausias atvejis paleisti laikas įterpimo Rūšiuoti yra N kvadratu.
Geriausiu atveju paleisti laikas yra n.
>> Sujungti sort-- raktažodį Čia yra padalyti ir sujungti.
Mes padalinti visą masyvą, ar tai šešis elementus, aštuoni elementai,
10000 elements-- mes padalinti ją žemyn per pusę, per pusę, per pusę,
kol mes turime pagal masyvo n vieno elemento matricos.
A n vieno elemento masyvų rinkinys.
Taigi mes pradėjome su vienu 1000-elementas masyvas,
ir mes gauti iki taško, kur mes turi 1000 vieno elemento masyvus.
Tada mes pradedame sujungti tuos sub masyvai atgal kartu teisinga tvarka.
Taigi mes dvi vieno elemento masyvai ir sukurti dviejų elementų masyvas.
Mes du dviejų elementų masyvai ir sukurti keturių elementų masyvas
ir taip toliau ir taip toliau, kol mes vėl atstatyta vieną n elementų masyvas.
>> Blogiausias atvejis paleisti laikas sujungti rūšiuoti yra n kartų log n.
Mes turime n elementų, tačiau tai apsauginio apvalkalo procesas
priima log n žingsniai gauti atgal į visu masyvo.
Geriausiu atveju paleisti laiką taip pat n Prisijungti n, nes šis procesas tikrai ne
nesvarbu, ar masyvas buvo rūšiuojamos ar ne pradėti.
Šis procesas yra tas pats, ten jokiu būdu trumpo jungimo dalykų.
Taigi n log n, blogiausiu atveju, N log N geriausiu atveju.
>> Mes kalbėjome apie dviejų ieškoti algoritmai.
Taigi linijinis paieška yra apie Iteracja.
Mes toliau visoje masyvo vieną kartą, iš kairės į dešinę,
bando surasti skaičių kad mes ieškome.
Blogiausias atvejis paleisti laikas yra didelis O n.
Tai gali užtrukti mus Iteracja visoje kiekvieno elemento
rasti elementą Mes ieškome už, arba paskutinėje vietoje,
arba ne visi.
Bet mes negalime patvirtinti, kad iki mes pažvelgė viskas.
M geriausiu atveju, mes iš karto.
Geriausiu atveju paleisti laikas linijinis paieška omega 1 d.
>> Galiausiai, buvo dvejetainis paieškos, kuris reikalauja asorti masyvo.
Atminkite, kad tai labai svarbu atsižvelgti
Dirbdami su dvejetainiu paiešką.
Tai būtina sąlyga siekiant naudojant it-- masyvo, kad jūs ieškote per
turi būti rūšiuojami.
Priešingu atveju, raktinis žodis yra skaldyk ir valdyk.
Splitas masyvo į pusę ir pašalinti pusė elementų
kiekvieną kartą, kaip jums pereiti per.
Dėl šios Skaldyk ir valdyk ir trupinimo dalykų pusę požiūrio,
blogiausiu atveju vykdymo metu dvejetainiai paieška
log n, kuris yra iš esmės geriau nei Linijinio Paieška anketa n.
Geriausiu atveju vykdymo metu yra ir dar vienas.
>> Mes galime rasti jį nedelsiant Pirmą kartą mes dalybą, bet
vėl prisiminti, kad nors dvejetainis paieška
iš esmės geriau nei tiesinės paieškos pagal būties žurnalas n palyginti n,
jums gali tekti eiti per darbo rūšiavimo jūsų masyvo pirmas, kuris
gali padaryti jį mažiau veiksmingas, priklausomai nuo ant Iteracja surūšiuoti dydžio.
>> Aš Doug Lloyd, tai CS50.