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

2
00:00:05,830 --> 00:00:07,910
>> ყველა უფლება, ასე, გამოთვლითი სირთულის.

3
00:00:07,910 --> 00:00:10,430
უბრალოდ ცოტა გაფრთხილება
სანამ ჩვენ ჩაყვინთვის ძალიან far--

4
00:00:10,430 --> 00:00:13,070
ამ ყველაფერს, ალბათ, მათ შორის
ყველაზე მათემატიკის მძიმე რამ

5
00:00:13,070 --> 00:00:14,200
ჩვენ ვსაუბრობთ CS50.

6
00:00:14,200 --> 00:00:16,950
იმედია ეს არ იქნება ძალიან დიდი
და ჩვენ შევეცდებით და დაგეხმარებათ

7
00:00:16,950 --> 00:00:19,200
მეშვეობით პროცესში, მაგრამ
უბრალოდ ცოტა სამართლიანი გაფრთხილება.

8
00:00:19,200 --> 00:00:21,282
არსებობს ცოტა
მათემატიკის ჩართული აქ.

9
00:00:21,282 --> 00:00:23,990
ყველა უფლება, რათა
გამოყენება ჩვენი გამოთვლითი რესურსების

10
00:00:23,990 --> 00:00:28,170
რეალურ world-- ეს მართლაც
მნიშვნელოვანია გვესმოდეს, ალგორითმები

11
00:00:28,170 --> 00:00:30,750
და როგორ გადაამუშავებს მონაცემები.

12
00:00:30,750 --> 00:00:32,810
თუ ჩვენ მართლაც გვაქვს
ეფექტური ალგორითმი, ჩვენ

13
00:00:32,810 --> 00:00:36,292
შეიძლება შეამციროს ოდენობით რესურსები
ჩვენ გვაქვს გაუმკლავდეთ მას.

14
00:00:36,292 --> 00:00:38,750
თუ ჩვენ გვაქვს ალგორითმი, რომელიც
აპირებს ბევრი მუშაობა

15
00:00:38,750 --> 00:00:41,210
დამუშავება ნამდვილად
დიდი კომპლექტი მონაცემები, ეს

16
00:00:41,210 --> 00:00:44,030
აპირებს მოითხოვოს მეტი
და სხვა რესურსები, რომელიც

17
00:00:44,030 --> 00:00:47,980
ფული, RAM, რომ ყველა სახის ნივთები.

18
00:00:47,980 --> 00:00:52,090
>> ასე რომ, მას შეუძლია ანალიზი
ალგორითმის გამოყენებით ეს ინსტრუმენტი კომპლექტი,

19
00:00:52,090 --> 00:00:56,110
ძირითადად, სთხოვს კითხვა
როგორ აკეთებს ამას ალგორითმი მასშტაბის

20
00:00:56,110 --> 00:00:59,020
როგორც ჩვენ იმისათვის, რომ უფრო და უფრო მეტი მონაცემები მას?

21
00:00:59,020 --> 00:01:02,220
In CS50, თანხის მონაცემები ჩვენ
მუშაობს საკმაოდ მცირე.

22
00:01:02,220 --> 00:01:05,140
საერთოდ, ჩვენი პროგრამების ვაპირებთ
აწარმოებს მეორე ან less--

23
00:01:05,140 --> 00:01:07,830
ალბათ ბევრი ნაკლებად
განსაკუთრებით დასაწყისში.

24
00:01:07,830 --> 00:01:12,250
>> მაგრამ ვიფიქროთ კომპანია, რომელიც ეხება
ასობით მილიონი მომხმარებელს.

25
00:01:12,250 --> 00:01:14,970
და მათ უნდა დამუშავება
რომ კლიენტების მონაცემები.

26
00:01:14,970 --> 00:01:18,260
როგორც რაოდენობის მომხმარებელს ისინი
აქვს უფრო დიდი და უფრო დიდი,

27
00:01:18,260 --> 00:01:21,230
ის აპირებს მოითხოვს
უფრო და უფრო მეტი რესურსი.

28
00:01:21,230 --> 00:01:22,926
კიდევ რამდენი რესურსი?

29
00:01:22,926 --> 00:01:25,050
ისე, რომ დამოკიდებულია იმაზე, რამდენად
ჩვენ ანალიზი ალგორითმი,

30
00:01:25,050 --> 00:01:28,097
გამოყენებით ინსტრუმენტი ამ ყუთისთვის.

31
00:01:28,097 --> 00:01:31,180
როდესაც ვსაუბრობთ სირთულის
ალგორითმი, რომელიც ზოგჯერ თქვენ

32
00:01:31,180 --> 00:01:34,040
მესმის, რომ ეს მოხსენიებული, როგორც დრო
სირთულის ან ჰარით სირთულის

