1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Taigi CS50 mes sužinojome apie
iš rūšiavimo ir paieškos įvairovė

3
00:00:08,900 --> 00:00:09,442
algoritmai.

4
00:00:09,442 --> 00:00:11,400
Ir kartais ji gali būti
šiek tiek sudėtinga išlaikyti

5
00:00:11,400 --> 00:00:14,161
stebėti, kas algoritmas ką daro.

6
00:00:14,161 --> 00:00:15,910
Mes tikrai tik
nugriebto paviršių taip pat,

7
00:00:15,910 --> 00:00:18,740
yra daug kitų paieška
ir rūšiavimo algoritmų.

8
00:00:18,740 --> 00:00:21,780
Taigi šio vaizdo tegul
tiesiog užtrukti keletą minučių

9
00:00:21,780 --> 00:00:24,980
išbandyti ir distiliuoti kiekvieną algoritmą
iki jos pagrindinių elementų

10
00:00:24,980 --> 00:00:27,810
todėl jūs galite prisiminti, labiausiai
Svarbi informacija apie juos

11
00:00:27,810 --> 00:00:31,970
ir gebėti formuluoti
skirtumai, jei reikia.

12
00:00:31,970 --> 00:00:34,220
>> Pirmasis pasirinkimas rūšiuoti.

13
00:00:34,220 --> 00:00:38,210
Pagrindinė idėja atrankos rūšiuoti
yra rasti mažiausią nerūšiuotas elementą

14
00:00:38,210 --> 00:00:42,890
masyve ir sukeisti su
Pirmasis nerūšiuotos elementas toje masyvo.

15
00:00:42,890 --> 00:00:46,620
Mes sakė, kad blogiausio atvejo
buvo n kvadratu paleisti laikas, kad.

16
00:00:46,620 --> 00:00:50,060
Ir jei norite atšaukti, kodėl imtis
Žvilgsnis atrankos rūšiavimo vaizdo.

17
00:00:50,060 --> 00:00:54,560
Geriausiu atveju vykdymo metu
taip pat n kvadrato.

18
00:00:54,560 --> 00:00:58,910
>> Burbulas rūšiuoti, už idėja, kad
viena yra apsikeitimo gretimų porų.

19
00:00:58,910 --> 00:01:01,730
Štai raktas, kuris padeda jums
prisiminti skirtumą čia.

20
00:01:01,730 --> 00:01:04,920
Atrankos Rūšiuoti tai yra, kiek,
rasti smallest-- burbulas

21
00:01:04,920 --> 00:01:06,790
Rūšiuoti yra apsikeitimo gretimų porų.

22
00:01:06,790 --> 00:01:08,710
Mes apsikeitimo gretimų porų
elementų, jeigu jie

23
00:01:08,710 --> 00:01:12,530
yra iš tam, kuris efektyviai
bubbles didesnius elementus į dešinę,

24
00:01:12,530 --> 00:01:17,060
ir tuo pačiu metu ji taip pat pradeda
judėti mažesnius elementus į kairę.

25
00:01:17,060 --> 00:01:20,180
Blogiausias atvejis atvejis vykdymo metu
burbuliukų rūšiuoti yra N kvadratu.

26
00:01:20,180 --> 00:01:23,476
Geriausiu atveju vykdymo metu
Bubble Rūšiuoti yra n.

27
00:01:23,476 --> 00:01:25,350
Kadangi tokioje situacijoje
mes neturime actually--

28
00:01:25,350 --> 00:01:27,141
mes galime nereikia
jokių apsikeitimo ne visiems.

29
00:01:27,141 --> 00:01:31,026
Mes tik turime padaryti vieną
perduoti visoms n elementų.

30
00:01:31,026 --> 00:01:34,600
>> Be įterpimo rūšiuoti, The
Pagrindinė idėja čia keičiasi.

31
00:01:34,600 --> 00:01:36,630
Štai dėl įterpimo rūšiuoti raktinį žodį.

32
00:01:36,630 --> 00:01:39,630
Mes ketiname dėti vieną kartą per
iš masyvo kairės į dešinę.

33
00:01:39,630 --> 00:01:41,670
Ir kaip mes darome, mes
ketina perkelti elementus

34
00:01:41,670 --> 00:01:46,260
mes jau matėme, kad paliktume
mažesni, kad reikia, kad tilptų kažkur

35
00:01:46,260 --> 00:01:48,080
atgal į tą surūšiuoti dalį.

36
00:01:48,080 --> 00:01:51,600
Taigi mes statome surūšiuoti masyvo vienas
elementas vienu metu, iš kairės į dešinę,

37
00:01:51,600 --> 00:01:54,740
ir mes pereiti dalykų padaryti kambarį.

38
00:01:54,740 --> 00:01:58,650
Blogiausias atvejis paleisti laikas
įterpimo Rūšiuoti yra N kvadratu.

39
00:01:58,650 --> 00:02:02,380
Geriausiu atveju paleisti laikas yra n.

40
00:02:02,380 --> 00:02:05,380
>> Sujungti sort-- raktažodį
Čia yra padalyti ir sujungti.

41
00:02:05,380 --> 00:02:08,949
Mes padalinti visą masyvą, ar
tai šešis elementus, aštuoni elementai,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- mes padalinti ją
žemyn per pusę, per pusę, per pusę,

43
00:02:13,790 --> 00:02:17,720
kol mes turime pagal masyvo
n vieno elemento matricos.

44
00:02:17,720 --> 00:02:19,470
A n vieno elemento masyvų rinkinys.

