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

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Allura fil CS50 aħna tgħallmu dwar
varjetà ta 'għażla u tiftix

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

4
00:00:09,442 --> 00:00:11,400
U xi kultant jista 'jkun
ftit delikata biex iżommu

5
00:00:11,400 --> 00:00:14,161
rekord ta 'dak algoritmu ma dak.

6
00:00:14,161 --> 00:00:15,910
Imxejna verament biss
xkumat-wiċċ wisq,

7
00:00:15,910 --> 00:00:18,740
hemm tiftix oħra ħafna
u l-għażla algoritmi.

8
00:00:18,740 --> 00:00:21,780
Allura f'dan il-video ejja
ħu ftit minuti

9
00:00:21,780 --> 00:00:24,980
li tipprova jiddistillaw kull algoritmu
l isfel għall-elementi ewlenin tagħha

10
00:00:24,980 --> 00:00:27,810
sabiex inti tista 'tiftakar l-aktar
informazzjoni importanti dwarhom

11
00:00:27,810 --> 00:00:31,970
u jkunu kapaċi li tartikula l-
differenzi, jekk ikun hemm bżonn.

12
00:00:31,970 --> 00:00:34,220
>> L-ewwel huwa tip ta 'għażla.

13
00:00:34,220 --> 00:00:38,210
L-idea bażika wara sort għażla
hu li jinstabu l-iżgħar element mhux magħżul

14
00:00:38,210 --> 00:00:42,890
fil-firxa u tpartit ma 'l-
ewwel element mhux magħżul ta 'dak array.

15
00:00:42,890 --> 00:00:46,620
Aħna qal li l-agħar każ
ħin run ta 'li kien n kwadrat.

16
00:00:46,620 --> 00:00:50,060
U jekk inti tixtieq li tfakkar għaliex, jieħdu
Ħarsa lejn il-video tip għażla.

17
00:00:50,060 --> 00:00:54,560
L-aħjar każ run time
huwa wkoll n kwadrat.

18
00:00:54,560 --> 00:00:58,910
>> Sort Bubble, l-idea wara li
wieħed huwa li tpartit pari li jmissu magħhom.

19
00:00:58,910 --> 00:01:01,730
Allura dak l-ewlenin li jgħinek
ftakar id-differenza hawn.

20
00:01:01,730 --> 00:01:04,920
Għażla sort jiġifieri, s'issa,
isibu l-bużżieqa smallest--

21
00:01:04,920 --> 00:01:06,790
sort jiġifieri swap pari li jmissu magħhom.

22
00:01:06,790 --> 00:01:08,710
Aħna tpartit pari li jmissu magħhom
ta 'elementi jekk

23
00:01:08,710 --> 00:01:12,530
huma out of order, li effettivament
bżieżaq elementi akbar għad-dritt,

24
00:01:12,530 --> 00:01:17,060
u fl-istess ħin li jibda wkoll
li jiċċaqalqu elementi iżgħar lejn ix-xellug.

25
00:01:17,060 --> 00:01:20,180
L-agħar każ time każ jibqa 'jiddekorri
tal sort bużżieqa huwa n kwadrat.

26
00:01:20,180 --> 00:01:23,476
L-aħjar każ run time
ta 'bużżieqa tip huwa n.

27
00:01:23,476 --> 00:01:25,350
Minħabba f'dik is-sitwazzjoni
aħna ma actually--

28
00:01:25,350 --> 00:01:27,141
aħna ma jista 'jeħtieġ li
tagħmel xi swaps fil-livelli kollha.

29
00:01:27,141 --> 00:01:31,026
Aħna biss għandek tagħmel waħda
jgħaddu fl-elementi kollha n.

30
00:01:31,026 --> 00:01:34,600
>> Fil sort inserzjoni, il-
idea bażika hawnhekk qed tiċċaqlaq.

31
00:01:34,600 --> 00:01:36,630
Dik hija l-keyword għall tip inserzjoni.

32
00:01:36,630 --> 00:01:39,630
Aħna ser pass darba permezz
l-array mix-xellug għal-lemin.

33
00:01:39,630 --> 00:01:41,670
U kif nagħmlu, aħna qed
se ċċaqlaq elementi

34
00:01:41,670 --> 00:01:46,260
konna diġà raw biex tagħmel spazju għall
dawk iżgħar li jeħtieġ li jitwaħħal x'imkien

35
00:01:46,260 --> 00:01:48,080
lura b'dik il-porzjon magħżula.

36
00:01:48,080 --> 00:01:51,600
Allura aħna nibnu l-array Issortjat wieħed
element fi żmien, xellug għal-lemin,

37
00:01:51,600 --> 00:01:54,740
u aħna bidla affarijiet li jagħmlu kamra.

38
00:01:54,740 --> 00:01:58,650
L-agħar każ run time ta
sort inserzjoni huwa n kwadrat.

39
00:01:58,650 --> 00:02:02,380
L-aħjar każ run time huwa n.

40
00:02:02,380 --> 00:02:05,380
>> Jingħaqdu sort---keyword
hawn huwa maqsum u jingħaqdu.

41
00:02:05,380 --> 00:02:08,949
Aħna maqsuma l-firxa sħiħa, kemm jekk
huwa sitt elementi, tmien elementi,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- aħna qasmitha
stabbiliti bin-nofs, bin-nofs, bin-nofs,

43
00:02:13,790 --> 00:02:17,720
sakemm ikollna taħt firxa
tal arrays element n wieħed.

44
00:02:17,720 --> 00:02:19,470
Sett ta 'arrays element n wieħed.