33
00:01:34,040 --> 00:01:36,190
მაგრამ ჩვენ უბრალოდ აპირებს
მოვუწოდებთ complexity--

34
00:01:36,190 --> 00:01:38,770
ჩვენ ზოგადად ვსაუბრობთ
ყველაზე ცუდი სცენარით.

35
00:01:38,770 --> 00:01:42,640
იმის გათვალისწინებით, რომ ყველაზე უარესი წყობის
მონაცემები, რომ ჩვენ შეიძლება სროლა მას,

36
00:01:42,640 --> 00:01:46,440
როგორ არის ეს ალგორითმი აპირებს
დამუშავება და გაუმკლავდეთ, რომ მონაცემები?

37
00:01:46,440 --> 00:01:51,450
ჩვენ მოვუწოდებთ ზოგადად უარესი
runtime ალგორითმი დიდი ო.

38
00:01:51,450 --> 00:01:56,770
ასე რომ, ალგორითმი შეიძლება ითქვას, რომ
აწარმოებს ო ო ან O of n კვადრატში.

39
00:01:56,770 --> 00:01:59,110
და უფრო მეტი რა
იმ ნიშნავს მეორე.

40
00:01:59,110 --> 00:02:01,620
>> ზოგჯერ, თუმცა, ჩვენ ზრუნვა
შესახებ საუკეთესო სცენარია.

41
00:02:01,620 --> 00:02:05,400
თუ ეს მონაცემები ყველაფერი, რაც გვინდოდა
ეს უნდა იყოს და ეს იყო აბსოლუტურად სრულყოფილი

42
00:02:05,400 --> 00:02:09,630
და ჩვენ გაგზავნის ამ სრულყოფილი
მითითებული მონაცემების მეშვეობით ჩვენი ალგორითმი.

43
00:02:09,630 --> 00:02:11,470
როგორ უნდა გაუმკლავდეს, რომ სიტუაცია?

44
00:02:11,470 --> 00:02:15,050
ჩვენ ზოგჯერ ეხება, რომ როგორც
დიდი Omega, ასე რომ განსხვავებით დიდი O,

45
00:02:15,050 --> 00:02:16,530
ჩვენ გვაქვს დიდი ომეგა.

46
00:02:16,530 --> 00:02:18,880
Big-Omega საუკეთესო სცენარია.

47
00:02:18,880 --> 00:02:21,319
Big-O უარესი სცენარით.

48
00:02:21,319 --> 00:02:23,860
საერთოდ, როდესაც ჩვენ ვსაუბრობთ
სირთულის ალგორითმი,

49
00:02:23,860 --> 00:02:26,370
ჩვენ ვსაუბრობთ
უარესი სცენარით.

50
00:02:26,370 --> 00:02:28,100
გააგრძელეთ, რომ გონება.

51
00:02:28,100 --> 00:02:31,510
>> და ამ კლასში, ჩვენ ზოგადად აპირებს
დატოვება მკაცრი ანალიზი განზე.

52
00:02:31,510 --> 00:02:35,350
არსებობს მეცნიერებათა და სფეროებში
მიეძღვნა ამ სახის ნივთები.

53
00:02:35,350 --> 00:02:37,610
როდესაც ვსაუბრობთ მიზეზის
მეშვეობით ალგორითმები,

54
00:02:37,610 --> 00:02:41,822
რომელიც ჩვენ ყველაფერს გავაკეთებთ, ცალი მიერ ცალი მრავალი
ალგორითმები ვსაუბრობთ კლასში.

55
00:02:41,822 --> 00:02:44,780
ჩვენ რეალურად მხოლოდ ვსაუბრობთ
მსჯელობა საღი აზრი,

56
00:02:44,780 --> 00:02:47,070
არა ფორმულები, ან მტკიცებულებები,
ან რამე მსგავსი.

57
00:02:47,070 --> 00:02:51,600
ასე რომ არ ინერვიულოთ, ჩვენ არ იქნება
ნელა დიდი მათემატიკის კლასის.

58
00:02:51,600 --> 00:02:55,920
>> ამიტომ ვთქვი, რომ ჩვენ ვზრუნავთ სირთულის
იმიტომ, რომ ეს სვამს კითხვას, თუ როგორ

59
00:02:55,920 --> 00:03:00,160
გთხოვთ ჩვენი ალგორითმები გაუმკლავდეს უფრო დიდი და
უფრო დიდი მონაცემთა კომპლექტი მიმდინარეობს ესროლეს მათ.

60
00:03:00,160 --> 00:03:01,960
ისე, რა არის მონაცემთა ნაკრები?

61
00:03:01,960 --> 00:03:03,910
რა არ ვგულისხმობ, როცა განაცხადა, რომ?

