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

2
00:00:05,760 --> 00:00:08,900
>> DOUG Lloyd: Pra, në CS50 kemi mësuar për
një shumëllojshmëri të klasifikim dhe kërkim

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

4
00:00:09,442 --> 00:00:11,400
Dhe nganjëherë kjo mund të jetë
pak e ndërlikuar për të mbajtur

5
00:00:11,400 --> 00:00:14,161
gjurmët e asaj që algorithm bën çfarë.

6
00:00:14,161 --> 00:00:15,910
Ne kemi me të vërtetë vetëm
skremuar sipërfaqen shumë,

7
00:00:15,910 --> 00:00:18,740
ka shumë të tjera kërkim
dhe klasifikim algoritme.

8
00:00:18,740 --> 00:00:21,780
Pra, në këtë video, le të
të marrë vetëm disa minuta

9
00:00:21,780 --> 00:00:24,980
të përpiqen dhe të gjej çdo algorithm
deri në elementet e saj themelore

10
00:00:24,980 --> 00:00:27,810
kështu që ju mund të mbani mend më shumë
informacione të rëndësishme rreth tyre

11
00:00:27,810 --> 00:00:31,970
dhe të jenë në gjendje të artikulojnë
dallimet, nëse është e nevojshme.

12
00:00:31,970 --> 00:00:34,220
>> E para është zgjedhja lloj.

13
00:00:34,220 --> 00:00:38,210
Ideja themelore prapa përzgjedhjes lloj
është gjetur elementin më të vogël Unsorted

14
00:00:38,210 --> 00:00:42,890
në një grup dhe të bie në ujdi atë me
Elementi i parë unsorted e atij grup.

15
00:00:42,890 --> 00:00:46,620
Kemi thënë se më e keqja, rasti
kohë të drejtuar nga që ishte katror n.

16
00:00:46,620 --> 00:00:50,060
Dhe në qoftë se ju doni të kujtojnë pse, të marrë
Një vështrim në video përzgjedhjes renditjes.

17
00:00:50,060 --> 00:00:54,560
Më të mirë-Rasti kohë të drejtuar
është gjithashtu katror n.

18
00:00:54,560 --> 00:00:58,910
>> Lloj flluskë, ideja që
një është që të bie në ujdi çifte ngjitur.

19
00:00:58,910 --> 00:01:01,730
Pra, kjo është çelësi që ju ndihmon
mos harroni dallimin këtu.

20
00:01:01,730 --> 00:01:04,920
Përzgjedhja lloj është, deri tani,
gjeni flluskë smallest--

21
00:01:04,920 --> 00:01:06,790
lloji është shkëmbim palë ngjitur.

22
00:01:06,790 --> 00:01:08,710
Ne swap palë ngjitur
e elementeve në qoftë se ata

23
00:01:08,710 --> 00:01:12,530
janë jashtë funksionit, e cila në mënyrë efektive
bubbles elemente më të mëdha në të djathtë,

24
00:01:12,530 --> 00:01:17,060
dhe në të njëjtën kohë ajo gjithashtu fillon
për të lëvizur elementet më të vogla në të majtë.

25
00:01:17,060 --> 00:01:20,180
Më e keqja-Rasti kohë drejtuar rasti
i flluskë lloji është katror n.

26
00:01:20,180 --> 00:01:23,476
Më të mirë-Rasti kohë të drejtuar
i flluskë lloj është n.

27
00:01:23,476 --> 00:01:25,350
Sepse në këtë situatë
ne nuk actually--

28
00:01:25,350 --> 00:01:27,141
ne nuk mund të kenë nevojë për të
bëjë ndonjë këmbime në të gjitha.

29
00:01:27,141 --> 00:01:31,026
Ne vetëm duhet të bëjë një
kalojnë nëpër të gjitha elementet n.

30
00:01:31,026 --> 00:01:34,600
>> Në futje lloj, The
Ideja themelore këtu është zhvendosur.

31
00:01:34,600 --> 00:01:36,630
Kjo është fjalen për futje lloj.

32
00:01:36,630 --> 00:01:39,630
Ne jemi duke shkuar për të rritur një herë përmes
array nga e majta në të djathtë.

33
00:01:39,630 --> 00:01:41,670
Dhe si ne të bëjmë, ne jemi
do të zhvendoset elementet

34
00:01:41,670 --> 00:01:46,260
ne kemi parë tashmë për të bërë vend për
ato më të vogla që duhet të përshtaten diku

35
00:01:46,260 --> 00:01:48,080
përsëri në atë pjesë renditura.

36
00:01:48,080 --> 00:01:51,600
Kështu që ne ndërtojmë array renditura një
element në një kohë, majta në të djathtë,

37
00:01:51,600 --> 00:01:54,740
dhe ne ndryshim gjëra për të bërë dhomë.

38
00:01:54,740 --> 00:01:58,650
Më e keqja-Rasti kohë të drejtuar nga
futje lloj është katror n.

39
00:01:58,650 --> 00:02:02,380
Më të mirë-Rasti drejtuar kohë është n.

40
00:02:02,380 --> 00:02:05,380
>> Merge sort-- fjalen
këtu është e ndarë dhe të shkrihej.

41
00:02:05,380 --> 00:02:08,949
Ne të ndarë koleksion të plotë, nëse
është gjashtë elemente, tetë elemente,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- ne ndarë atë
poshtë nga gjysma, përgjysmë, përgjysmë,

43
00:02:13,790 --> 00:02:17,720
derisa të kemi nën grup
e n një vargjeve element.

