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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Belə ki, CS50 biz haqqında öyrəndim
çeşidlənməsi və axtarış bir sıra

3
00:00:08,900 --> 00:00:09,442
alqoritmləri.

4
00:00:09,442 --> 00:00:11,400
Və bəzən ola bilər
saxlamaq üçün bir az çətin

5
00:00:11,400 --> 00:00:14,161
nə alqoritm track nə yoxdur.

6
00:00:14,161 --> 00:00:15,910
Biz, həqiqətən, yalnız var
çox səthi məsulları

7
00:00:15,910 --> 00:00:18,740
bir çox digər axtarış var
və alqoritmləri çeşidlənməsi.

8
00:00:18,740 --> 00:00:21,780
Belə ki, bu video edək
yalnız bir neçə dəqiqə

9
00:00:21,780 --> 00:00:24,980
cəhd və hər alqoritm çəkmək
əsas elementləri aşağı

10
00:00:24,980 --> 00:00:27,810
belə ki, ən yadda bilər
onlar haqqında əhəmiyyətli məlumatlar

11
00:00:27,810 --> 00:00:31,970
və ifadə etmək mümkün
fərqlər, zəruri hallarda.

12
00:00:31,970 --> 00:00:34,220
>> ilk seçim sortudur.

13
00:00:34,220 --> 00:00:38,210
seçim sort əsas ideyası
kiçik çeşidlənməmiş element tapmaq olunur

14
00:00:38,210 --> 00:00:42,890
və bir sıra ilə dəyişdirmək
ki, serialın ilk çeşidlənməmiş element.

15
00:00:42,890 --> 00:00:46,620
Ən pis halda olduğunu bildirib
ki, run dəfə kvadrat n oldu.

16
00:00:46,620 --> 00:00:50,060
Və niyə geri istəyirsinizsə, almaq
bir seçim sort video baxmaq.

17
00:00:50,060 --> 00:00:54,560
Ən yaxşı halda run vaxt
də n kvadrat edir.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort ki, arxasında ideyası
bir bitişik cüt dəyişdirmək üçün.

19
00:00:58,910 --> 00:01:01,730
Belə ki, sizə kömək edir əsas var
Burada fərq xatırlayıram.

20
00:01:01,730 --> 00:01:04,920
Seçki sort, bu günə qədər,
smallest-- bubble tapmaq

21
00:01:04,920 --> 00:01:06,790
sort bitişik cüt dəyişdirmək.

22
00:01:06,790 --> 00:01:08,710
Biz qonşu cüt dəyişdirmək
elementləri onlar əgər

23
00:01:08,710 --> 00:01:12,530
olan səmərəli qaydada həyata
, sağ böyük elementləri Bubbles

24
00:01:12,530 --> 00:01:17,060
və eyni zamanda bu da başlayır
sol kiçik elementləri hərəkət etmək.

25
00:01:17,060 --> 00:01:20,180
ən pis halda hal run vaxt
bubble növ n kvadrat edir.

26
00:01:20,180 --> 00:01:23,476
Ən yaxşı halda run vaxt
bubble sort n edir.

27
00:01:23,476 --> 00:01:25,350
Çünki ki, vəziyyət
biz həqiqətən deyil

28
00:01:25,350 --> 00:01:27,141
biz lazımdır bilər
hər hansı svopları edir.

29
00:01:27,141 --> 00:01:31,026
Biz yalnız bir etmək lazımdır
bütün n elementləri arasında keçir.

30
00:01:31,026 --> 00:01:34,600
>> Durub sort,
Burada əsas fikir dəyişir.

31
00:01:34,600 --> 00:01:36,630
Bu durub sırala üçün söz var.

32
00:01:36,630 --> 00:01:39,630
Biz vasitəsilə bir dəfə addım olacaq
olan array soldan sağa.

33
00:01:39,630 --> 00:01:41,670
Biz kimi, biz istəyirik
elementləri keçmək gedir

34
00:01:41,670 --> 00:01:46,260
Biz artıq üçün otaq etmək gördüm
haradasa uyğun lazımdır kiçik olanları

35
00:01:46,260 --> 00:01:48,080
geri sıralanır hissəsi.

36
00:01:48,080 --> 00:01:51,600
Beləliklə, biz sıralanır array qurmaq bir
soldan sağa bir zamanda element,

37
00:01:51,600 --> 00:01:54,740
və biz otaq etmək şeyi keçmək.

38
00:01:54,740 --> 00:01:58,650
ən pis halda run vaxt
durub sort n kvadrat edir.

39
00:01:58,650 --> 00:02:02,380
Ən yaxşı halda run zaman n edir.

40
00:02:02,380 --> 00:02:05,380
>> Söz sort Birleştirme
burada split və daxil edilir.

41
00:02:05,380 --> 00:02:08,949
Biz olsun, tam array split
bu altı elementləri, səkkiz elementləri var,

42
00:02:08,949 --> 00:02:13,790
10.000 elementləri biz split
aşağı yarısında, yarım, yarım,

43
00:02:13,790 --> 00:02:17,720
biz array altında qədər
n bir element seriallarda.

44
00:02:17,720 --> 00:02:19,470
N bir element seriallarda toplusu.

