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
ใน 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
เมื่อเราพูดคุยเกี่ยวกับความซับซ้อนของ
algorithm-- ซึ่งบางครั้งคุณจะ

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
โดยทั่วไปเราเรียกว่าเลวร้ายที่สุดกรณี
รันไทม์ของอัลกอริทึมใหญ่-O

38
00:01:51,450 --> 00:01:56,770
ดังนั้นขั้นตอนวิธีการอาจจะกล่าวได้ว่า
ทำงานในโอ n หรือโอ 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
บางครั้งเราหมายถึงว่า
โอเมก้าขนาดใหญ่ดังนั้นในทางตรงกันข้ามกับใหญ่โอ

45
00:02:15,050 --> 00:02:16,530
เรามีขนาดใหญ่โอเมก้า

46
00:02:16,530 --> 00:02:18,880
บิ๊กโอเมก้าสำหรับกรณีที่ดีที่สุด

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
เราอาจจะมีการพูดคุยเกี่ยวกับวิธีการ
หลายกิโลไบต์ประกอบด้วยแฟ้มที่

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
>> ตอนนี้เราสามารถวัด
algorithm-- โดยเฉพาะอย่างยิ่ง

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-- หรือเมกะไบต์ 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
และเราสามารถเรียกสิ่งนี้
วัดพลฉของ n

80
00:03:56,200 --> 00:03:59,420
ที่ n คือจำนวนของ
องค์ประกอบในชุดข้อมูล

81
00:03:59,420 --> 00:04:02,640
และฉของ n เป็นจำนวน 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--
แน่นอนจะไม่เคยอยู่ในฉัน class-- นี้

85
00:04:13,700 --> 00:04:18,709
ดำน้ำในลึกจริงๆใด ๆ
วิเคราะห์สิ่งที่ฉของ n คือ

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 คีบยกกำลังสองบวกทรัพยากร n

94
00:04:47,000 --> 00:04:49,350
ในการประมวลผลชุดข้อมูลขนาด n

95
00:04:49,350 --> 00:04:52,030
และเรามีสาม
อัลกอริทึมที่ทำงาน in-- ว่า

96
00:04:52,030 --> 00:04:58,300
จะขึ้นคีบ n ลบยืด 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
ฉันจริงๆเพียงแค่ต้องเหล่านี้ขึ้น
นี่เป็นตัวอย่างของจุดหนึ่ง

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
มันสามารถ run-- ก็สามารถใช้
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
และขั้นตอนวิธีการทำงานที่สาม
ในเพียงขี้อายของพันล้านขั้นตอน

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,

136
00:06:50,006 --> 00:06:52,380
และเพื่อให้เราจริงจะดู
ทุกขั้นตอนวิธีการเหล่านี้

137
00:06:52,380 --> 00:06:59,520
ว่าเป็นคำสั่งของ n
คีบหรือใหญ่-O ของ cubed n

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
คุณเคยเห็นอย่างแน่นอนโดยขณะนี้คือ
ฉีกจากสมุดโทรศัพท์

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
และเพื่อให้เป็น n ขนาดใหญ่ได้รับ
และมีขนาดใหญ่และ 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 log 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
หรือเวลาที่ชี้แจงซึ่ง
แม้แต่ C worse-- เพื่อที่ n

166
00:08:20,810 --> 00:08:24,670
ดังนั้นบางจำนวนคงที่ยกขึ้นไป
อำนาจของขนาดของการป้อนข้อมูล

167
00:08:24,670 --> 00:08:28,990
ดังนั้นหากมี 1,000-- ถ้า
การป้อนข้อมูลที่มีขนาด 1,000

168
00:08:28,990 --> 00:08:31,310
มันจะใช้เวลา C ถึงอำนาจ 1000

169
00:08:31,310 --> 00:08:33,559
มันมากเลวร้ายยิ่งกว่าเวลาพหุนาม

170
00:08:33,559 --> 00:08:35,030
>> ปัจจัยเวลาเป็นยิ่งแย่ลง

171
00:08:35,030 --> 00:08:37,760
และในความเป็นจริงมีจริงๆ
ขั้นตอนวิธีการที่มีอยู่เวลาที่สิ้นสุด

172
00:08:37,760 --> 00:08:43,740
เช่นที่เรียกว่าโง่ที่มี sort--
งานคือการสุ่มสับเปลี่ยนอาร์เรย์

173
00:08:43,740 --> 00:08:45,490
และจากนั้นตรวจสอบเพื่อดู
ไม่ว่าจะเป็นการเรียง

