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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Quindi, in CS50 abbiamo imparato a conoscere
una varietà di ordinamento e ricerca

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

4
00:00:09,442 --> 00:00:11,400
E a volte può essere
un po 'difficile da mantenere

5
00:00:11,400 --> 00:00:14,161
traccia di ciò che l'algoritmo fa che cosa.

6
00:00:14,161 --> 00:00:15,910
Abbiamo davvero solo
scremato la superficie troppo,

7
00:00:15,910 --> 00:00:18,740
ci sono molti altri di ricerca
e algoritmi di ordinamento.

8
00:00:18,740 --> 00:00:21,780
Quindi, in questo video diamo
basta prendere pochi minuti

9
00:00:21,780 --> 00:00:24,980
per cercare di distillare ogni algoritmo
fino ai suoi elementi fondamentali

10
00:00:24,980 --> 00:00:27,810
in modo da poter ricordare la più
informazioni importanti su di loro

11
00:00:27,810 --> 00:00:31,970
ed essere in grado di articolare la
le differenze, se necessario.

12
00:00:31,970 --> 00:00:34,220
>> Il primo è selection sort.

13
00:00:34,220 --> 00:00:38,210
L'idea di base dietro ordinamento per selezione
è trovare il più piccolo elemento indifferenziati

14
00:00:38,210 --> 00:00:42,890
in un array e scambiarlo con il
primo elemento indifferenziati di tale matrice.

15
00:00:42,890 --> 00:00:46,620
Abbiamo detto che il caso peggiore
tempo di esecuzione di cui è stato n al quadrato.

16
00:00:46,620 --> 00:00:50,060
E se si desidera richiamare perché, prende
un guardare il video selection sort.

17
00:00:50,060 --> 00:00:54,560
Il tempo di esecuzione nel caso migliore
è anche n quadrato.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, l'idea alla base che
uno è quello di scambiare coppie adiacenti.

19
00:00:58,910 --> 00:01:01,730
Quindi questa è la chiave che ti aiuta
ricordare la differenza qui.

20
00:01:01,730 --> 00:01:04,920
Selezione tipo è, fino ad ora,
trovare la bolla smallest--

21
00:01:04,920 --> 00:01:06,790
sort è scambiare le coppie adiacenti.

22
00:01:06,790 --> 00:01:08,710
Ci scambiamo coppie adiacenti
di elementi se

23
00:01:08,710 --> 00:01:12,530
sono fuori uso, che di fatto
bolle elementi più grandi a destra,

24
00:01:12,530 --> 00:01:17,060
e allo stesso tempo inizia anche
spostare elementi più piccoli a sinistra.

25
00:01:17,060 --> 00:01:20,180
Il tempo di esecuzione caso peggiore
di bubble sort è n quadrato.

26
00:01:20,180 --> 00:01:23,476
Il tempo di esecuzione nel caso migliore
di bubble sort è n.

27
00:01:23,476 --> 00:01:25,350
Perché in quella situazione
noi non actually--

28
00:01:25,350 --> 00:01:27,141
potremmo non è necessario
apportare swap affatto.

29
00:01:27,141 --> 00:01:31,026
Dobbiamo solo fare un
passare attraverso tutti gli elementi n.

30
00:01:31,026 --> 00:01:34,600
>> In insertion sort, il
idea di base si sta spostando.

31
00:01:34,600 --> 00:01:36,630
Questa è la parola chiave per insertion sort.

32
00:01:36,630 --> 00:01:39,630
Stiamo andando a un passo una volta attraverso
la matrice da sinistra a destra.

33
00:01:39,630 --> 00:01:41,670
E come facciamo noi, che siamo
andando a spostare elementi

34
00:01:41,670 --> 00:01:46,260
abbiamo già visto per fare spazio a
quelli più piccoli che hanno bisogno di adattarsi in qualche luogo

35
00:01:46,260 --> 00:01:48,080
indietro in quella porzione filtrate.

36
00:01:48,080 --> 00:01:51,600
Così si costruisce il array ordinato uno
elemento alla volta, da sinistra a destra,

37
00:01:51,600 --> 00:01:54,740
e ci spostiamo le cose per fare spazio.

38
00:01:54,740 --> 00:01:58,650
Il tempo di esecuzione nel caso peggiore di
insertion sort è n al quadrato.

39
00:01:58,650 --> 00:02:02,380
Il momento migliore caso familiare è n.

40
00:02:02,380 --> 00:02:05,380
>> Unire sort-- la parola chiave
qui è diviso e unire.

41
00:02:05,380 --> 00:02:08,949
Abbiamo diviso la gamma completa, se
è sei elementi, otto elementi,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- abbiamo diviso
giù della metà, della metà, della metà,

43
00:02:13,790 --> 00:02:17,720
fino a quando abbiamo sotto matrice
di n un array di elementi.

44
00:02:17,720 --> 00:02:19,470
Un insieme di n uno array di elementi.