62
00:03:03,910 --> 00:03:07,600
ეს იმას ნიშნავს, რაც ხდის ყველაზე
გრძნობა კონტექსტში, უნდა იყოს პატიოსანი.

63
00:03:07,600 --> 00:03:11,160
თუ ჩვენ გვაქვს ალგორითმი,
პროცესები Strings-- ჩვენ, ალბათ,

64
00:03:11,160 --> 00:03:13,440
ვსაუბრობთ ზომის სიმებიანი.

65
00:03:13,440 --> 00:03:15,190
სწორედ მონაცემები set--
ზომა, რაოდენობა

66
00:03:15,190 --> 00:03:17,050
გმირები, რომ შეადგინოს სიმებიანი.

67
00:03:17,050 --> 00:03:20,090
თუ ჩვენ ვსაუბრობთ
ალგორითმი, რომელიც გადაამუშავებს ფაილი,

68
00:03:20,090 --> 00:03:23,930
ჩვენ შეიძლება საუბარი, თუ როგორ
ბევრი kilobytes მოიცავს რომ ფაილი.

69
00:03:23,930 --> 00:03:25,710
და ეს მონაცემები კომპლექტი.

70
00:03:25,710 --> 00:03:28,870
თუ ჩვენ ვსაუბრობთ ალგორითმი
რომელიც ამუშავებს კოლექტორები უფრო ზოგადად,

71
00:03:28,870 --> 00:03:31,510
როგორიცაა დახარისხება ალგორითმები
ან ძებნას ალგორითმები,

72
00:03:31,510 --> 00:03:36,690
ჩვენ, ალბათ, ვსაუბრობთ ნომერი
ელემენტები, რომელიც მოიცავს მასივი.

73
00:03:36,690 --> 00:03:39,272
>> ახლა, ჩვენ შეგვიძლია გავზომოთ
ალგორითმი, კერძოდ,

74
00:03:39,272 --> 00:03:40,980
როდესაც ვამბობ, რომ ჩვენ შეგვიძლია
გავზომოთ ალგორითმი, მე

75
00:03:40,980 --> 00:03:43,840
იმას ნიშნავს, რომ ჩვენ შეგვიძლია გავზომოთ როგორ
ბევრი რესურსი სჭირდება მდე.

76
00:03:43,840 --> 00:03:48,990
თუ არა იმ რესურსების, რამდენი
ბაიტი RAM-- ან მბ მეხსიერება

77
00:03:48,990 --> 00:03:49,790
იგი იყენებს.

78
00:03:49,790 --> 00:03:52,320
ან, თუ რამდენი დრო სჭირდება აწარმოებს.

79
00:03:52,320 --> 00:03:56,200
და ჩვენ შეგვიძლია ვუწოდოთ
გავზომოთ, თვითნებურად, ვ ო.

80
00:03:56,200 --> 00:03:59,420
სადაც n რაოდენობის
ელემენტების მონაცემები კომპლექტი.

81
00:03:59,420 --> 00:04:02,640
და ფ ო რამდენი somethings.

82
00:04:02,640 --> 00:04:07,530
რამდენი ერთეული რესურსების აკეთებს
ის მოითხოვს დამუშავებას, რომ მონაცემები.

83
00:04:07,530 --> 00:04:10,030
>> ახლა, ჩვენ რეალურად არ მაინტერესებს
იმაზე, თუ რა ვ N არის ზუსტად.

84
00:04:10,030 --> 00:04:13,700
ფაქტობრივად, ჩვენ ძალიან იშვიათად will--
რა თქმა უნდა, არასდროს ამ კლასის მე

85
00:04:13,700 --> 00:04:18,709
ჩაყვინთვის შევიდა ნებისმიერი მართლაც ღრმა
ანალიზი, თუ რა ვ ო.

86
00:04:18,709 --> 00:04:23,510
ჩვენ უბრალოდ აპირებს ვისაუბროთ, თუ რა ვ
n დაახლოებით ან რა ეს ტენდენცია.

87
00:04:23,510 --> 00:04:27,600
და ტენდენცია ალგორითმი
ნაკარნახევი მისი უმაღლესი ჯილდო ვადით.

88
00:04:27,600 --> 00:04:29,440
და ჩვენ ვხედავთ, რაც მე
ნიშნავს, რომ ხდება

89
00:04:29,440 --> 00:04:31,910
შევხედოთ უფრო კონკრეტული მაგალითი.

90
00:04:31,910 --> 00:04:34,620
>> მოდით ვთქვათ, რომ ჩვენ გვაქვს
სამი სხვადასხვა ალგორითმები.

91
00:04:34,620 --> 00:04:39,350
პირველი, რომელიც იღებს n
კუბი, რამდენიმე ერთეული რესურსები

