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

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Tātad CS50 mēs uzzinājām
dažādas šķirošanas un meklēšanas

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

4
00:00:09,442 --> 00:00:11,400
Un dažreiz tas var būt
nedaudz grūts, lai saglabātu

5
00:00:11,400 --> 00:00:14,161
līdzi tam, ko algoritms ko dara.

6
00:00:14,161 --> 00:00:15,910
Mēs esam tiešām tikai
vājpiena virsmu pārāk,

7
00:00:15,910 --> 00:00:18,740
ir daudzi citi meklēšana
un šķirošanas algoritmu.

8
00:00:18,740 --> 00:00:21,780
Tātad šajā video pieņemsim
lietojiet tikai dažas minūtes

9
00:00:21,780 --> 00:00:24,980
mēģināt destilēt katru algoritmu
leju, lai tās galvenajiem elementiem

10
00:00:24,980 --> 00:00:27,810
lai jūs varētu atcerēties visvairāk
Svarīga informācija par tām

11
00:00:27,810 --> 00:00:31,970
un jāspēj formulēt
atšķirības, ja nepieciešams.

12
00:00:31,970 --> 00:00:34,220
>> Pirmais ir izvēle kārtošanas.

13
00:00:34,220 --> 00:00:38,210
Pamatideja atlases veida
ir atrast mazāko nešķirotas elements

14
00:00:38,210 --> 00:00:42,890
masīva un mijmaiņas to ar
Pirmais nešķiroti elements šī masīva.

15
00:00:42,890 --> 00:00:46,620
Mēs teicām, ka sliktākajā gadījumā
palaist laiks, kas bija n brusas.

16
00:00:46,620 --> 00:00:50,060
Un, ja jūs vēlaties, lai atcerēties, kāpēc ņemt
apskatīt atlase kārtošanas video.

17
00:00:50,060 --> 00:00:54,560
Labākā gadījuma darbības laiks
ir arī n brusas.

18
00:00:54,560 --> 00:00:58,910
>> Bubble kārtot, ideja, ka
viens ir mijmaiņas blakus pāriem.

19
00:00:58,910 --> 00:01:01,730
Tātad tas ir galvenais, kas palīdz jums
atcerēties atšķirību šeit.

20
00:01:01,730 --> 00:01:04,920
Atlases kārtošanas ir, līdz šim,
atrast smallest-- burbuli

21
00:01:04,920 --> 00:01:06,790
kārtošanas ir mijmaiņas blakus pāriem.

22
00:01:06,790 --> 00:01:08,710
Mēs mijmaiņas blakus pāriem
elementu, ja tie

23
00:01:08,710 --> 00:01:12,530
ir iziet no ierindas, kas efektīvi
burbuļi lielākus elementus tiesībām,

24
00:01:12,530 --> 00:01:17,060
un tajā pašā laikā, tā arī sākas
virzīties uz mazākiem elementiem kreisi.

25
00:01:17,060 --> 00:01:20,180
Sliktākajā-Case darbības laiks
burbuļiem veida ir n brusas.

26
00:01:20,180 --> 00:01:23,476
Labākā gadījuma darbības laiks
burbuļiem kārtošanas ir n.

27
00:01:23,476 --> 00:01:25,350
Jo šajā situācijā
mums nav actually--

28
00:01:25,350 --> 00:01:27,141
mēs, iespējams, nav nepieciešams
nekādas mijmaiņas darījumus vispār.

29
00:01:27,141 --> 00:01:31,026
Mums ir tikai veikt vienu
iet pāri visām n elementiem.

30
00:01:31,026 --> 00:01:34,600
>> In ievietošanas veida, tad
Pamatideja šeit mainās.

31
00:01:34,600 --> 00:01:36,630
Tas ir atslēgvārds ievietošanas veida.

32
00:01:36,630 --> 00:01:39,630
Mēs ejam soli vienreiz cauri
masīvs no kreisās puses uz labo.

33
00:01:39,630 --> 00:01:41,670
Un, kā mēs to darām, mēs esam
gatavojas novirzīt elementus

34
00:01:41,670 --> 00:01:46,260
mēs jau esam redzējuši, lai padarītu telpu
mazākie, kas nepieciešams, lai ietilptu kaut kur

35
00:01:46,260 --> 00:01:48,080
atpakaļ šajā sakārtoti porciju.

36
00:01:48,080 --> 00:01:51,600
Tātad mēs veidojam sakārtoti masīvs viens
elements laikā, no kreisās uz labo,

37
00:01:51,600 --> 00:01:54,740
un mēs novirzīt lietas, lai padarītu telpu.

38
00:01:54,740 --> 00:01:58,650
Sliktāko palaist laiks
ievietošanas kārtošanas ir n brusas.

39
00:01:58,650 --> 00:02:02,380
Vislabāk lieta palaist laiks n.

40
00:02:02,380 --> 00:02:05,380
>> Apvienot sort-- atslēgvārda
šeit ir sadalīt un apvienot.

41
00:02:05,380 --> 00:02:08,949
Mēs sadalīt pilnu klāstu, vai
tas ir seši elementi, astoņas elementus,

42
00:02:08,949 --> 00:02:13,790
10,000 elements-- mēs sadalīt to
leju uz pusi, uz pusi, uz pusi,

43
00:02:13,790 --> 00:02:17,720
kamēr mums ir zem masīva
no n viens elements masīvi.

44
00:02:17,720 --> 00:02:19,470
Kopums n viena elementa masīvi.

