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

2
00:00:05,760 --> 00:00:08,900
>> Даг LLOYD: Значи во CS50 научивме за
различни сортирање и пребарување

3
00:00:08,900 --> 00:00:09,442
алгоритми.

4
00:00:09,442 --> 00:00:11,400
А понекогаш тоа може да биде
малку незгодно да се задржи

5
00:00:11,400 --> 00:00:14,161
пратите на она што алгоритам што прави.

6
00:00:14,161 --> 00:00:15,910
Ние сме навистина само
обезмастено површината премногу,

7
00:00:15,910 --> 00:00:18,740
постојат многу други пребарување
и алгоритми за сортирање.

8
00:00:18,740 --> 00:00:21,780
Така што во овој видео ајде
само да потрае неколку минути

9
00:00:21,780 --> 00:00:24,980
да се обиде да го дестилираат секој алгоритам
надолу за да нејзините основни елементи

10
00:00:24,980 --> 00:00:27,810
за да можете да се сеќавам на повеќето
важни информации за нив

11
00:00:27,810 --> 00:00:31,970
и да бидат способни да ги артикулираат
разлики, ако е потребно.

12
00:00:31,970 --> 00:00:34,220
>> Првиот е селекција вид.

13
00:00:34,220 --> 00:00:38,210
Основната идеја зад селекција вид
се најде најмалиот несортиран елемент

14
00:00:38,210 --> 00:00:42,890
во низа и го трампа со
Првиот несортиран елемент на таа низа.

15
00:00:42,890 --> 00:00:46,620
Кажавме дека најлошото
се кандидира за време на која беше n квадрат.

16
00:00:46,620 --> 00:00:50,060
И ако сакате да се потсетиме зошто, да ги преземе
Еден поглед на избор на вид на видео.

17
00:00:50,060 --> 00:00:54,560
Време најдобар случај бегство
е исто така n квадрат.

18
00:00:54,560 --> 00:00:58,910
>> Меур вид, идејата зад кои
едно е да се разменуваат со соседните парови.

19
00:00:58,910 --> 00:01:01,730
Значи тоа е клучот, кој ви помага
запомните разликата тука.

20
00:01:01,730 --> 00:01:04,920
Селекција вид е, досега,
најдете smallest-- меурот

21
00:01:04,920 --> 00:01:06,790
вид е разменуваат со соседните парови.

22
00:01:06,790 --> 00:01:08,710
Ние разменуваат со соседните парови
на елементите, ако тие

23
00:01:08,710 --> 00:01:12,530
се надвор од употреба, кои ефикасно
меурчиња поголеми елементи на правото,

24
00:01:12,530 --> 00:01:17,060
и во исто време, исто така, таа започнува
да се движи помали елементи од лево.

25
00:01:17,060 --> 00:01:20,180
Време случај рок најлош случај
на меур вид е N на квадрат.

26
00:01:20,180 --> 00:01:23,476
Време најдобар случај бегство
на меур вид е n.

27
00:01:23,476 --> 00:01:25,350
Бидејќи во таква ситуација
ние не actually--

28
00:01:25,350 --> 00:01:27,141
ние не би можеле да треба да се
направи било размена на сите.

29
00:01:27,141 --> 00:01:31,026
Ние само треба да се направи една
поминат низ сите n елементи.

30
00:01:31,026 --> 00:01:34,600
>> Во вметнување вид,
Основната идеја тука се менува.

31
00:01:34,600 --> 00:01:36,630
Тоа е клучниот збор за вметнување вид.

32
00:01:36,630 --> 00:01:39,630
Ние ќе треба да се чекор еднаш преку
низа од лево кон десно.

33
00:01:39,630 --> 00:01:41,670
И што и да правиме, ние сме
ќе се префрлат елементи

34
00:01:41,670 --> 00:01:46,260
веќе видовме се направи простор за
помали, кои треба да се вклопи некаде

35
00:01:46,260 --> 00:01:48,080
назад во таа подредени дел.

36
00:01:48,080 --> 00:01:51,600
За да можеме да се изгради една низа сортирани
елемент во исто време, од лево кон десно,

37
00:01:51,600 --> 00:01:54,740
и ние смена работите да се направи простор.

38
00:01:54,740 --> 00:01:58,650
Времето на најлош случај на бегство
вметнување вид е N на квадрат.

39
00:01:58,650 --> 00:02:02,380
Време најдобар случај се кандидира е n.

40
00:02:02,380 --> 00:02:05,380
>> Логирате sort-- клучниот збор
тука е поделена и се спојуваат.

41
00:02:05,380 --> 00:02:08,949
Тргнавме целиот низ, без разлика дали
тоа е шест елементи, осум елементи,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- ние го подели
надолу за половина, на половина, за половина,

43
00:02:13,790 --> 00:02:17,720
додека имаме под низа
од n еден елемент низи.