44
00:02:17,720 --> 00:02:19,470
Një grup i n një vargjeve element.

45
00:02:19,470 --> 00:02:22,640
Pra, kemi filluar me një
1000-element array,

46
00:02:22,640 --> 00:02:26,550
dhe ne të merrni në pikën ku ne
kanë 1.000 vargjeve një element.

47
00:02:26,550 --> 00:02:30,990
Atëherë ne fillojmë të bashkojë këto vargjeve nën
përsëri së bashku në mënyrë korrekte.

48
00:02:30,990 --> 00:02:34,860
Pra, ne marrim dy vargjeve një element
dhe për të krijuar një grup të dy element.

49
00:02:34,860 --> 00:02:38,180
Ne kemi marrë dy vargjeve dy-element
dhe për të krijuar një grup të katër element

50
00:02:38,180 --> 00:02:43,900
dhe kështu me radhë e kështu me radhë derisa ne kemi
përsëri rindërtuar një koleksion element n.

51
00:02:43,900 --> 00:02:48,410
>> Më e keqja-Rasti kohë të drejtuar nga
bashkojë lloj N herë log n.

52
00:02:48,410 --> 00:02:52,390
Ne kemi elemente n, por
ky proces recombining

53
00:02:52,390 --> 00:02:56,960
merr log n hapa për të marrë
mbështetur në një koleksion të plotë.

54
00:02:56,960 --> 00:03:01,160
Rasti më i mirë drejtuar kohë është edhe log n
n për shkak se ky proces nuk ka të vërtetë

55
00:03:01,160 --> 00:03:04,090
intereson nëse array ishte
renditura apo jo për të filluar me.

56
00:03:04,090 --> 00:03:07,590
Procesi është i njëjtë, nuk ka
asnjë mënyrë për gjëra qark të shkurtër.

57
00:03:07,590 --> 00:03:11,610
Pra, n log n në rastin më të keq,
n log n në rastin më të mirë.

58
00:03:11,610 --> 00:03:13,960
>> Ne folëm për dy
kërkim algoritme.

59
00:03:13,960 --> 00:03:16,230
Pra Kërkimi linear është rreth iterating.

60
00:03:16,230 --> 00:03:19,500
Ne të vazhdojë nëpër rrjet
një herë, nga e majta në të djathtë,

61
00:03:19,500 --> 00:03:21,950
duke u përpjekur për të gjetur numrin
se ne jemi duke kërkuar për të.

62
00:03:21,950 --> 00:03:24,550
Më e keqja-Rasti drejtuar kohë është O e madhe e n.

63
00:03:24,550 --> 00:03:27,610
Ajo mund të na iterating
nëpër çdo element të vetme

64
00:03:27,610 --> 00:03:30,660
për të gjetur elementin ne jemi duke kërkuar
për, ose në pozitën e fundit,

65
00:03:30,660 --> 00:03:31,630
ose aspak.

66
00:03:31,630 --> 00:03:34,720
Por ne nuk mund të konfirmojë se deri
ne kemi shikuar në çdo gjë.

67
00:03:34,720 --> 00:03:36,730
m të mirë-rasti, ne gjejmë menjëherë.

68
00:03:36,730 --> 00:03:41,060
Më të mirë-Rasti kohë të drejtuar nga
Kërkimi linear është omega e 1.

69
00:03:41,060 --> 00:03:43,689
>> Së fundi, ka pasur kërko binar,
e cila kërkon array ndryshme.

70
00:03:43,689 --> 00:03:45,605
Mos harroni se është një shumë
konsideratë e rëndësishme

71
00:03:45,605 --> 00:03:47,155
kur punojnë me kërkimin binar.

72
00:03:47,155 --> 00:03:50,180
Është një parakusht për të përdorur it--
array që ju jeni në kërkim përmes

73
00:03:50,180 --> 00:03:52,160
duhet të ndahen.

74
00:03:52,160 --> 00:03:54,500
Përndryshe, fjalen
është Përça dhe sundo.

75
00:03:54,500 --> 00:03:58,310
Split array në gjysmë dhe
eliminuar gjysma e elementeve

76
00:03:58,310 --> 00:04:00,780
çdo herë si ju të vazhdojë përmes.

77
00:04:00,780 --> 00:04:04,330
Për shkak të kësaj përça dhe sundo
dhe ndarjen gjëra në gjysmën qasje,

78
00:04:04,330 --> 00:04:07,450
rastin më të keq koha kandidojë
i kërko binar është

79
00:04:07,450 --> 00:04:11,730
log n, e cila eshte substancialisht
më mirë se n kërkim linear së.

80
00:04:11,730 --> 00:04:13,570
Më të mirë-Rasti drejtuar kohë është ende një.

81
00:04:13,570 --> 00:04:17,010
>> Ne mund të gjeni atë menjëherë
hera e parë që ne kemi bërë një ndarje, por,

82
00:04:17,010 --> 00:04:19,339
përsëri, mos harroni se
megjithëse kërko binar është

83
00:04:19,339 --> 00:04:24,030
dukshëm më mirë se kërkim lineare
duke u mbështetur në të qenit log n kundrejt n,

84
00:04:24,030 --> 00:04:27,110
ju mund të keni për të shkuar nëpërmjet punës
i sorting rrjet tuaj të parë, e cila

85
00:04:27,110 --> 00:04:32,010
mund të bëjë atë më pak efektive në varësi
në madhësinë e iterating renditura.

86
00:04:32,010 --> 00:04:35,250
>> Unë jam Doug Lloyd, kjo është CS50.

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