92
00:04:39,350 --> 00:04:42,880
დამუშავებას მონაცემები კომპლექტი ზომა n.

93
00:04:42,880 --> 00:04:47,000
ჩვენ გვყავს მეორე ალგორითმი, რომელიც იღებს
n cubed პლუს n კვადრატში რესურსები

94
00:04:47,000 --> 00:04:49,350
დამუშავებას მონაცემები კომპლექტი ზომა n.

95
00:04:49,350 --> 00:04:52,030
და ჩვენ გვაქვს მესამე
ალგორითმი, რომელიც ეშვება შიგნით რომ

96
00:04:52,030 --> 00:04:58,300
იკავებს n cubed მინუს 8n კვადრატი
პლუს 20 n ერთეული რესურსები

97
00:04:58,300 --> 00:05:02,370
დამუშავებას ალგორითმი
მონაცემები მითითებული ზომა n.

98
00:05:02,370 --> 00:05:05,594
>> ახლა, ჩვენ ნამდვილად არ ვაპირებთ
შეღწევას ამ დონის დეტალურად.

99
00:05:05,594 --> 00:05:08,260
მე ნამდვილად უნდა ამ up
აქ როგორც ილუსტრაცია წერტილი

100
00:05:08,260 --> 00:05:10,176
რომ მე ვაპირებ
მიღების მეორე, რომელიც

101
00:05:10,176 --> 00:05:12,980
არის, რომ ჩვენ მხოლოდ ნამდვილად აინტერესებს
შესახებ ტენდენცია რამ

102
00:05:12,980 --> 00:05:14,870
როგორც მონაცემების კომპლექტი დიდია.

103
00:05:14,870 --> 00:05:18,220
ასე რომ, თუ მონაცემები კომპლექტი არის პატარა, არსებობს
რეალურად საკმაოდ დიდი განსხვავება

104
00:05:18,220 --> 00:05:19,870
ამ ალგორითმები.

105
00:05:19,870 --> 00:05:23,000
მესამე ალგორითმი არსებობს
იღებს 13-ჯერ აღარ,

106
00:05:23,000 --> 00:05:27,980
13-ჯერ თანხა რესურსების
აწარმოებს ნათესავი პირველი.

107
00:05:27,980 --> 00:05:31,659
>> თუ ჩვენი მონაცემები კომპლექტი არის ზომა 10, რომელიც
არის დიდი, მაგრამ არ არის აუცილებელი დიდი,

108
00:05:31,659 --> 00:05:33,950
ჩვენ ვხედავთ, რომ იქ
რეალურად ცოტა განსხვავება.

109
00:05:33,950 --> 00:05:36,620
მესამე ალგორითმი
უფრო ეფექტური.

110
00:05:36,620 --> 00:05:40,120
ეს არის რეალურად 40% -
ან 60% -ით უფრო ეფექტურია.

111
00:05:40,120 --> 00:05:41,580
იგი იღებს 40% დროის.

112
00:05:41,580 --> 00:05:45,250
ეს შეიძლება პერსპექტივაში მას შეუძლია მიიღოს
400 ერთეული რესურსების

113
00:05:45,250 --> 00:05:47,570
დამუშავებას მონაცემები კომპლექტი ზომა 10.

114
00:05:47,570 --> 00:05:49,410
ვინაიდან პირველი
ალგორითმი, პირიქით,

115
00:05:49,410 --> 00:05:54,520
იღებს 1,000 ერთეული რესურსები
დამუშავებას მონაცემები კომპლექტი ზომა 10.

116
00:05:54,520 --> 00:05:57,240
მაგრამ შეხედეთ, რა ხდება,
ჩვენი ციფრები კიდევ უფრო დიდი.

117
00:05:57,240 --> 00:05:59,500
>> ახლა, განსხვავება
შორის ამ ალგორითმები

118
00:05:59,500 --> 00:06:01,420
დაიწყოს გახდეს ცოტა ნაკლებად აშკარა.

119
00:06:01,420 --> 00:06:04,560
ხოლო ის ფაქტი, რომ არსებობს
ქვედა რათა terms-- უფრო სწორად,

120
00:06:04,560 --> 00:06:09,390
ვადები, ქვედა exponents--
დაიწყოს გახდეს შეუსაბამო.

121
00:06:09,390 --> 00:06:12,290
თუ მონაცემები კომპლექტი არის ზომა
1000 და პირველი ალგორითმი

122
00:06:12,290 --> 00:06:14,170
გადის მილიარდი ნაბიჯები.

123
00:06:14,170 --> 00:06:17,880
და მეორე ალგორითმი ეშვება
მილიარდი და მილიონი ნაბიჯები.

124
00:06:17,880 --> 00:06:20,870
და მესამე ალგორითმი გადის
მხოლოდ shy მილიარდი ნაბიჯები.