45
00:02:19,470 --> 00:02:22,640
Taigi mes pradėjome su vienu
1000-elementas masyvas,

46
00:02:22,640 --> 00:02:26,550
ir mes gauti iki taško, kur mes
turi 1000 vieno elemento masyvus.

47
00:02:26,550 --> 00:02:30,990
Tada mes pradedame sujungti tuos sub masyvai
atgal kartu teisinga tvarka.

48
00:02:30,990 --> 00:02:34,860
Taigi mes dvi vieno elemento masyvai
ir sukurti dviejų elementų masyvas.

49
00:02:34,860 --> 00:02:38,180
Mes du dviejų elementų masyvai
ir sukurti keturių elementų masyvas

50
00:02:38,180 --> 00:02:43,900
ir taip toliau ir taip toliau, kol mes
vėl atstatyta vieną n elementų masyvas.

51
00:02:43,900 --> 00:02:48,410
>> Blogiausias atvejis paleisti laikas
sujungti rūšiuoti yra n kartų log n.

52
00:02:48,410 --> 00:02:52,390
Mes turime n elementų, tačiau
tai apsauginio apvalkalo procesas

53
00:02:52,390 --> 00:02:56,960
priima log n žingsniai gauti
atgal į visu masyvo.

54
00:02:56,960 --> 00:03:01,160
Geriausiu atveju paleisti laiką taip pat n Prisijungti
n, nes šis procesas tikrai ne

55
00:03:01,160 --> 00:03:04,090
nesvarbu, ar masyvas buvo
rūšiuojamos ar ne pradėti.

56
00:03:04,090 --> 00:03:07,590
Šis procesas yra tas pats, ten
jokiu būdu trumpo jungimo dalykų.

57
00:03:07,590 --> 00:03:11,610
Taigi n log n, blogiausiu atveju,
N log N geriausiu atveju.

58
00:03:11,610 --> 00:03:13,960
>> Mes kalbėjome apie dviejų
ieškoti algoritmai.

59
00:03:13,960 --> 00:03:16,230
Taigi linijinis paieška yra apie Iteracja.

60
00:03:16,230 --> 00:03:19,500
Mes toliau visoje masyvo
vieną kartą, iš kairės į dešinę,

61
00:03:19,500 --> 00:03:21,950
bando surasti skaičių
kad mes ieškome.

62
00:03:21,950 --> 00:03:24,550
Blogiausias atvejis paleisti laikas yra didelis O n.

63
00:03:24,550 --> 00:03:27,610
Tai gali užtrukti mus Iteracja
visoje kiekvieno elemento

64
00:03:27,610 --> 00:03:30,660
rasti elementą Mes ieškome
už, arba paskutinėje vietoje,

65
00:03:30,660 --> 00:03:31,630
arba ne visi.

66
00:03:31,630 --> 00:03:34,720
Bet mes negalime patvirtinti, kad iki
mes pažvelgė viskas.

67
00:03:34,720 --> 00:03:36,730
M geriausiu atveju, mes iš karto.

68
00:03:36,730 --> 00:03:41,060
Geriausiu atveju paleisti laikas
linijinis paieška omega 1 d.

69
00:03:41,060 --> 00:03:43,689
>> Galiausiai, buvo dvejetainis paieškos,
kuris reikalauja asorti masyvo.

70
00:03:43,689 --> 00:03:45,605
Atminkite, kad tai labai
svarbu atsižvelgti

71
00:03:45,605 --> 00:03:47,155
Dirbdami su dvejetainiu paiešką.

72
00:03:47,155 --> 00:03:50,180
Tai būtina sąlyga siekiant naudojant it--
masyvo, kad jūs ieškote per

73
00:03:50,180 --> 00:03:52,160
turi būti rūšiuojami.

74
00:03:52,160 --> 00:03:54,500
Priešingu atveju, raktinis žodis
yra skaldyk ir valdyk.

75
00:03:54,500 --> 00:03:58,310
Splitas masyvo į pusę ir
pašalinti pusė elementų

76
00:03:58,310 --> 00:04:00,780
kiekvieną kartą, kaip jums pereiti per.

77
00:04:00,780 --> 00:04:04,330
Dėl šios Skaldyk ir valdyk
ir trupinimo dalykų pusę požiūrio,

78
00:04:04,330 --> 00:04:07,450
blogiausiu atveju vykdymo metu
dvejetainiai paieška

79
00:04:07,450 --> 00:04:11,730
log n, kuris yra iš esmės
geriau nei Linijinio Paieška anketa n.

80
00:04:11,730 --> 00:04:13,570
Geriausiu atveju vykdymo metu yra ir dar vienas.

81
00:04:13,570 --> 00:04:17,010
>> Mes galime rasti jį nedelsiant
Pirmą kartą mes dalybą, bet

82
00:04:17,010 --> 00:04:19,339
vėl prisiminti, kad
nors dvejetainis paieška

83
00:04:19,339 --> 00:04:24,030
iš esmės geriau nei tiesinės paieškos
pagal būties žurnalas n palyginti n,

84
00:04:24,030 --> 00:04:27,110
jums gali tekti eiti per darbo
rūšiavimo jūsų masyvo pirmas, kuris

85
00:04:27,110 --> 00:04:32,010
gali padaryti jį mažiau veiksmingas, priklausomai nuo
ant Iteracja surūšiuoti dydžio.

86
00:04:32,010 --> 00:04:35,250
>> Aš Doug Lloyd, tai CS50.

87
00:04:35,250 --> 00:04:36,757