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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Deci, în CS50 am aflat despre
o varietate de sortare și căutare

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

4
00:00:09,442 --> 00:00:11,400
Și, uneori, poate fi
un pic cam complicat pentru a menține

5
00:00:11,400 --> 00:00:14,161
evidența a ceea ce algoritm ce face.

6
00:00:14,161 --> 00:00:15,910
Avem într-adevăr numai
degresat suprafața le

7
00:00:15,910 --> 00:00:18,740
Există multe alte cautare
și sortare algoritmi.

8
00:00:18,740 --> 00:00:21,780
Deci, în acest film să
doar să ia câteva minute

9
00:00:21,780 --> 00:00:24,980
pentru a încerca și distila fiecare algoritm
până la elementele sale de bază

10
00:00:24,980 --> 00:00:27,810
astfel încât să puteți aminti cel mai mult
informații importante despre ele

11
00:00:27,810 --> 00:00:31,970
și să fie capabil de a articula
diferențe, dacă este necesar.

12
00:00:31,970 --> 00:00:34,220
>> Primul este de selectare fel.

13
00:00:34,220 --> 00:00:38,210
Ideea de bază de selecție fel
este găsi cel mai mic element nesortat

14
00:00:38,210 --> 00:00:42,890
într-o matrice și schimb cu
prim element nesortate din matrice.

15
00:00:42,890 --> 00:00:46,620
Am spus că cel mai rău caz
timp a alerga de care a fost n pătrat.

16
00:00:46,620 --> 00:00:50,060
Și dacă vrei să amintim de ce, ia
o privire la video de selecție de sortare.

17
00:00:50,060 --> 00:00:54,560
Timpul de functionare mai bun caz
este, de asemenea, n pătrat.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, ideea din spatele care
unul este de a schimba perechile adiacente.

19
00:00:58,910 --> 00:01:01,730
Deci, asta e cheia care vă ajută
amintiți-vă diferența aici.

20
00:01:01,730 --> 00:01:04,920
Selecție fel este, până în prezent,
găsi bubble smallest--

21
00:01:04,920 --> 00:01:06,790
fel de swap este de perechi adiacente.

22
00:01:06,790 --> 00:01:08,710
Am schimba perechi adiacente
de elemente în cazul în care

23
00:01:08,710 --> 00:01:12,530
sunt în afara de ordine, care în mod eficient
bule elemente mai mari la dreapta,

24
00:01:12,530 --> 00:01:17,060
și, în același timp, începe de asemenea
a muta elementele mici spre stânga.

25
00:01:17,060 --> 00:01:20,180
Timpul de caz run cel mai rău caz
de bule fel este n pătrat.

26
00:01:20,180 --> 00:01:23,476
Timpul de functionare mai bun caz
de bule fel este n.

27
00:01:23,476 --> 00:01:25,350
Pentru că în această situație
noi nu actually--

28
00:01:25,350 --> 00:01:27,141
nu poate fi necesar să
face orice swap-uri, la toate.

29
00:01:27,141 --> 00:01:31,026
Trebuie doar pentru a face o
treci peste toate elementele N.

30
00:01:31,026 --> 00:01:34,600
>> În sortare prin inserție, The
idee de bază aici este schimbarea.

31
00:01:34,600 --> 00:01:36,630
Asta e cuvântul cheie pentru introducerea fel.

32
00:01:36,630 --> 00:01:39,630
Vom pas dată prin
matrice de la stânga la dreapta.

33
00:01:39,630 --> 00:01:41,670
Și cum facem, suntem
va schimba elemente

34
00:01:41,670 --> 00:01:46,260
am văzut deja pentru a face loc
cele mai mici care au nevoie de a se potrivi undeva

35
00:01:46,260 --> 00:01:48,080
înapoi în acea parte sortate.

36
00:01:48,080 --> 00:01:51,600
Așa că am construi matrice sortate unul
element de la un moment dat, la stânga la dreapta,

37
00:01:51,600 --> 00:01:54,740
și trecem lucruri pentru a face loc.

38
00:01:54,740 --> 00:01:58,650
Timpul de functionare cel mai rău caz de
sortare prin inserție este n pătrat.

39
00:01:58,650 --> 00:02:02,380
Timpul cel mai bun caz a alerga este n.

40
00:02:02,380 --> 00:02:05,380
>> Merge sort-- cuvântul cheie
aici este împărțit și îmbinare.

41
00:02:05,380 --> 00:02:08,949
Ne-am despartit matrice complet, dacă
e șase elemente, opt elemente,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- am împărțit
jos cu jumătate, la jumătate, la jumătate,

43
00:02:13,790 --> 00:02:17,720
până când vom avea în gamă
de n unul matrice de elemente.

44
00:02:17,720 --> 00:02:19,470
Un set de n o matrice de elemente.

45
00:02:19,470 --> 00:02:22,640
Așa că am început cu o
Matrice de 1.000 elemente,