125
00:06:20,870 --> 00:06:22,620
ეს საკმაოდ ბევრი მილიარდი ნაბიჯები.

126
00:06:22,620 --> 00:06:25,640
ისინი ქვედა წესრიგის თვალსაზრისით დაიწყოს
გახდეს ნამდვილად შეუსაბამო.

127
00:06:25,640 --> 00:06:27,390
და მხოლოდ ნამდვილად
ჩაქუჩი მთავარი point--

128
00:06:27,390 --> 00:06:31,240
იმ შემთხვევაში, თუ მონაცემების შეტანის არის ზომა
million-- სამივე საკმაოდ ბევრი

129
00:06:31,240 --> 00:06:34,960
მიიღოს ერთი quintillion-- თუ
ჩემი მათემატიკის correct-- ნაბიჯები

130
00:06:34,960 --> 00:06:37,260
დამუშავებას მონაცემების შეტანის
ზომა მილიონი.

131
00:06:37,260 --> 00:06:38,250
ეს არის ის, ბევრი ნაბიჯები.

132
00:06:38,250 --> 00:06:42,092
ხოლო ის ფაქტი, რომ ერთ-ერთი მათგანი, შესაძლოა,
მიიღოს რამდენიმე 100,000 ან რამდენიმე 100

133
00:06:42,092 --> 00:06:44,650
მილიონი კიდევ უფრო ნაკლები, როდესაც
ჩვენ ვსაუბრობთ ნომერი

134
00:06:44,650 --> 00:06:46,990
რომ big-- ეს არის სახის შეუსაბამო.

135
00:06:46,990 --> 00:06:50,006
ისინი ყველა ტენდენცია მიიღოს
დაახლოებით n cubed,

136
00:06:50,006 --> 00:06:52,380
და ასე რომ, ჩვენ რეალურად ეხება
ყველა ეს ალგორითმები

137
00:06:52,380 --> 00:06:59,520
როგორც ბრძანებით n
კუბი და დიდი ო ო cubed.

138
00:06:59,520 --> 00:07:03,220
>> აქ არის სია ზოგიერთი უფრო
საერთო გამოთვლითი სირთულის კატეგორიები

139
00:07:03,220 --> 00:07:05,820
ის, რომ ჩვენ ვაწყდებით
ალგორითმები, ზოგადად.

140
00:07:05,820 --> 00:07:07,970
და ასევე კონკრეტულად CS50.

141
00:07:07,970 --> 00:07:11,410
ეს დავალება
ზოგადად სწრაფად ზედა,

142
00:07:11,410 --> 00:07:13,940
ზოგადად ნელი ბოლოში.

143
00:07:13,940 --> 00:07:16,920
ასე რომ, მუდმივი დრო ალგორითმები, როგორც წესი,
იყოს სწრაფი, მიუხედავად იმისა,

144
00:07:16,920 --> 00:07:19,110
ერთი ზომა
მონაცემთა შეყვანის გაივლის.

145
00:07:19,110 --> 00:07:23,760
ისინი ყოველთვის ერთი ოპერაციის და
ერთი ერთეული რესურსების გამკლავება.

146
00:07:23,760 --> 00:07:25,730
ეს შეიძლება იყოს 2, შესაძლოა,
3, ეს შეიძლება იყოს 4.

147
00:07:25,730 --> 00:07:26,910
მაგრამ ეს მუდმივი ნომერი.

148
00:07:26,910 --> 00:07:28,400
ეს არ იცვლება.

149
00:07:28,400 --> 00:07:31,390
>> ლოგარითმული დრო ალგორითმები
ოდნავ უკეთესი.

150
00:07:31,390 --> 00:07:33,950
და ძალიან კარგი მაგალითია
ლოგარითმული დრო ალგორითმი

151
00:07:33,950 --> 00:07:37,420
თქვენ აუცილებლად ჩანს ახლა არის
tearing გარდა სატელეფონო წიგნი

152
00:07:37,420 --> 00:07:39,480
მოძიების მაიკ სმიტი სატელეფონო წიგნი.

153
00:07:39,480 --> 00:07:40,980
ჩვენ გაჭრა პრობლემა ნახევარი.

154
00:07:40,980 --> 00:07:43,580
ასე რომ, როგორც ო იღებს დიდი
და უფრო დიდი და larger--

155
00:07:43,580 --> 00:07:47,290
ფაქტობრივად, ყოველ დროს, თქვენ გაორმაგდება
n, ეს მხოლოდ იღებს, კიდევ ერთი ნაბიჯი.

156
00:07:47,290 --> 00:07:49,770
ასე რომ, ბევრი უკეთესი
ვიდრე, ვთქვათ, ხაზოვანი დრო.

