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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Takže CS50 sme sa dozvedeli o
rôzne triedenie a vyhľadávanie

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

4
00:00:09,442 --> 00:00:11,400
A niekedy to môže byť
trochu zložitejšie udržať

5
00:00:11,400 --> 00:00:14,161
sledovať, čo robí, čo algoritmus.

6
00:00:14,161 --> 00:00:15,910
Máme naozaj len
sušeného povrchu príliš,

7
00:00:15,910 --> 00:00:18,740
existuje mnoho ďalších vyhľadávanie
a triedenie algoritmy.

8
00:00:18,740 --> 00:00:21,780
Takže v tomto videu poďme
len trvať niekoľko minút

9
00:00:21,780 --> 00:00:24,980
vyskúšať a destilovať každý algoritmus
až na jeho kľúčové prvky

10
00:00:24,980 --> 00:00:27,810
takže si môžete pamätať najviac
dôležité informácie o nich

11
00:00:27,810 --> 00:00:31,970
a byť schopný formulovať
rozdiely, pokiaľ je to nutné.

12
00:00:31,970 --> 00:00:34,220
>> Prvý z nich je výber triediť.

13
00:00:34,220 --> 00:00:38,210
Základnou myšlienkou výberom Triediť
je nájsť najmenší netriedeného prvok

14
00:00:38,210 --> 00:00:42,890
v poli a vymeniť ich s
Prvý netriedený prvok tejto matice.

15
00:00:42,890 --> 00:00:46,620
Povedali sme, že najhorší prípad
bežať doba, ktorá bola n na druhú.

16
00:00:46,620 --> 00:00:50,060
A ak si chcete pripomenúť, prečo, prijať
Pozrite sa na výber triedenie videu.

17
00:00:50,060 --> 00:00:54,560
Najlepšie-case run time
je tiež n na druhú.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, myšlienka, že
jeden je swap priľahlých párov.

19
00:00:58,910 --> 00:01:01,730
Tak to je kľúč, ktorý vám pomôže
spomenúť na rozdiel tu.

20
00:01:01,730 --> 00:01:04,920
Výberom Triediť ich, tak ďaleko,
nájsť smallest-- bublinu

21
00:01:04,920 --> 00:01:06,790
Triedenie je swap priľahlých párov.

22
00:01:06,790 --> 00:01:08,710
My swap priľahlých párov
prvkov v prípade, že

23
00:01:08,710 --> 00:01:12,530
sú mimo prevádzky, ktorý účinne
bubliny väčší prvky na pravej strane,

24
00:01:12,530 --> 00:01:17,060
a súčasne tiež začne
pre pohyb menších prvkov na ľavej strane.

25
00:01:17,060 --> 00:01:20,180
Najhorší prípad run time
bublinkové druhu je n na druhú.

26
00:01:20,180 --> 00:01:23,476
Najlepšie-case run time
Bubble sort je n.

27
00:01:23,476 --> 00:01:25,350
Pretože v tejto situácii
nemáme actually--

28
00:01:25,350 --> 00:01:27,141
by sme mohli nie je potreba
žiadne swapy vôbec.

29
00:01:27,141 --> 00:01:31,026
Máme len urobiť jednu
prejsť cez všetky n prvkov.

30
00:01:31,026 --> 00:01:34,600
>> V vloženie radenie,
Základnou myšlienkou je tu mení.

31
00:01:34,600 --> 00:01:36,630
To je kľúčové slovo pre vkladanie druhu.

32
00:01:36,630 --> 00:01:39,630
Budeme krok raz prostredníctvom
poľa zľava doprava.

33
00:01:39,630 --> 00:01:41,670
A ako my, my sme
sa k posunu prvkov

34
00:01:41,670 --> 00:01:46,260
sme už videli, aby sa priestor pre
tie menšie, ktoré potrebujú, aby sa zmestili niekde

35
00:01:46,260 --> 00:01:48,080
späť v tomto zoradené časti.

36
00:01:48,080 --> 00:01:51,600
Takže sme budovať zoradené poľa jedného
prvok v čase, zľava doprava,

37
00:01:51,600 --> 00:01:54,740
a posunieme veci, aby miestnosť.

38
00:01:54,740 --> 00:01:58,650
Najhoršie run time of
insertion sort je n na druhú.

39
00:01:58,650 --> 00:02:02,380
Najlepšie-case spustiť n.

40
00:02:02,380 --> 00:02:05,380
>> Zlúčiť sort-- kľúčové slovo
Tu je rozdeliť a zlúčiť.

41
00:02:05,380 --> 00:02:08,949
Rozdelili sme celé palety, či
to je šesť prvkov, osem elementov,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- sme to rozdeliť
dole o polovicu, na polovicu, na polovicu,

43
00:02:13,790 --> 00:02:17,720
kým nebudeme mať v poli
n jedného prvku poľa.

44
00:02:17,720 --> 00:02:19,470
Sada n jedného prvku poľa.

45
00:02:19,470 --> 00:02:22,640
Tak sme začali s jedným
1000-prvok poľa,

