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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Takže CS50 jsme se dozvěděli o
různé třídění a vyhledávání

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

4
00:00:09,442 --> 00:00:11,400
A někdy to může být
trochu složitější udržet

5
00:00:11,400 --> 00:00:14,161
sledovat, co dělá, co algoritmus.

6
00:00:14,161 --> 00:00:15,910
Máme opravdu jen
sušeného povrchu příliš,

7
00:00:15,910 --> 00:00:18,740
existuje mnoho dalších vyhledávání
a třídění algoritmy.

8
00:00:18,740 --> 00:00:21,780
Takže v tomto videu pojďme
jen trvat několik minut

9
00:00:21,780 --> 00:00:24,980
vyzkoušet a destilovat každý algoritmus
až na jeho klíčové prvky

10
00:00:24,980 --> 00:00:27,810
takže si můžete pamatovat nejvíce
důležité informace o nich

11
00:00:27,810 --> 00:00:31,970
a být schopen formulovat
rozdíly, pokud je to nutné.

12
00:00:31,970 --> 00:00:34,220
>> První z nich je výběr třídit.

13
00:00:34,220 --> 00:00:38,210
Základní myšlenkou výběrem Třídit
je najít nejmenší netříděného prvek

14
00:00:38,210 --> 00:00:42,890
v poli a vyměnit je s
První netříděný prvek této matice.

15
00:00:42,890 --> 00:00:46,620
Řekli jsme, že nejhorší případ
běžet doba, která byla n na druhou.

16
00:00:46,620 --> 00:00:50,060
A pokud si chcete připomenout, proč, přijmout
Podívejte se na výběr třídění videu.

17
00:00:50,060 --> 00:00:54,560
Nejlepší-case run time
je také n na druhou.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, myšlenka, že
jeden je swap přilehlých párů.

19
00:00:58,910 --> 00:01:01,730
Tak to je klíč, který vám pomůže
vzpomenout na rozdíl zde.

20
00:01:01,730 --> 00:01:04,920
Výběrem Třídit je, tak daleko,
najít smallest-- bublinu

21
00:01:04,920 --> 00:01:06,790
Třídění je swap přilehlých párů.

22
00:01:06,790 --> 00:01:08,710
My swap přilehlých párů
prvků v případě, že

23
00:01:08,710 --> 00:01:12,530
jsou mimo provoz, který účinně
bubliny větší prvky na pravé straně,

24
00:01:12,530 --> 00:01:17,060
a současně také začne
pro pohyb menších prvků na levé straně.

25
00:01:17,060 --> 00:01:20,180
Nejhorší případ run time
bublinkové druhu je n na druhou.

26
00:01:20,180 --> 00:01:23,476
Nejlepší-case run time
Bubble sort je n.

27
00:01:23,476 --> 00:01:25,350
Protože v této situaci
nemáme actually--

28
00:01:25,350 --> 00:01:27,141
bychom mohli není potřeba
žádné swapy vůbec.

29
00:01:27,141 --> 00:01:31,026
Máme jen udělat jednu
projít přes všechny n prvků.

30
00:01:31,026 --> 00:01:34,600
>> V vložení řazení,
Základní myšlenkou je zde mění.

31
00:01:34,600 --> 00:01:36,630
To je klíčové slovo pro vkládání druhu.

32
00:01:36,630 --> 00:01:39,630
Budeme krok jednou prostřednictvím
pole zleva doprava.

33
00:01:39,630 --> 00:01:41,670
A jako my, my jsme
se k posunu prvků

34
00:01:41,670 --> 00:01:46,260
jsme již viděli, aby se prostor pro
ty menší, které potřebují, aby se vešly někde

35
00:01:46,260 --> 00:01:48,080
zpět v tomto seřazené části.

36
00:01:48,080 --> 00:01:51,600
Takže jsme budovat seřazené pole jednoho
prvek v době, zleva doprava,

37
00:01:51,600 --> 00:01:54,740
a posuneme věci, aby místnost.

38
00:01:54,740 --> 00:01:58,650
Nejhorší run time of
insertion sort je n na druhou.

39
00:01:58,650 --> 00:02:02,380
Nejlepší-case běhu n.

40
00:02:02,380 --> 00:02:05,380
>> Sloučit sort-- klíčové slovo
Zde je rozdělit a sloučit.

41
00:02:05,380 --> 00:02:08,949
Rozdělili jsme celé palety, zda
to je šest prvků, osm elementů,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- jsme to rozdělit
dolů o polovinu, na polovinu, na polovinu,

43
00:02:13,790 --> 00:02:17,720
dokud nebudeme mít v poli
n jednoho prvku pole.

44
00:02:17,720 --> 00:02:19,470
Sada n jednoho prvku pole.

45
00:02:19,470 --> 00:02:22,640
Tak jsme začali s jedním
1000-prvek pole,