44
00:02:17,720 --> 00:02:19,470
А во собата на еден елемент n низи.

45
00:02:19,470 --> 00:02:22,640
Па почнавме со една
1000-елемент низа,

46
00:02:22,640 --> 00:02:26,550
а ние се дојде до точка каде што
има 1.000 еден елемент низи.

47
00:02:26,550 --> 00:02:30,990
Тогаш почнуваме да се спојат овие суб низи
повторно заедно во правилен ред.

48
00:02:30,990 --> 00:02:34,860
Па ние се две една елемент низи
и создаде две-елемент низа.

49
00:02:34,860 --> 00:02:38,180
Земаме две со две низи елемент
и да се создаде четири-елемент на низата

50
00:02:38,180 --> 00:02:43,900
и така натаму и така натаму се додека ние сме
повторно го обновил еден n елемент низа.

51
00:02:43,900 --> 00:02:48,410
>> Времето на најлош случај на бегство
спојат вид е n log n пати.

52
00:02:48,410 --> 00:02:52,390
Имаме n елементи, но
овој процес рекомбинирачките

53
00:02:52,390 --> 00:02:56,960
зема логирате n чекори за да добие
назад кон целосна низа.

54
00:02:56,960 --> 00:03:01,160
Најдобар случај кандидира време е исто така n најавите
n бидејќи овој процес навистина не

55
00:03:01,160 --> 00:03:04,090
грижа дали низата беше
подредени или да не се започне со.

56
00:03:04,090 --> 00:03:07,590
Процесот е ист, има
нема начин да краток спој работите.

57
00:03:07,590 --> 00:03:11,610
Така n log n во најлош случај,
n log n во најдобар случај.

58
00:03:11,610 --> 00:03:13,960
>> Ние разговаравме за двајца
пребарување алгоритми.

59
00:03:13,960 --> 00:03:16,230
Така линеарно пребарување е за процесирањето.

60
00:03:16,230 --> 00:03:19,500
Ние се продолжи низ низа
еднаш, од лево кон десно,

61
00:03:19,500 --> 00:03:21,950
во обид да се најде бројот
кои ги барате.

62
00:03:21,950 --> 00:03:24,550
Најлош случај кандидира време е голема О на n.

63
00:03:24,550 --> 00:03:27,610
Тоа би можело да ни потрае процесирањето
низ секој елемент

64
00:03:27,610 --> 00:03:30,660
да се најде на елементот што го бараме
за, било на последното место,

65
00:03:30,660 --> 00:03:31,630
или воопшто не.

66
00:03:31,630 --> 00:03:34,720
Но, ние не може да се потврди дека до
Ние гледаше во сè.

67
00:03:34,720 --> 00:03:36,730
m на најдобар случај, ние веднаш се најде.

68
00:03:36,730 --> 00:03:41,060
Време најдобар случај на бегство
линеарно пребарување е омега на 1.

69
00:03:41,060 --> 00:03:43,689
>> И на крај, имаше бинарни пребарување,
која бара избрани низа.

70
00:03:43,689 --> 00:03:45,605
Се сеќавам дека е многу
важен предвид

71
00:03:45,605 --> 00:03:47,155
кога се работи со бинарни пребарување.

72
00:03:47,155 --> 00:03:50,180
Тоа е предуслов за користење it--
низата дека барате преку

73
00:03:50,180 --> 00:03:52,160
мора да се решат.

74
00:03:52,160 --> 00:03:54,500
Инаку, на клучен збор
е раздели па владеј.

75
00:03:54,500 --> 00:03:58,310
Подели на низа во половина и
елиминира половина на елементи

76
00:03:58,310 --> 00:04:00,780
секој пат како што напредувате низ.

77
00:04:00,780 --> 00:04:04,330
Затоа што на оваа поделба и освојување
и поделба на работите на половина пристап,

78
00:04:04,330 --> 00:04:07,450
време најлош случај бегство
на бинарни пребарување е

79
00:04:07,450 --> 00:04:11,730
најавите n, што е значително
подобра од n линеарно пребарување е.

80
00:04:11,730 --> 00:04:13,570
Време најдобар случај се кандидира е уште еден.

81
00:04:13,570 --> 00:04:17,010
>> Ние може да го најдете веднаш
прв пат, ние правиме поделба, но,

82
00:04:17,010 --> 00:04:19,339
повторно, се сеќавам дека
иако бинарни пребарување е

83
00:04:19,339 --> 00:04:24,030
значително подобро од линеарно пребарување
со самото тоа што наспроти најавите n n,

84
00:04:24,030 --> 00:04:27,110
можеби ќе треба да се оди преку работата
на сортирањето вашиот низа Првиот, кој

85
00:04:27,110 --> 00:04:32,010
Може да се направи тоа помалку ефикасни во зависност
од големината на процесирањето подредени.

86
00:04:32,010 --> 00:04:35,250
>> Јас сум Даг Лојд, ова е CS50.

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