46
00:02:22,640 --> 00:02:26,550
si ajungem la punctul în care ne-am
au 1.000 de matrice-un element.

47
00:02:26,550 --> 00:02:30,990
Apoi vom începe să fuzioneze aceste sub matrice
din nou împreună în ordinea corectă.

48
00:02:30,990 --> 00:02:34,860
Deci, vom lua două rețele-un element
și de a crea o gamă de două elemente.

49
00:02:34,860 --> 00:02:38,180
Luăm două matrici cu elemente de doi
și de a crea o gamă de patru elemente

50
00:02:38,180 --> 00:02:43,900
și așa mai departe și așa mai departe, până când ne-am
din nou reconstruit o matrice n elemente.

51
00:02:43,900 --> 00:02:48,410
>> Timpul de functionare cel mai rău caz de
merge sort este de n ori log n.

52
00:02:48,410 --> 00:02:52,390
Avem n elemente, dar
acest proces recombinarea

53
00:02:52,390 --> 00:02:56,960
ia log n pasi pentru a obține
înapoi la o gamă completă.

54
00:02:56,960 --> 00:03:01,160
Cel mai bun caz de timp a alerga, de asemenea, n log
n pentru că acest proces nu prea

55
00:03:01,160 --> 00:03:04,090
de îngrijire dacă matrice a fost
sortate sau nu pentru a începe cu.

56
00:03:04,090 --> 00:03:07,590
Procesul este la fel, nu e
nici o modalitate de a lucruri scurtcircuit.

57
00:03:07,590 --> 00:03:11,610
Deci n log n în cel mai rău caz,
n log n în cel mai bun caz.

58
00:03:11,610 --> 00:03:13,960
>> Am vorbit despre doi
căutare algoritmi.

59
00:03:13,960 --> 00:03:16,230
Deci căutare liniară este de aproximativ iterarea.

60
00:03:16,230 --> 00:03:19,500
Vom proceda în întreaga matrice
o dată, de la stânga la dreapta,

61
00:03:19,500 --> 00:03:21,950
încercarea de a găsi numărul
pe care le căutați.

62
00:03:21,950 --> 00:03:24,550
Timpul cel mai rău caz rula este O mare de n.

63
00:03:24,550 --> 00:03:27,610
Aceasta ne-ar putea lua iterarea
peste fiecare singur element

64
00:03:27,610 --> 00:03:30,660
pentru a găsi elementul căutăm
pentru, fie în ultima poziție,

65
00:03:30,660 --> 00:03:31,630
sau deloc.

66
00:03:31,630 --> 00:03:34,720
Dar nu putem confirma că până
ne-am uitat la tot.

67
00:03:34,720 --> 00:03:36,730
m cel mai bun-caz, găsim imediat.

68
00:03:36,730 --> 00:03:41,060
Timpul de functionare cel mai bun caz de
căutare liniară este omega 1.

69
00:03:41,060 --> 00:03:43,689
>> În cele din urmă, nu a fost de căutare binară,
care necesită matrice asortate.

70
00:03:43,689 --> 00:03:45,605
Amintiți-vă că este un foarte
element important

71
00:03:45,605 --> 00:03:47,155
atunci când se lucrează cu căutare binară.

72
00:03:47,155 --> 00:03:50,180
Este o condiție de a utiliza it--
matrice pe care o căutați prin

73
00:03:50,180 --> 00:03:52,160
trebuie să fie sortate.

74
00:03:52,160 --> 00:03:54,500
În caz contrar, cuvântul cheie
este divide și cuceri.

75
00:03:54,500 --> 00:03:58,310
Împărțit matrice în jumătatea și
elimina jumătate din elementele

76
00:03:58,310 --> 00:04:00,780
de fiecare dată așa cum ați proceda prin.

77
00:04:00,780 --> 00:04:04,330
Datorită acestui decalaj și cucerire
și lucruri de despicare în jumătate de abordare,

78
00:04:04,330 --> 00:04:07,450
timpul de functionare cel mai rău caz
de căutare binare este

79
00:04:07,450 --> 00:04:11,730
log n, care este în mod substanțial
mai bine decât n căutare liniar.

80
00:04:11,730 --> 00:04:13,570
Timpul cel mai bun caz a alerga este încă una.

81
00:04:13,570 --> 00:04:17,010
>> S-ar putea găsi imediat
prima dată am face o divizare, dar,

82
00:04:17,010 --> 00:04:19,339
din nou, amintiți-vă că
deși căutare binară este

83
00:04:19,339 --> 00:04:24,030
substanțial mai bine decât căutarea liniară
în virtutea faptului că log n față n,

84
00:04:24,030 --> 00:04:27,110
ar putea să aibă de a merge prin munca
de sortare matrice întâi, care

85
00:04:27,110 --> 00:04:32,010
s-ar putea face mai puțin eficient, în funcție
pe dimensiunea iterating sortate.

86
00:04:32,010 --> 00:04:35,250
>> Sunt Doug Lloyd, aceasta este CS50.

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