157
00:07:49,770 --> 00:07:53,030
რა არის თუ ორჯერ n, ის
იღებს ორმაგი რაოდენობის ნაბიჯები.

158
00:07:53,030 --> 00:07:55,980
თუ თქვენ გასამმაგებას n, სჭირდება
გასამმაგებას რაოდენობის ნაბიჯები.

159
00:07:55,980 --> 00:07:58,580
ერთი ნაბიჯი თითო ერთეული.

160
00:07:58,580 --> 00:08:01,790
>> მაშინ რამ კიდევ ცოტა more--
ცოტა ნაკლები დიდი იქიდან.

161
00:08:01,790 --> 00:08:06,622
თქვენ ხაზოვანი რიტმული დროს, ზოგჯერ
სახელად შესვლა ხაზოვანი დროს ან უბრალოდ N შეხვიდეთ n.

162
00:08:06,622 --> 00:08:08,330
და ჩვენ, მაგალითად
ალგორითმი, რომელიც

163
00:08:08,330 --> 00:08:13,370
ეშვება N შესვლა N, რომელიც ჯერ კიდევ უკეთესი
მეტი კვადრატული time-- n კვადრატში.

164
00:08:13,370 --> 00:08:17,320
ან მრავალწევრის დროს, n ორი
ნებისმიერი რაოდენობის აღემატება ორ.

165
00:08:17,320 --> 00:08:20,810
ან ექსპონენციალური დრო, რომელიც
კიდევ worse-- C ო.

166
00:08:20,810 --> 00:08:24,670
ასე რომ, გარკვეული მუდმივი დააყენა, რათა
ძალა ზომა შეყვანა.

167
00:08:24,670 --> 00:08:28,990
ასე რომ, თუ იქ 1,000-- თუ
მონაცემთა შეყვანის ზომა 1000

168
00:08:28,990 --> 00:08:31,310
დასჭირდება C რომ 1,000th ძალა.

169
00:08:31,310 --> 00:08:33,559
ეს გაცილებით უარესია, ვიდრე მრავალწევრის დროს.

170
00:08:33,559 --> 00:08:35,030
>> Factorial დრო არის უარესი.

171
00:08:35,030 --> 00:08:37,760
და სინამდვილეში, იქ ნამდვილად გააკეთებს
არსებობს უსასრულო დრო ალგორითმები,

172
00:08:37,760 --> 00:08:43,740
როგორიცაა, ე.წ. სულელური დალაგება რომლის
სამუშაო შემთხვევით shuffle მასივი

173
00:08:43,740 --> 00:08:45,490
და მაშინ შეამოწმეთ
თუ არა ეს დახარისხებული.

174
00:08:45,490 --> 00:08:47,589
და თუ ეს ასე არ არის, შემთხვევით
shuffle მასივი ერთხელ

175
00:08:47,589 --> 00:08:49,130
და შეამოწმეთ თუ არა ეს დახარისხებული.

176
00:08:49,130 --> 00:08:51,671
და როგორც თქვენ ალბათ imagine--
თქვენ წარმოიდგინეთ სიტუაცია

177
00:08:51,671 --> 00:08:55,200
სადაც ყველაზე უარესი, რაც უზრუნველყოფს
არასოდეს რეალურად იწყება მასივი.

178
00:08:55,200 --> 00:08:57,150
ეს ალგორითმი, რომ აწარმოებს სამუდამოდ.

179
00:08:57,150 --> 00:08:59,349
და ისე, რომ იქნება
უსასრულო დრო ალგორითმი.

180
00:08:59,349 --> 00:09:01,890
იმედია თქვენ არ უნდა წერა
ნებისმიერი factorial და უსასრულო დრო

181
00:09:01,890 --> 00:09:04,510
ალგორითმები CS50.

182
00:09:04,510 --> 00:09:09,150
>> ასე რომ, მოდით ცოტა მეტი
კონკრეტული შევხედოთ ზოგიერთი მარტივი

183
00:09:09,150 --> 00:09:11,154
გამოთვლითი სირთულის კლასი.

184
00:09:11,154 --> 00:09:13,070
ასე რომ, ჩვენ გვაქვს მაგალითად
ან ორი მაგალითები აქ

185
00:09:13,070 --> 00:09:15,590
მუდმივი დრო ალგორითმები,
რომელიც ყოველთვის

186
00:09:15,590 --> 00:09:17,980
ერთი ოპერაცია უარეს შემთხვევაში.

187
00:09:17,980 --> 00:09:20,050
ასე რომ, პირველი მაგალითად
ჩვენ გვაქვს ფუნქცია

188
00:09:20,050 --> 00:09:23,952
მოუწოდა 4 თქვენთვის, რომელიც
იღებს მასივი ზომა 1000.

