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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Tehát CS50 tanultunk
a különböző válogatás és keresés

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

4
00:00:09,442 --> 00:00:11,400
És néha lehet
egy kicsit trükkös tartani

5
00:00:11,400 --> 00:00:14,161
követni, hogy mi algoritmus mit csinál.

6
00:00:14,161 --> 00:00:15,910
Már tényleg csak
sovány a felület túl,

7
00:00:15,910 --> 00:00:18,740
sok más keresés
és rendezési algoritmusok.

8
00:00:18,740 --> 00:00:21,780
Szóval ez a videó nézzük
Csak egy pár percre

9
00:00:21,780 --> 00:00:24,980
hogy megpróbálja distill egyes algoritmus
le központi elemének,

10
00:00:24,980 --> 00:00:27,810
így emlékszik a leginkább
Fontos információkat róluk

11
00:00:27,810 --> 00:00:31,970
és képes legyen megfogalmazni a
különbségek, ha szükséges.

12
00:00:31,970 --> 00:00:34,220
>> Az első szelekció egyfajta.

13
00:00:34,220 --> 00:00:38,210
Az alapgondolata kiválasztási sorrend
találnunk a legkisebb szétválogatott elem

14
00:00:38,210 --> 00:00:42,890
egy tömbben, és cserélni azt a
első válogatás nélkül eleme a tömb.

15
00:00:42,890 --> 00:00:46,620
Azt mondta, hogy a legrosszabb
futási ideje, amit n négyzeten.

16
00:00:46,620 --> 00:00:50,060
És ha azt szeretnénk felidézni, miért, hogy
Egy pillantás a kiválasztási sorrend videót.

17
00:00:50,060 --> 00:00:54,560
A legjobb esetben futási idő
is n faragva.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, az ötlet mögött, hogy
az egyik az, hogy a csere szomszédos pár.

19
00:00:58,910 --> 00:01:01,730
Szóval ez a kulcs, amely segít
emlékszik itt a különbség.

20
00:01:01,730 --> 00:01:04,920
Válogatás a sort, eddig
megtalálni a smallest-- buborék

21
00:01:04,920 --> 00:01:06,790
rendezés swap szomszédos párokat.

22
00:01:06,790 --> 00:01:08,710
Mi swap szomszédos párok
elemek, ha azok

23
00:01:08,710 --> 00:01:12,530
elfogyott a rend, amely hatékonyan
buborékok nagyobb elemeket, hogy a jobb,

24
00:01:12,530 --> 00:01:17,060
és ugyanakkor azt is megkezdődik
mozgatni kisebb elemeket a bal oldalon.

25
00:01:17,060 --> 00:01:20,180
A legrosszabb esetben futási idő
buborék rendezés n faragva.

26
00:01:20,180 --> 00:01:23,476
A legjobb esetben futási idő
buborék rendezés n.

27
00:01:23,476 --> 00:01:25,350
Mivel ebben a helyzetben
mi nem actually--

28
00:01:25,350 --> 00:01:27,141
talán nem kell
semmilyen csereügyletek egyáltalán.

29
00:01:27,141 --> 00:01:31,026
Már csak, hogy egy
át az összes n elemű.

30
00:01:31,026 --> 00:01:34,600
>> Beszúrási sort, a
alapötlet itt tolódik.

31
00:01:34,600 --> 00:01:36,630
Ez a kulcsszó behelyezhető sort.

32
00:01:36,630 --> 00:01:39,630
Fogunk lépéssel egyszer át
a tömb balról jobbra.

33
00:01:39,630 --> 00:01:41,670
És, mint mi vagyunk,
fog váltani elemek

34
00:01:41,670 --> 00:01:46,260
már láttuk, hogy helyet adjon
kisebb, hogy kell, hogy illeszkedjen valahol

35
00:01:46,260 --> 00:01:48,080
vissza, hogy válogatni része.

36
00:01:48,080 --> 00:01:51,600
Így építünk rendezett tömbben egy
eleme egy időben, balról jobbra,

37
00:01:51,600 --> 00:01:54,740
és mi váltás dolgokat, hogy legyen hely.

38
00:01:54,740 --> 00:01:58,650
A legrosszabb futási ideje
behelyezés rendezés n faragva.

39
00:01:58,650 --> 00:02:02,380
A legjobb esetben futási ideje n.

40
00:02:02,380 --> 00:02:05,380
>> Merge sort-- a kulcsszó
Itt van osztva, és egyesíti.

41
00:02:05,380 --> 00:02:08,949
Mi osztott a teljes tömb, hogy
ez hat elem, nyolc elem,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- mi osztott meg
a felére, felére, felére,

43
00:02:13,790 --> 00:02:17,720
amíg van értelmében tömb
n egyik eleme tömbök.

44
00:02:17,720 --> 00:02:19,470
Egy sor n az egyik eleme tömbök.

45
00:02:19,470 --> 00:02:22,640
Így kezdődött az egyik
1000 tömböt,

