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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Kaya sa CS50 natutunan namin tungkol sa
isang iba't ibang mga pag-uuri at paghahanap

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

4
00:00:09,442 --> 00:00:11,400
At minsan ay maaari itong maging
isang maliit na manlilinlang upang panatilihin

5
00:00:11,400 --> 00:00:14,161
subaybayan kung ano ang algorithm ang ano.

6
00:00:14,161 --> 00:00:15,910
Na namin talagang lamang
sinagap na masyadong sa ibabaw,

7
00:00:15,910 --> 00:00:18,740
mayroon ding iba't ibang mga paghahanap
at pag-uuri algorithm.

8
00:00:18,740 --> 00:00:21,780
Kaya sa video na ito ay hahayaan
tumagal lamang ng ilang minuto

9
00:00:21,780 --> 00:00:24,980
upang subukan at distill bawat algorithm
pababa sa core elemento nito

10
00:00:24,980 --> 00:00:27,810
upang maaari mong tandaan ang pinaka
mahalagang impormasyon tungkol sa kanila

11
00:00:27,810 --> 00:00:31,970
at ma-nakapagsasalita ang
pagkakaiba, kung kinakailangan.

12
00:00:31,970 --> 00:00:34,220
>> Ang una ay ang uri ng pagpili.

13
00:00:34,220 --> 00:00:38,210
Ang pangunahing ideya sa likod ng pagpili ng uri
ay hanapin ang pinakamaliit unsorted elemento

14
00:00:38,210 --> 00:00:42,890
sa isang array at magpalitan ng mga ito gamit ang
unang unsorted elemento ng array na.

15
00:00:42,890 --> 00:00:46,620
Sabi namin na ang pinakamasama-case
magpatakbo ng oras na iyon ay n nakalapat.

16
00:00:46,620 --> 00:00:50,060
At kung gusto mong isipin kung bakit, tumagal
isang tumingin sa pagpili ng uri ng video.

17
00:00:50,060 --> 00:00:54,560
Ang pinakamahusay na-case na tumakbo ng oras
ay din n nakalapat.

18
00:00:54,560 --> 00:00:58,910
>> Bubble-uuri, ang ideya sa likod na
ang isa ay upang magpalitan ng katabi pares.

19
00:00:58,910 --> 00:01:01,730
Kaya iyon ang key na tumutulong sa iyo
tandaan ang mga pagkakaiba dito.

20
00:01:01,730 --> 00:01:04,920
Pinili uri ay, sa ngayon,
hanapin ang smallest-- bubble

21
00:01:04,920 --> 00:01:06,790
uri ay magpalitan ng mga katabi pares.

22
00:01:06,790 --> 00:01:08,710
Swap namin katabi ng mga pares
ng mga elemento kung sila

23
00:01:08,710 --> 00:01:12,530
ay sira, na epektibong
bula ng mas malaking elemento sa kanan,

24
00:01:12,530 --> 00:01:17,060
at sa parehong oras din ito ay nagsisimula
upang ilipat ang mas maliit na mga elemento sa kaliwa.

25
00:01:17,060 --> 00:01:20,180
Ang pinakamasama-case time kaso run
ng bubble sort ay n nakalapat.

26
00:01:20,180 --> 00:01:23,476
Ang pinakamahusay na-case na tumakbo ng oras
ng bubble sort ay n.

27
00:01:23,476 --> 00:01:25,350
Dahil sa na sitwasyon
hindi namin actually--

28
00:01:25,350 --> 00:01:27,141
Maaaring hindi namin kailangan upang
gumawa ng anumang mga swaps sa lahat.

29
00:01:27,141 --> 00:01:31,026
Kami lamang magkaroon upang gumawa ng isa
pumasa sa lahat ng mga elemento n.

30
00:01:31,026 --> 00:01:34,600
>> In-uuri, ang
pangunahing ideya dito ay nagbabago.

31
00:01:34,600 --> 00:01:36,630
Iyan ang keyword para sa uri pagpapasok.