45
00:02:19,470 --> 00:02:22,640
Beləliklə, biz bir ilə başladı
1000-element array,

46
00:02:22,640 --> 00:02:26,550
və biz nöqtəsinə almaq biz
1000-element Diziler var.

47
00:02:26,550 --> 00:02:30,990
Sonra biz həmin sub serialların daxil başlayır
geri birlikdə düzgün qaydada.

48
00:02:30,990 --> 00:02:34,860
Beləliklə, biz iki bir-element serialların almaq
və iki element sıra yaratmaq.

49
00:02:34,860 --> 00:02:38,180
Biz iki-element Diziler almaq
və dörd element sıra yaratmaq

50
00:02:38,180 --> 00:02:43,900
və s və s biz sizin qədər
daha bir n element array yenidən.

51
00:02:43,900 --> 00:02:48,410
>> ən pis halda run vaxt
sort daxil n dəfə n daxil olun.

52
00:02:48,410 --> 00:02:52,390
Biz n elementləri var, amma
bu recombining proses

53
00:02:52,390 --> 00:02:56,960
daxil edir n addımlar almaq üçün
tam array geri.

54
00:02:56,960 --> 00:03:01,160
vaxt run ən yaxşı halda da n log edir
n bu proses həqiqətən deyil, çünki

55
00:03:01,160 --> 00:03:04,090
array olub qayğı
sıralanır və ya ilə başlamaq.

56
00:03:04,090 --> 00:03:07,590
proses var, eyni
qısa qapanma şeylər üçün heç bir yol.

57
00:03:07,590 --> 00:03:11,610
Belə ki, n ən pis halda n log,
n ən yaxşı halda n daxil olun.

58
00:03:11,610 --> 00:03:13,960
>> Biz iki haqqında danışdı
alqoritmlər axtarış.

59
00:03:13,960 --> 00:03:16,230
Belə ki, xətti axtarış iterating edir.

60
00:03:16,230 --> 00:03:19,500
Biz array arasında davam
bir dəfə, soldan sağa,

61
00:03:19,500 --> 00:03:21,950
sayı tapmaq üçün çalışırıq
ki, biz aradığınız.

62
00:03:21,950 --> 00:03:24,550
ən pis halda run zaman n böyük O edir.

63
00:03:24,550 --> 00:03:27,610
Bu iterating bizi bilər
hər bir element üzrə

64
00:03:27,610 --> 00:03:30,660
biz aradığınız element tapmaq
üçün, ya son mövqe,

65
00:03:30,660 --> 00:03:31,630
və ya bütün.

66
00:03:31,630 --> 00:03:34,720
Amma biz qədər təsdiq edə
biz hər şeyi baxdı etdik.

67
00:03:34,720 --> 00:03:36,730
ən yaxşı halda deyiləm, biz dərhal tapa bilərsiniz.

68
00:03:36,730 --> 00:03:41,060
ən yaxşı halda run vaxt
xətti axtarış 1 omega edir.

69
00:03:41,060 --> 00:03:43,689
>> Nəhayət, ikili axtarış var idi
olan müxtəlif array tələb edir.

70
00:03:43,689 --> 00:03:45,605
Ki, bir çox var saxla
mühüm baxılması

71
00:03:45,605 --> 00:03:47,155
Binar axtarış ilə iş zamanı.

72
00:03:47,155 --> 00:03:50,180
Bu pseudocode istifadə bir ön şərt var
Siz vasitəsilə aradığınız array

73
00:03:50,180 --> 00:03:52,160
sıralanır olmalıdır.

74
00:03:52,160 --> 00:03:54,500
Əks halda, söz
parçala və fəth edir.

75
00:03:54,500 --> 00:03:58,310
Yarısı daxil array Split və
elementlərin yarım aradan qaldırılması

76
00:03:58,310 --> 00:04:00,780
hər dəfə vasitəsilə davam kimi.

77
00:04:00,780 --> 00:04:04,330
Çünki bu uçurum və fəth
və yarım yanaşma parçalanması şeyi,

78
00:04:04,330 --> 00:04:07,450
ən pis halda run vaxt
ikili axtarış

79
00:04:07,450 --> 00:04:11,730
əhəmiyyətli dərəcədə olan, n log
xətti axtarış nin n daha yaxşı.

80
00:04:11,730 --> 00:04:13,570
Ən yaxşı halda run zaman hələ biridir.

81
00:04:13,570 --> 00:04:17,010
>> Biz dərhal tapa bilərsiniz
İlk dəfə biz bir bölmə, lakin

82
00:04:17,010 --> 00:04:19,339
yenə unutmayın ki
ikili axtarış, baxmayaraq ki,

83
00:04:19,339 --> 00:04:24,030
xətti axtarış nisbətən əhəmiyyətli dərəcədə daha yaxşı
log olmanın gərəyi n n qarşı,

84
00:04:24,030 --> 00:04:27,110
iş vasitəsilə getmək üçün ola bilər
, ilk array çeşidlənməsi hansı

85
00:04:27,110 --> 00:04:32,010
asılı olaraq az effektiv edə bilər
sıralaması iterating ölçüsü.

86
00:04:32,010 --> 00:04:35,250
>> Mən Doug Lloyd deyiləm, bu CS50 edir.

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