46
00:02:22,640 --> 00:02:26,550
és mi kap az a pont, ahol
hogy 1000 egyelemû tömbök.

47
00:02:26,550 --> 00:02:30,990
Aztán elkezdik egyesíteni azokat a sub tömbök
Újra együtt a megfelelő sorrendben.

48
00:02:30,990 --> 00:02:34,860
Tehát, hogy két egyelemű tömböt
és hozzon létre egy kételemű tömb.

49
00:02:34,860 --> 00:02:38,180
Vesszük két kételemű tömb
és hozzon létre egy négy részből álló tömb

50
00:02:38,180 --> 00:02:43,900
és így tovább, és így tovább, amíg meg nem
ismét átépítették egy n elem tömb.

51
00:02:43,900 --> 00:02:48,410
>> A legrosszabb futási ideje
merge sort n-szerese log n.

52
00:02:48,410 --> 00:02:52,390
Van n elemek, de
ez a rekombináció folyamatának

53
00:02:52,390 --> 00:02:56,960
tudomásul log n kap
vissza a teljes tömb.

54
00:02:56,960 --> 00:03:01,160
A legjobb esetben üzemidejét is n log
n, mert ez a folyamat nem igazán

55
00:03:01,160 --> 00:03:04,090
érdekel, hogy a tömb volt
válogatni, vagy sem kezdeni.

56
00:03:04,090 --> 00:03:07,590
A folyamat ugyanaz, van
nem lehet zárlat a dolgokat.

57
00:03:07,590 --> 00:03:11,610
Tehát n log n a legrosszabb esetben,
n log n a legjobb esetben.

58
00:03:11,610 --> 00:03:13,960
>> Beszéltünk két
keresőalgoritmust.

59
00:03:13,960 --> 00:03:16,230
Tehát lineáris keresés szól iterációjával.

60
00:03:16,230 --> 00:03:19,500
Mi jár az egész tömb
Egyszer, balról jobbra,

61
00:03:19,500 --> 00:03:21,950
megpróbálja megtalálni száma
hogy keresünk.

62
00:03:21,950 --> 00:03:24,550
A legrosszabb futási ideje nagy O n.

63
00:03:24,550 --> 00:03:27,610
Lehet, hogy minket ismételve
szerte minden elemét

64
00:03:27,610 --> 00:03:30,660
megtalálni az elem keresünk
A, vagy az utolsó pozícióban,

65
00:03:30,660 --> 00:03:31,630
vagy egyáltalán nem.

66
00:03:31,630 --> 00:03:34,720
De nem tudjuk megerősíteni, hogy amíg
átnéztük mindent.

67
00:03:34,720 --> 00:03:36,730
vagyok a legjobb, a találunk azonnal.

68
00:03:36,730 --> 00:03:41,060
A legjobb esetben futási ideje
lineáris keresés omegája 1.

69
00:03:41,060 --> 00:03:43,689
>> Végül ott volt a bináris keresés,
amely előírja válogatott tömb.

70
00:03:43,689 --> 00:03:45,605
Ne feledje, hogy ez egy nagyon
Fontos szempont

71
00:03:45,605 --> 00:03:47,155
ha dolgozik, bináris keresés.

72
00:03:47,155 --> 00:03:50,180
Ez előfeltétele annak, hogy a it--
A tömb, amit keres keresztül

73
00:03:50,180 --> 00:03:52,160
kell válogatni.

74
00:03:52,160 --> 00:03:54,500
Ellenkező esetben a kulcsszó
ez Oszd meg és uralkodj.

75
00:03:54,500 --> 00:03:58,310
Osztott a tömb a felét és
megszüntesse a fele az elemek

76
00:03:58,310 --> 00:04:00,780
minden alkalommal, ahogy halad előre.

77
00:04:00,780 --> 00:04:04,330
Emiatt Oszd meg és uralkodj
és felosztása a dolgok fele megközelítést,

78
00:04:04,330 --> 00:04:07,450
A legrosszabb futási idő
A bináris keresés

79
00:04:07,450 --> 00:04:11,730
log n, amely lényegében
jobb, mint a lineáris keresés a n.

80
00:04:11,730 --> 00:04:13,570
A legjobb esetben futásidő még mindig az egyik.

81
00:04:13,570 --> 00:04:17,010
>> Lehet, hogy rögtön megtalálta a
először teszünk egy részlege, de,

82
00:04:17,010 --> 00:04:19,339
Újra, ne feledje, hogy
bár bináris keresés

83
00:04:19,339 --> 00:04:24,030
lényegesen jobb, mint a lineáris keresés
annak révén, hogy log n versus n,

84
00:04:24,030 --> 00:04:27,110
lehet, hogy menjen át a munkát
A válogatás a tömb első, amely

85
00:04:27,110 --> 00:04:32,010
Lehet, hogy kevésbé hatékony függően
A méret a iterációjával rendezve.

86
00:04:32,010 --> 00:04:35,250
>> Én Doug Lloyd, ez CS50.

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