32
00:01:36,630 --> 00:01:39,630
Kami ay pagpunta sa hakbang beses sa pamamagitan ng
array mula kaliwa papuntang kanan.

33
00:01:39,630 --> 00:01:41,670
At tulad ng ginagawa namin, hindi namin
pagpunta sa shift elemento

34
00:01:41,670 --> 00:01:46,260
na namin nakita para gumawa nang lugar para sa
mas maliit na mga na kailangan upang umangkop sa tabi-tabi

35
00:01:46,260 --> 00:01:48,080
bumalik sa na pinagsunod-sunod sa bahaging ito.

36
00:01:48,080 --> 00:01:51,600
Kaya bumuo kami ang pinagsunod-sunod array isa
sangkap sa isang panahon, sa kaliwa papunta sa kanan,

37
00:01:51,600 --> 00:01:54,740
at shift namin ang mga bagay na gumawa ng room.

38
00:01:54,740 --> 00:01:58,650
Ang pinakamasama-case tumakbo ang oras ng
uri pagpapasok ay n nakalapat.

39
00:01:58,650 --> 00:02:02,380
Ang pinakamahusay na-case magpatakbo ng oras ay n.

40
00:02:02,380 --> 00:02:05,380
>> Sumanib sort-- keyword
dito ay nahati at sumanib.

41
00:02:05,380 --> 00:02:08,949
Hatiin namin ang buong array, kung
ito ay anim na mga sangkap, walong elemento,

42
00:02:08,949 --> 00:02:13,790
10,000 elements-- hatiin namin ito
down sa pamamagitan ng kalahati, sa pamamagitan ng kalahati, sa pamamagitan ng kalahati,

43
00:02:13,790 --> 00:02:17,720
hanggang kami ay may sa ilalim ng array
ng n isa array elemento.

44
00:02:17,720 --> 00:02:19,470
Isang set ng n isa array elemento.

45
00:02:19,470 --> 00:02:22,640
Kaya namin na nagsimula sa isa
1000-element array,

46
00:02:22,640 --> 00:02:26,550
at makuha namin sa punto kung saan kami ay
Mayroon 1,000 array one-element.

47
00:02:26,550 --> 00:02:30,990
Pagkatapos namin simulan upang sumanib sa mga sub arrays
likod magkasama sa tamang order.

48
00:02:30,990 --> 00:02:34,860
Kaya naming gawin dalawang array one-element
at lumikha ng isang array two-element.

49
00:02:34,860 --> 00:02:38,180
Kumuha kami ng dalawang array two-element
at lumikha ng isang array four-element

50
00:02:38,180 --> 00:02:43,900
at iba pa at iba pa hanggang hindi namin
muli itinayong muli isa n element ng array.

51
00:02:43,900 --> 00:02:48,410
>> Ang pinakamasama-case tumakbo ang oras ng
sumanib-uuri ay n beses log n.

52
00:02:48,410 --> 00:02:52,390
Mayroon kaming n elemento, ngunit
ang proseso na ito recombining

53
00:02:52,390 --> 00:02:56,960
tumatagal log n hakbang upang makakuha ng
i-back sa isang buong array.

54
00:02:56,960 --> 00:03:01,160
Ang pinakamahusay na kaso magpatakbo ng oras ay din n log
n dahil ang proseso na ito ay hindi tunay

55
00:03:01,160 --> 00:03:04,090
pag-aalaga kung ang array ay
inayos o hindi na magsimula sa.

56
00:03:04,090 --> 00:03:07,590
Ang proseso ay ang parehong, mayroong
walang paraan upang short circuit ng mga bagay.

57
00:03:07,590 --> 00:03:11,610
Kaya n log n sa pinakamasama kaso,
n log n sa pinakamahusay na kaso.

58
00:03:11,610 --> 00:03:13,960
>> Usapan natin ang tungkol sa dalawang
naghahanap algorithm.