174
00:08:45,490 --> 00:08:47,589
และถ้ามันไม่ได้แบบสุ่ม
สับเปลี่ยนแถวอีกครั้ง

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
หวังว่าคุณจะไม่ได้เขียน
เวลาปัจจัยหรือไม่มีที่สิ้นสุด

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
ดังนั้นเราจึงมี example--
หรือสองตัวอย่าง here--

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
ดังนั้น example-- แรก
เรามีฟังก์ชั่น

188
00:09:20,050 --> 00:09:23,952
ที่เรียกว่า 4 สำหรับคุณที่
ใช้เวลามากมายขนาด 1,000

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
>> นี่คือตัวอย่างของหนึ่ง
algorithm-- เส้นเวลา

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
ในอาร์เรย์ของขนาด 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
>> คู่คำถามอย่างรวดเร็วสำหรับคุณ

229
00:11:08,270 --> 00:11:11,170
อะไรคือสิ่งที่ runtime--
ที่เลวร้ายที่สุดกรณีรันไทม์

230
00:11:11,170 --> 00:11:13,700
ของตัวอย่างนี้โดยเฉพาะของรหัส?

231
00:11:13,700 --> 00:11:17,420
ดังนั้นผมจึงมีวง 4 ที่นี่ที่ทำงาน
จากเจเท่ากับ 0 ทั้งหมดทางขึ้นไปยังม.

232
00:11:17,420 --> 00:11:21,980
และสิ่งที่ฉันเห็นที่นี่เป็นที่
ร่างกายของวงทำงานในเวลาคง

233
00:11:21,980 --> 00:11:24,730
ดังนั้นการใช้คำศัพท์ที่ว่า
เราได้พูดคุยแล้ว about-- สิ่งที่

234
00:11:24,730 --> 00:11:29,390
จะเป็นกรณีที่เลวร้ายที่สุด
รันไทม์ของขั้นตอนวิธีนี้หรือไม่?

235
00:11:29,390 --> 00:11:31,050
ใช้เป็นครั้งที่สอง

236
00:11:31,050 --> 00:11:34,270
ส่วนด้านในของวง
วิ่งในเวลาคง

237
00:11:34,270 --> 00:11:37,510
และส่วนที่ด้านนอกของ
ห่วงจะไปทำงานครั้งเมตร

238
00:11:37,510 --> 00:11:40,260
ดังนั้นสิ่งที่รันไทม์เลวร้ายที่สุดกรณีที่นี่?

239
00:11:40,260 --> 00:11:43,210
คุณคิดว่าใหญ่ของ O m?

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
เวลาที่เรามีนี้
วงในของวง

243
00:11:48,590 --> 00:11:50,905
เรามีห่วงด้านนอก
ที่ไหลจากศูนย์ถึงพี

244
00:11:50,905 --> 00:11:54,630
และเรามีห่วงด้านในที่ทำงาน
จากศูนย์ถึงพีและภายในของที่

245
00:11:54,630 --> 00:11:57,890
ผมว่าร่างกาย
ห่วงทำงานในเวลาคง

246
00:11:57,890 --> 00:12:02,330
ดังนั้นสิ่งที่รันไทม์เลวร้ายที่สุดกรณี
ของตัวอย่างนี้โดยเฉพาะของรหัส?

247
00:12:02,330 --> 00:12:06,140
ดีอีกครั้งที่เรามี
ห่วงนอกที่ทำงานครั้งหน้า

248
00:12:06,140 --> 00:12:09,660
และแต่ละซ้ำ time--
ของวงที่ค่อนข้าง

249
00:12:09,660 --> 00:12:13,170
เรามีห่วงด้านใน
ที่ยังทำงานครั้งหน้า

250
00:12:13,170 --> 00:12:16,900
และจากนั้นภายในที่มีคือ
ตัวอย่างเล็ก ๆ น้อย ๆ คงมี time--

251
00:12:16,900 --> 00:12:19,890
>> ดังนั้นหากเรามีห่วงด้านนอกที่
วิ่งครั้งภายในพีซึ่งเป็น

252
00:12:19,890 --> 00:12:22,880
ห่วงภายในที่
วิ่งพี times-- สิ่งที่เป็น

253
00:12:22,880 --> 00:12:26,480
ที่เลวร้ายที่สุดกรณีรันไทม์
ของตัวอย่างของรหัสนี้หรือไม่?

254
00:12:26,480 --> 00:12:30,730
คุณคิดว่าใหญ่โอพียืด?

255
00:12:30,730 --> 00:12:31,690
>> ฉันลอยด์ดั๊ก

256
00:12:31,690 --> 00:12:33,880
นี่คือ CS50

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