189
00:09:23,952 --> 00:09:25,660
მაგრამ შემდეგ, როგორც ჩანს,
ფაქტობრივად არ ჰგავს

190
00:09:25,660 --> 00:09:29,000
განთავსებულია it-- ნამდვილად არ აინტერესებს რა არის
შიგნით, რომ მასივი.

191
00:09:29,000 --> 00:09:30,820
ყოველთვის მხოლოდ ბრუნდება ოთხ.

192
00:09:30,820 --> 00:09:32,940
ასე რომ, ალგორითმი,
მიუხედავად იმისა, რომ ეს

193
00:09:32,940 --> 00:09:35,840
იღებს 1,000 ელემენტები არ
არაფერი მათთან.

194
00:09:35,840 --> 00:09:36,590
უბრალოდ ბრუნდება ოთხ.

195
00:09:36,590 --> 00:09:38,240
ის ყოველთვის ერთი ნაბიჯი.

196
00:09:38,240 --> 00:09:41,600
>> ფაქტობრივად, დავუმატოთ 2 nums-- რომელიც
ჩვენ ვნახეთ ადრე, როგორც well--

197
00:09:41,600 --> 00:09:43,680
მხოლოდ ამუშავებს ორი რიცხვებით.

198
00:09:43,680 --> 00:09:44,692
ეს არ არის ერთი ნაბიჯი.

199
00:09:44,692 --> 00:09:45,900
ეს, ფაქტობრივად, რამდენიმე ნაბიჯი.

200
00:09:45,900 --> 00:09:50,780
თქვენ, თქვენ b, თქვენ დაამატოთ მათ
ერთად და გამომავალი შედეგები.

201
00:09:50,780 --> 00:09:53,270
ასე რომ, ეს 84 ნაბიჯები.

202
00:09:53,270 --> 00:09:55,510
მაგრამ ეს ყოველთვის მუდმივი,
მიუხედავად იმისა, ან ბ.

203
00:09:55,510 --> 00:09:59,240
თქვენ უნდა მიიღოს, კიდევ ბ, დაამატოთ
მათ ერთად, გამომავალი შედეგი.

204
00:09:59,240 --> 00:10:02,900
ასე რომ, მუდმივი დროის ალგორითმი.

205
00:10:02,900 --> 00:10:05,170
>> აი, მაგალითად,
ხაზოვანი დროს ალგორითმი

206
00:10:05,170 --> 00:10:08,740
ალგორითმი, რომელიც gets--, რომელიც იღებს
დამატებით ერთი ნაბიჯი, შესაძლოა,

207
00:10:08,740 --> 00:10:10,740
როგორც თქვენი შეყვანის იზრდება 1.

208
00:10:10,740 --> 00:10:14,190
ასე რომ, ვთქვათ, ჩვენ ვეძებთ
ნომერი 5 შიგნით მასივი.

209
00:10:14,190 --> 00:10:16,774
ალბათ სიტუაცია, სადაც
თქვენ შეგიძლიათ იპოვოთ ის საკმაოდ ადრეულ.

210
00:10:16,774 --> 00:10:18,606
მაგრამ თქვენ შეიძლება ასევე აქვს
სიტუაცია, სადაც ის

211
00:10:18,606 --> 00:10:20,450
შეიძლება იყოს ბოლო ელემენტს მასივი.

212
00:10:20,450 --> 00:10:23,780
In მასივი ზომა 5, თუ
ჩვენ ვეძებთ ნომერი 5.

213
00:10:23,780 --> 00:10:25,930
დასჭირდება 5 ნაბიჯები.

214
00:10:25,930 --> 00:10:29,180
და სინამდვილეში, წარმოვიდგენდი, რომ იქ
არა 5 სადმე ამ მასივი.

215
00:10:29,180 --> 00:10:32,820
ჩვენ ჯერ კიდევ რეალურად უნდა შევხედოთ
თითოეული ელემენტის მასივი

216
00:10:32,820 --> 00:10:35,550
რათა დადგინდეს,
თუ არა 5 არის.

217
00:10:35,550 --> 00:10:39,840
>> ასე რომ, უარეს შემთხვევაში, არის ის, რომ
ელემენტი არის ბოლო მასივი

218
00:10:39,840 --> 00:10:41,700
ან არ არსებობს.

219
00:10:41,700 --> 00:10:44,690
ჩვენ კვლავ უნდა შევხედოთ
ყველა n ელემენტებს.

220
00:10:44,690 --> 00:10:47,120
ასე რომ, ეს ალგორითმი
გადის ხაზოვანი დრო.

221
00:10:47,120 --> 00:10:50,340
თქვენ შეგიძლიათ ადასტურებენ, რომ
ექსტრაპოლაციის ცოტა განაცხადა,