45
00:02:19,470 --> 00:02:22,640
Così abbiamo iniziato con uno
Array di 1000 elementi,

46
00:02:22,640 --> 00:02:26,550
e arriviamo al punto in cui siamo
avere 1.000 matrici di un elemento.

47
00:02:26,550 --> 00:02:30,990
Poi si comincia a fondere quelle sub array
nuovo insieme nell'ordine corretto.

48
00:02:30,990 --> 00:02:34,860
Quindi prendiamo due array un elemento-
e creare una matrice a due elementi.

49
00:02:34,860 --> 00:02:38,180
Prendiamo due array di due elementi
e creare un array di quattro elementi

50
00:02:38,180 --> 00:02:43,900
e così via e così via finché non avremo
di nuovo ricostruito un array elemento n.

51
00:02:43,900 --> 00:02:48,410
>> Il tempo di esecuzione nel caso peggiore di
merge sort è n volte il log n.

52
00:02:48,410 --> 00:02:52,390
Abbiamo n elementi, ma
questo processo ricombinazione

53
00:02:52,390 --> 00:02:56,960
prende il log n passi per arrivare
indietro di una gamma completa.

54
00:02:56,960 --> 00:03:01,160
Il caso migliore tempo di esecuzione è anche log n
n perché questo processo non lo fa davvero

55
00:03:01,160 --> 00:03:04,090
gli importa se la matrice era
ordinati o non iniziare con.

56
00:03:04,090 --> 00:03:07,590
Il processo è lo stesso, c'è
modo di cose cortocircuito.

57
00:03:07,590 --> 00:03:11,610
Quindi n log n nel caso peggiore,
n log n nel migliore dei casi.

58
00:03:11,610 --> 00:03:13,960
>> Abbiamo parlato di due
algoritmi di ricerca.

59
00:03:13,960 --> 00:03:16,230
Quindi ricerca lineare è di circa iterazione.

60
00:03:16,230 --> 00:03:19,500
Si procede attraverso l'array
una volta, da sinistra a destra,

61
00:03:19,500 --> 00:03:21,950
cercando di trovare il numero di
che stiamo cercando.

62
00:03:21,950 --> 00:03:24,550
Il tempo peggiore familiare è grande O di n.

63
00:03:24,550 --> 00:03:27,610
Ci potrebbe prendere iterare
attraverso ogni singolo elemento

64
00:03:27,610 --> 00:03:30,660
per trovare l'elemento che stiamo cercando
per, sia in ultima posizione,

65
00:03:30,660 --> 00:03:31,630
o per niente.

66
00:03:31,630 --> 00:03:34,720
Ma non possiamo confermare che fino a
abbiamo esaminato tutto.

67
00:03:34,720 --> 00:03:36,730
m il caso migliore, troviamo subito.

68
00:03:36,730 --> 00:03:41,060
Il tempo di esecuzione nel caso migliore di
ricerca lineare è omega di 1.

69
00:03:41,060 --> 00:03:43,689
>> Infine, c'era la ricerca binaria,
che richiede schiera assortita.

70
00:03:43,689 --> 00:03:45,605
Ricordate che è una molto
importante considerazione

71
00:03:45,605 --> 00:03:47,155
quando si lavora con ricerca binaria.

72
00:03:47,155 --> 00:03:50,180
E 'un prerequisito per utilizzare it--
la matrice che si sta guardando attraverso

73
00:03:50,180 --> 00:03:52,160
devono essere ordinati.

74
00:03:52,160 --> 00:03:54,500
Altrimenti, la parola chiave
è divide et impera.

75
00:03:54,500 --> 00:03:58,310
Dividere l'array in mezzo e
eliminare la metà degli elementi

76
00:03:58,310 --> 00:04:00,780
ogni volta, come si procede attraverso.

77
00:04:00,780 --> 00:04:04,330
A causa di questo divide et impera
e le cose suddivisione in mezza approccio,

78
00:04:04,330 --> 00:04:07,450
il tempo di esecuzione nel caso peggiore
di ricerca binaria è

79
00:04:07,450 --> 00:04:11,730
log n, che è sostanzialmente
meglio di ricerca lineare n.

80
00:04:11,730 --> 00:04:13,570
Il momento migliore caso familiare, è ancora uno.

81
00:04:13,570 --> 00:04:17,010
>> Potremmo trovare subito il
prima volta che facciamo una divisione, ma,

82
00:04:17,010 --> 00:04:19,339
ancora una volta, ricordate che
sebbene ricerca binaria è

83
00:04:19,339 --> 00:04:24,030
sostanzialmente migliore di ricerca lineare
in virtù di essere contro log n n,

84
00:04:24,030 --> 00:04:27,110
potrebbe essere necessario passare attraverso il lavoro
di ordinare l'array prima, che

85
00:04:27,110 --> 00:04:32,010
potrebbe rendere meno efficaci a seconda
sulla dimensione della iterazione filtrate.

86
00:04:32,010 --> 00:04:35,250
>> Sono Doug Lloyd, questo è CS50.

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