45
00:02:19,470 --> 00:02:22,640
Allura bdejna ma 'wieħed
Firxa 1,000 element,

46
00:02:22,640 --> 00:02:26,550
u aħna jasal sal-punt fejn aħna
jkollhom 1,000 arrays one-element.

47
00:02:26,550 --> 00:02:30,990
Imbagħad aħna jibdew jingħaqdu f'dawk is arrays
lura flimkien fl-ordni korretta.

48
00:02:30,990 --> 00:02:34,860
Allura aħna jieħdu żewġ arrays one-element
u joħolqu firxa żewġ element.

49
00:02:34,860 --> 00:02:38,180
Nieħdu żewġ arrays two-element
u joħolqu firxa ta 'erba' element

50
00:02:38,180 --> 00:02:43,900
u hekk u hekk sakemm konna
għal darb'oħra inbniet wieħed array element n.

51
00:02:43,900 --> 00:02:48,410
>> L-agħar każ run time ta
jingħaqdu sort jiġifieri n żminijiet log n.

52
00:02:48,410 --> 00:02:52,390
Għandna elementi n, iżda
dan il-proċess jiżżewweġ

53
00:02:52,390 --> 00:02:56,960
jieħu log n-passi biex tikseb
lura għal firxa sħiħa.

54
00:02:56,960 --> 00:03:01,160
L-aħjar każ ħin run hija wkoll log n
n għaliex dan il-proċess ma verament

55
00:03:01,160 --> 00:03:04,090
kura jekk l-firxa kienet
magħżula jew le biex jibdew bihom.

56
00:03:04,090 --> 00:03:07,590
Il-proċess huwa l-istess, hemm
ebda mod biex l-affarijiet ċirkwit qasir.

57
00:03:07,590 --> 00:03:11,610
Allura n log n fl-agħar każ,
n log n fl-aħjar każ.

58
00:03:11,610 --> 00:03:13,960
>> Aħna tkellimna dwar żewġ
tiftix algoritmi.

59
00:03:13,960 --> 00:03:16,230
Allura tfittxija lineari hija ta 'madwar mtennija.

60
00:03:16,230 --> 00:03:19,500
Aħna tipproċedi madwar l-firxa
darba, mix-xellug għal-lemin,

61
00:03:19,500 --> 00:03:21,950
tipprova ssib l-għadd
li aħna qed tfittex.

62
00:03:21,950 --> 00:03:24,550
Il-ħin agħar każ run hija O kbir ta 'n.

63
00:03:24,550 --> 00:03:27,610
Jista 'jieħu us mtennija
madwar kull element wieħed

64
00:03:27,610 --> 00:03:30,660
biex isibu l-element aħna qed tfittex
għal, jew fl-aħħar pożizzjoni,

65
00:03:30,660 --> 00:03:31,630
jew xejn affattu.

66
00:03:31,630 --> 00:03:34,720
Iżda aħna ma tista 'tikkonferma li sakemm
konna ħares lejn kollox.

67
00:03:34,720 --> 00:03:36,730
m-aħjar każ, insibu immedjatament.

68
00:03:36,730 --> 00:03:41,060
L-aħjar każ run time ta
tfittxija lineari huwa omega-1 ta '.

69
00:03:41,060 --> 00:03:43,689
>> Fl-aħħar nett, kien hemm tfittxija binarju,
li teħtieġ firxa assortiti.

70
00:03:43,689 --> 00:03:45,605
Ftakar li l-ħafna
konsiderazzjoni importanti

71
00:03:45,605 --> 00:03:47,155
meta jaħdmu mal-tfittxija binarja.

72
00:03:47,155 --> 00:03:50,180
Huwa prerekwiżit għall-użu it--
l-array li qed tfittex permezz

73
00:03:50,180 --> 00:03:52,160
għandhom jiġu magħżula.

74
00:03:52,160 --> 00:03:54,500
Inkella, il-keyword
huwa qasma u conquer.

75
00:03:54,500 --> 00:03:58,310
Taqsam il-firxa fil nofs u
jelimina nofs mill-elementi

76
00:03:58,310 --> 00:04:00,780
kull darba kif inti tipproċedi permezz.

77
00:04:00,780 --> 00:04:04,330
Minħabba dan firda u conquer
u affarijiet qsim fil nofs approċċ,

78
00:04:04,330 --> 00:04:07,450
l-agħar każ run time
ta 'tfittxija binarja huwa

79
00:04:07,450 --> 00:04:11,730
log n, li hija sostanzjalment
aħjar minn n tfittxija lineari.

80
00:04:11,730 --> 00:04:13,570
L-aħjar każ run time għadu wieħed.

81
00:04:13,570 --> 00:04:17,010
>> Aħna jistgħu jsibuha immedjatament l-
ewwel darba nagħmlu diviżjoni, iżda,

82
00:04:17,010 --> 00:04:19,339
għal darb'oħra, ftakar li
għalkemm tfittxija binarja huwa

83
00:04:19,339 --> 00:04:24,030
sostanzjalment aħjar minn tfittxija lineari
minħabba li jkunu qegħdin log n versus n,

84
00:04:24,030 --> 00:04:27,110
inti jista 'jkollok tmur permezz tax-xogħol
tal issortjar array tiegħek ewwel, li

85
00:04:27,110 --> 00:04:32,010
jista 'jagħmilha inqas effettiv jiddependi
fuq id-daqs tal-mtennija magħżula.

86
00:04:32,010 --> 00:04:35,250
>> Jien Doug Lloyd, dan huwa CS50.

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