222
00:10:50,340 --> 00:10:53,080
თუ ჩვენ გვქონდა 6-ელემენტს მასივი და
ჩვენ ეძებდნენ ნომერი 5,

223
00:10:53,080 --> 00:10:54,890
ეს შესაძლოა 6 ნაბიჯები.

224
00:10:54,890 --> 00:10:57,620
თუ ჩვენ გვაქვს 7-ელემენტს მასივი და
ჩვენ ვეძებთ ნომერი 5.

225
00:10:57,620 --> 00:10:59,160
ეს შეიძლება მიიღოს 7 ნაბიჯები.

226
00:10:59,160 --> 00:11:02,920
როგორც ჩვენ კიდევ ერთი ელემენტია ჩვენი
მასივი, სჭირდება კიდევ ერთი ნაბიჯი.

227
00:11:02,920 --> 00:11:06,750
სწორედ ხაზოვანი ალგორითმი
უარეს შემთხვევაში.

228
00:11:06,750 --> 00:11:08,270
>> Couple სწრაფი კითხვებზე თქვენთვის.

229
00:11:08,270 --> 00:11:11,170
რა არის runtime-- რა არის
უარესი runtime

230
00:11:11,170 --> 00:11:13,700
ამ კონკრეტულ მონაკვეთში კოდი?

231
00:11:13,700 --> 00:11:17,420
ასე რომ, მე მაქვს 4 loop აქ, რომ გადის
საწყისი j უდრის 0, ყველა გზა მდე მ.

232
00:11:17,420 --> 00:11:21,980
და რა მე ვხედავთ აქ, ის არის, რომ
ორგანოს loop გადის მუდმივ დრო.

233
00:11:21,980 --> 00:11:24,730
ამიტომ გამოყენებით ტერმინი,
ჩვენ უკვე ვისაუბრეთ ამაზე რა

234
00:11:24,730 --> 00:11:29,390
იქნება უარესი
runtime ამ ალგორითმი?

235
00:11:29,390 --> 00:11:31,050
მიიღეთ მეორე.

236
00:11:31,050 --> 00:11:34,270
შიდა ნაწილი loop
გადის მუდმივ დრო.

237
00:11:34,270 --> 00:11:37,510
და გარე ნაწილი
loop აპირებს აწარმოებს მ ჯერ.

238
00:11:37,510 --> 00:11:40,260
რა არის უარესი Runtime აქ?

239
00:11:40,260 --> 00:11:43,210
ხომ იცი, დიდი O მ?

240
00:11:43,210 --> 00:11:44,686
ნეტავ იყოს სწორი.

241
00:11:44,686 --> 00:11:46,230
>> როგორ შესახებ კიდევ ერთი?

242
00:11:46,230 --> 00:11:48,590
ამჯერად ჩვენ გვაქვს
loop შიგნით loop.

243
00:11:48,590 --> 00:11:50,905
ჩვენ გვყავს გარე მარყუჟის
რომელიც ეშვება ნულიდან გვ.

244
00:11:50,905 --> 00:11:54,630
და ჩვენ გვაქვს შიდა loop, რომელიც ეშვება
ნულიდან p, და შიგნით რომ,

245
00:11:54,630 --> 00:11:57,890
ვაცხადებ, რომ სხეულის
loop გადის მუდმივ დრო.

246
00:11:57,890 --> 00:12:02,330
რა არის უარესი Runtime
ამ კონკრეტულ მონაკვეთში კოდი?

247
00:12:02,330 --> 00:12:06,140
ისე, კიდევ ერთხელ, ჩვენ გვაქვს
გარე loop, რომელიც ეშვება p ჯერ.

248
00:12:06,140 --> 00:12:09,660
და თითოეული time-- იტერაციული
რომ მარყუჟი, საკმაოდ.

249
00:12:09,660 --> 00:12:13,170
ჩვენ გვყავს შიდა loop
რომელიც ასევე გადის p ჯერ.

250
00:12:13,170 --> 00:12:16,900
და შემდეგ შიგნით რომ, არსებობს
მუდმივი time-- მცირე მონაკვეთში არსებობს.

251
00:12:16,900 --> 00:12:19,890
>> ასე რომ, თუ ჩვენ გვაქვს გარე მარყუჟის, რომ
გადის p ჯერ შიგნით რაც არის

252
00:12:19,890 --> 00:12:22,880
შიდა მარყუჟის, რომ
გადის p times-- რა არის

253
00:12:22,880 --> 00:12:26,480
უარესი runtime
ამ მონაკვეთში კოდი?

254
00:12:26,480 --> 00:12:30,730
ხომ იცი, დიდი O პ კვადრატი?

255
00:12:30,730 --> 00:12:31,690
>> მე Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
ეს არის CS50.

257
00:12:33,880 --> 00:12:35,622