59
00:03:13,960 --> 00:03:16,230
Kaya linear paghahanap ay tungkol iterating.

60
00:03:16,230 --> 00:03:19,500
Magpatuloy namin sa buong array
sabay, mula kaliwa papuntang kanan,

61
00:03:19,500 --> 00:03:21,950
sinusubukan mong mahanap ang numero
na kami ay naghahanap para sa.

62
00:03:21,950 --> 00:03:24,550
Ang oras na patakbuhin pinakamasama-case ay malaking O ng n.

63
00:03:24,550 --> 00:03:27,610
Ito ay maaaring tumagal sa amin iterating
sa kabuuan ng bawat solong elemento

64
00:03:27,610 --> 00:03:30,660
upang mahanap ang elemento kaming naghahanap
para sa, alinman sa huling posisyon,

65
00:03:30,660 --> 00:03:31,630
o hindi sa lahat.

66
00:03:31,630 --> 00:03:34,720
Ngunit hindi pa namin makumpirma na hanggang
kami ay tumingin sa lahat ng bagay.

67
00:03:34,720 --> 00:03:36,730
m ang pinakamahusay na-case, nakita namin agad.

68
00:03:36,730 --> 00:03:41,060
Ang pinakamahusay na-case tumakbo ang oras ng
linear paghahanap ay wakas ng 1.

69
00:03:41,060 --> 00:03:43,689
>> Sa wakas, nagkaroon binary paghahanap,
na kung saan ay nangangailangan ng iba't-ibang mga array.

70
00:03:43,689 --> 00:03:45,605
Tandaan na ang isang tunay
mahalagang pagsasaalang-alang

71
00:03:45,605 --> 00:03:47,155
kapag nagtatrabaho sa binary paghahanap.

72
00:03:47,155 --> 00:03:50,180
Ito ay isang paunang kinakailangan upang gamit it--
ang array na kayo ay naghahanap sa pamamagitan ng

73
00:03:50,180 --> 00:03:52,160
dapat na pinagsunod-sunod.

74
00:03:52,160 --> 00:03:54,500
Kung hindi man, ang keyword
ay hatiin at lupigin.

75
00:03:54,500 --> 00:03:58,310
Hatiin ang array sa kalahati at
puksain ang kalahati ng mga elemento

76
00:03:58,310 --> 00:04:00,780
sa bawat oras na ikaw ay magpatuloy sa pamamagitan ng.

77
00:04:00,780 --> 00:04:04,330
Dahil dito hatiin at lupigin
at paghahati ng mga bagay sa loob ng kalahating diskarte,

78
00:04:04,330 --> 00:04:07,450
ang pinakamasama-case na tumakbo ng oras
ng binary paghahanap ay

79
00:04:07,450 --> 00:04:11,730
mag-log n, na kung saan ay sa kalahatan
mas mahusay kaysa sa n linear paghahanap ni.

80
00:04:11,730 --> 00:04:13,570
Ang pinakamahusay na-case magpatakbo ng oras ay isa pa rin.

81
00:04:13,570 --> 00:04:17,010
>> Maaari naming agad ito ang makahanap
unang oras na gumawa kami ng isang dibisyon, ngunit,

82
00:04:17,010 --> 00:04:19,339
muli, tandaan na
bagaman binary paghahanap ay

83
00:04:19,339 --> 00:04:24,030
malaki mas mahusay kaysa sa haba ng paghahanap
sa pamamagitan ng kabutihan ng pagiging log n laban n,

84
00:04:24,030 --> 00:04:27,110
maaaring kailangan mong pumunta sa pamamagitan ng mga gawa
ng paghihiwalay muna ang iyong array, na kung saan

85
00:04:27,110 --> 00:04:32,010
ay maaaring gumawa ng hindi gaanong epektibong mga ito depende
sa laki ng iterating pinagsunod-sunod.

86
00:04:32,010 --> 00:04:35,250
>> Ako Doug Lloyd, ito ay CS50.

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