45
00:02:19,470 --> 00:02:22,640
Tā mēs sākām ar vienu
1000-elementu masīvs,

46
00:02:22,640 --> 00:02:26,550
un mēs nokļūt līdz vietai, kur mēs
ir 1000 viena elementu masīvu.

47
00:02:26,550 --> 00:02:30,990
Tad mēs sākam apvienot šos sub bloki
atpakaļ kopā pareizā secībā.

48
00:02:30,990 --> 00:02:34,860
Tātad mēs divas viena elementu masīvu
un radīt divu elementu masīvu.

49
00:02:34,860 --> 00:02:38,180
Ņemam divus divu elementu masīvu
un izveidot četru elementu masīvs

50
00:02:38,180 --> 00:02:43,900
un tā tālāk, un tā tālāk, kamēr mēs esam
vēlreiz pārbūvēta viena n elementu klāstu.

51
00:02:43,900 --> 00:02:48,410
>> Sliktāko palaist laiks
apvienot kārtošanas ir n reizes log n.

52
00:02:48,410 --> 00:02:52,390
Mums ir n elementi, bet
šis krustmijas process

53
00:02:52,390 --> 00:02:56,960
ņem log n soļi, lai saņemtu
atpakaļ uz pilnu masīvs.

54
00:02:56,960 --> 00:03:01,160
Labākā lieta palaist laiks ir arī n log
n jo šis process nav īsti

55
00:03:01,160 --> 00:03:04,090
vienalga, vai masīvs bija
sakārtoti vai ne, lai sāktu ar.

56
00:03:04,090 --> 00:03:07,590
Process ir tāds pats, tur ir
Nav veids, kā īsslēguma lietām.

57
00:03:07,590 --> 00:03:11,610
Tātad n log n sliktākajā gadījumā,
n log n labākajā gadījumā.

58
00:03:11,610 --> 00:03:13,960
>> Mēs runājām par divām
meklējot algoritmus.

59
00:03:13,960 --> 00:03:16,230
Tātad lineārā meklēšana ir par atkārtojot.

60
00:03:16,230 --> 00:03:19,500
Mēs turpināt visā masīvs
vienreiz, no kreisās uz labo pusi,

61
00:03:19,500 --> 00:03:21,950
mēģinot atrast numuru
ka mēs meklējam.

62
00:03:21,950 --> 00:03:24,550
Sliktāko palaist laiks ir liels O n.

63
00:03:24,550 --> 00:03:27,610
Tas var aizņemt mūs atkārtojot
pāri katru elementu

64
00:03:27,610 --> 00:03:30,660
lai atrastu elementu mēs meklējam
par, vai nu pēdējā pozīcijā,

65
00:03:30,660 --> 00:03:31,630
vai nav vispār.

66
00:03:31,630 --> 00:03:34,720
Bet mēs nevaram apstiprināt, ka līdz
mēs esam paskatījās viss.

67
00:03:34,720 --> 00:03:36,730
m vislabāk lietu, mēs atrast uzreiz.

68
00:03:36,730 --> 00:03:41,060
Vislabāk gadījums palaist laiks
lineārā meklēšana ir omega no 1.

69
00:03:41,060 --> 00:03:43,689
>> Visbeidzot, tur bija bināro meklēšanu,
kas prasa asorti masīvs.

70
00:03:43,689 --> 00:03:45,605
Atcerieties, ka ir ļoti
Svarīgs apsvērums

71
00:03:45,605 --> 00:03:47,155
strādājot ar bināro meklēšanu.

72
00:03:47,155 --> 00:03:50,180
Tas ir priekšnoteikums, lai, izmantojot it--
masīvs, ka jūs meklējat, izmantojot

73
00:03:50,180 --> 00:03:52,160
ir sakārtoti.

74
00:03:52,160 --> 00:03:54,500
Pretējā gadījumā atslēgvārds
ir skaldi un valdi.

75
00:03:54,500 --> 00:03:58,310
Sadalīt masīvs uz pusi un
likvidēt puse no elementiem

76
00:03:58,310 --> 00:04:00,780
Katru reizi, kā jūs turpināt cauri.

77
00:04:00,780 --> 00:04:04,330
Sakarā ar šo skaldi un valdi
un sadalīšanas lietas pusi pieeju,

78
00:04:04,330 --> 00:04:07,450
sliktākajā gadījuma darbības laiks
no binārā meklēšana ir

79
00:04:07,450 --> 00:04:11,730
log n, kas ir būtiski
labāk nekā lineārās meklēšana s n.

80
00:04:11,730 --> 00:04:13,570
Vislabāk lieta palaist laiks ir vēl viens.

81
00:04:13,570 --> 00:04:17,010
>> Mēs varētu atrast to nekavējoties
Pirmo reizi mēs sadalījumu, bet,

82
00:04:17,010 --> 00:04:19,339
atkal, atcerieties, ka
kaut arī binārā meklēšana ir

83
00:04:19,339 --> 00:04:24,030
ievērojami labāk nekā lineāri meklēšanu
pamatojoties uz to log n pret n,

84
00:04:24,030 --> 00:04:27,110
jums varētu būt, lai iet caur darbu
šķirošanas savu masīvs pirmais, kas

85
00:04:27,110 --> 00:04:32,010
varētu padarīt to mazāk efektīvu atkarībā
par lielumu atkārtojot sakārtoti.

86
00:04:32,010 --> 00:04:35,250
>> Es esmu Doug Lloyd, tas ir CS50.

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