46
00:02:22,640 --> 00:02:26,550
a dostaneme do bodu, keď sme
majú 1000 jeden prvok poľa.

47
00:02:26,550 --> 00:02:30,990
Potom sme začali zlúčiť tieto čiastkové polia
dohromady v správnom poradí.

48
00:02:30,990 --> 00:02:34,860
Takže zoberieme dva jedného prvku poľa
a vytvoriť dve prvok poľa.

49
00:02:34,860 --> 00:02:38,180
Berieme dva dva-prvkov poľa
a vytvoriť štyri prvok poľa

50
00:02:38,180 --> 00:02:43,900
a tak ďalej, a tak ďalej, až kým máme
prestavaná jeden n prvku poľa.

51
00:02:43,900 --> 00:02:48,410
>> Najhoršie run time of
merge sort znamená n-krát log n.

52
00:02:48,410 --> 00:02:52,390
Máme n elementy, ale
tento proces rekombinantným

53
00:02:52,390 --> 00:02:56,960
berie log n kroky na získanie
späť na plnú pole.

54
00:02:56,960 --> 00:03:01,160
Najlepšie prípad behu je tiež n log
n preto, že tento proces nie je naozaj

55
00:03:01,160 --> 00:03:04,090
jedno, či bol pole
radené alebo nie začať.

56
00:03:04,090 --> 00:03:07,590
Tento proces je rovnaký, je tu
žiadny spôsob, ako skratu veci.

57
00:03:07,590 --> 00:03:11,610
Takže n log n v najhoršom prípade,
n log n v najlepšom prípade.

58
00:03:11,610 --> 00:03:13,960
>> Hovorili sme o dva
vyhľadávanie algoritmy.

59
00:03:13,960 --> 00:03:16,230
Takže lineárne hľadanie je o iterácie.

60
00:03:16,230 --> 00:03:19,500
Pokračujeme cez pole
Raz, zľava doprava,

61
00:03:19,500 --> 00:03:21,950
sa snaží nájsť číslo
že hľadáme.

62
00:03:21,950 --> 00:03:24,550
Najhoršie behu je veľký O n.

63
00:03:24,550 --> 00:03:27,610
To môže trvať nás iterácie
po každej jednotlivé súčasti

64
00:03:27,610 --> 00:03:30,660
nájsť prvok, čo hľadáme
pre, a to buď na poslednej pozícii,

65
00:03:30,660 --> 00:03:31,630
alebo vôbec nie.

66
00:03:31,630 --> 00:03:34,720
Ale nemôžeme potvrdiť, že kým
Pozerali sme sa na všetko.

67
00:03:34,720 --> 00:03:36,730
m najlepšie-prípad, nájdeme hneď.

68
00:03:36,730 --> 00:03:41,060
Najlepšie-case beh čas
lineárne vyhľadávanie je omegou 1.

69
00:03:41,060 --> 00:03:43,689
>> Napokon, bolo binárne vyhľadávanie,
ktorá vyžaduje rozmanité polia.

70
00:03:43,689 --> 00:03:45,605
Pamätajte si, že je to veľmi
dôležitým aspektom

71
00:03:45,605 --> 00:03:47,155
Pri práci s binárne vyhľadávanie.

72
00:03:47,155 --> 00:03:50,180
To je nevyhnutným predpokladom na používanie to--
pole, ktoré hľadáte skrz

73
00:03:50,180 --> 00:03:52,160
musí byť radené.

74
00:03:52,160 --> 00:03:54,500
V opačnom prípade kľúčové slovo
je rozdeľ a panuj.

75
00:03:54,500 --> 00:03:58,310
Rozdeľte pole do polovice a
eliminovať polovica z prvkov

76
00:03:58,310 --> 00:04:00,780
zakaždým, keď, ako budete postupovať cez.

77
00:04:00,780 --> 00:04:04,330
Kvôli tejto rozdeľ a panuj
a štiepanie veci v polovici prístupe,

78
00:04:04,330 --> 00:04:07,450
najhorší prípad run time
binárnych vyhľadávanie

79
00:04:07,450 --> 00:04:11,730
log n, ktorá je v podstate
lepšie ako lineárny hľadania v n.

80
00:04:11,730 --> 00:04:13,570
Najlepšie-case behu je ešte jeden.

81
00:04:13,570 --> 00:04:17,010
>> Mohli by sme ju okamžite nájsť
Prvýkrát robíme divíziu, ale,

82
00:04:17,010 --> 00:04:19,339
Znovu si uvedomte, že
aj keď je binárny vyhľadávanie

83
00:04:19,339 --> 00:04:24,030
podstatne lepší ako lineárny hľadanie
z dôvodu, že log n oproti n,

84
00:04:24,030 --> 00:04:27,110
možno budete musieť ísť cez prácu
triedenie svoje pole ako prvý, čo

85
00:04:27,110 --> 00:04:32,010
by mohol robiť to menej efektívne v závislosti
o veľkosti iterácie zoradené.

86
00:04:32,010 --> 00:04:35,250
>> Som Doug Lloyd, je to CS50.

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