46
00:02:22,640 --> 00:02:26,550
a dostaneme do bodu, kdy jsme
mají 1000 jeden prvek pole.

47
00:02:26,550 --> 00:02:30,990
Pak jsme začali sloučit tyto dílčí pole
dohromady ve správném pořadí.

48
00:02:30,990 --> 00:02:34,860
Takže vezmeme dva jednoho prvku pole
a vytvořit dvě prvek pole.

49
00:02:34,860 --> 00:02:38,180
Bereme dva dva-prvků pole
a vytvořit čtyři prvek pole

50
00:02:38,180 --> 00:02:43,900
a tak dále, a tak dále, dokud máme
přestavěna jeden n prvku pole.

51
00:02:43,900 --> 00:02:48,410
>> Nejhorší run time of
merge sort znamená n-krát log n.

52
00:02:48,410 --> 00:02:52,390
Máme n elementy, ale
tento proces rekombinantním

53
00:02:52,390 --> 00:02:56,960
bere log n kroky k získání
zpět na plnou pole.

54
00:02:56,960 --> 00:03:01,160
Nejlepší případ běhu je také n log
n proto, že tento proces není opravdu

55
00:03:01,160 --> 00:03:04,090
jedno, jestli byl pole
řazeny nebo ne začít.

56
00:03:04,090 --> 00:03:07,590
Tento proces je stejný, je tu
žádný způsob, jak zkratu věci.

57
00:03:07,590 --> 00:03:11,610
Takže n log n v nejhorším případě,
n log n v nejlepším případě.

58
00:03:11,610 --> 00:03:13,960
>> Mluvili jsme o dva
vyhledávání algoritmy.

59
00:03:13,960 --> 00:03:16,230
Takže lineární hledání je o iterace.

60
00:03:16,230 --> 00:03:19,500
Pokračujeme přes pole
Jednou, zleva doprava,

61
00:03:19,500 --> 00:03:21,950
se snaží najít číslo
že hledáme.

62
00:03:21,950 --> 00:03:24,550
Nejhorší běhu je velký O n.

63
00:03:24,550 --> 00:03:27,610
To může trvat nás iterace
po každé jednotlivé součásti

64
00:03:27,610 --> 00:03:30,660
najít prvek, co hledáme
pro, a to buď na poslední pozici,

65
00:03:30,660 --> 00:03:31,630
nebo vůbec ne.

66
00:03:31,630 --> 00:03:34,720
Ale nemůžeme potvrdit, že dokud
Dívali jsme se na všechno.

67
00:03:34,720 --> 00:03:36,730
m nejlepší-případ, najdeme hned.

68
00:03:36,730 --> 00:03:41,060
Nejlepší-case běh čas
lineární vyhledávání je omegou 1.

69
00:03:41,060 --> 00:03:43,689
>> A konečně, bylo binární vyhledávání,
která vyžaduje rozmanité pole.

70
00:03:43,689 --> 00:03:45,605
Pamatujte si, že je to velmi
důležitým aspektem

71
00:03:45,605 --> 00:03:47,155
Při práci s binární vyhledávání.

72
00:03:47,155 --> 00:03:50,180
To je nezbytným předpokladem k používání to--
pole, které hledáte skrz

73
00:03:50,180 --> 00:03:52,160
musí být řazeny.

74
00:03:52,160 --> 00:03:54,500
V opačném případě klíčové slovo
je rozděl a panuj.

75
00:03:54,500 --> 00:03:58,310
Rozdělte pole do poloviny a
eliminovat polovina z prvků

76
00:03:58,310 --> 00:04:00,780
pokaždé, když, jak budete postupovat přes.

77
00:04:00,780 --> 00:04:04,330
Kvůli této rozděl a panuj
a štípání věci v polovině přístupu,

78
00:04:04,330 --> 00:04:07,450
nejhorší případ run time
binárních vyhledávání

79
00:04:07,450 --> 00:04:11,730
log n, která je v podstatě
lepší než lineární hledání v n.

80
00:04:11,730 --> 00:04:13,570
Nejlepší-case běhu je ještě jeden.

81
00:04:13,570 --> 00:04:17,010
>> Mohli bychom ji okamžitě najít
Poprvé děláme divizi, ale,

82
00:04:17,010 --> 00:04:19,339
Znovu si uvědomte, že
i když je binární vyhledávání

83
00:04:19,339 --> 00:04:24,030
podstatně lepší než lineární hledání
z důvodu, že log n oproti n,

84
00:04:24,030 --> 00:04:27,110
možná budete muset jít přes práci
třídění své pole jako první, což

85
00:04:27,110 --> 00:04:32,010
by mohl dělat to méně efektivní v závislosti
o velikosti iterace seřazeny.

86
00:04:32,010 --> 00:04:35,250
>> Jsem Doug Lloyd, je to CS50.

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