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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: ดังนั้นใน CS50 เราได้ครอบคลุม
จำนวนมากของโครงสร้างข้อมูลที่แตกต่างกัน

3
00:00:08,300 --> 00:00:09,180
ใช่มั้ย?

4
00:00:09,180 --> 00:00:11,420
เราได้เห็นอาร์เรย์และเชื่อมโยง
รายการและตารางแฮช

5
00:00:11,420 --> 00:00:15,210
และพยายามกองและการรอคิว

6
00:00:15,210 --> 00:00:17,579
นอกจากนี้เรายังจะได้เรียนรู้เล็ก ๆ น้อย ๆ
เกี่ยวกับต้นไม้และกองซากปรักหักพัง

7
00:00:17,579 --> 00:00:20,120
แต่จริงๆเหล่านี้ทั้งหมดเพียงจบ
ขึ้นเป็นรูปแบบในธีม

8
00:00:20,120 --> 00:00:22,840
มีจริงๆเหล่านี้
สี่ชนิดของความคิดพื้นฐาน

9
00:00:22,840 --> 00:00:25,190
ทุกอย่างอื่นที่สามารถต้มลงไป

10
00:00:25,190 --> 00:00:28,150
อาร์เรย์รายการที่เชื่อมโยง
ตารางแฮชและพยายาม

11
00:00:28,150 --> 00:00:30,720
และเหมือนที่ผมกล่าวว่ามี
มีรูปแบบที่พวกเขา

12
00:00:30,720 --> 00:00:32,720
แต่นี้สวย
มากไปที่จะสรุป

13
00:00:32,720 --> 00:00:38,140
ทุกสิ่งที่เรากำลังจะพูดคุย
เกี่ยวกับในชั้นเรียนในแง่ของซีนี้

14
00:00:38,140 --> 00:00:40,140
>> แต่วิธีการทำสิ่งเหล่านี้วัดขึ้นทั้งหมดใช่มั้ย?

15
00:00:40,140 --> 00:00:44,265
เราได้พูดคุยเกี่ยวกับข้อดีและข้อเสีย
ของแต่ละวิดีโอแยกพวกเขา

16
00:00:44,265 --> 00:00:46,390
แต่มีจำนวนมากของตัวเลข
ได้รับการโยนไปรอบ ๆ

17
00:00:46,390 --> 00:00:48,723
มีจำนวนมากของทั่วไปเป็น
ความคิดที่ได้รับการโยนไปรอบ ๆ

18
00:00:48,723 --> 00:00:51,950
ลองและรวบรวม
มันกลายเป็นเพียงที่เดียว

19
00:00:51,950 --> 00:00:55,507
ลองชั่งน้ำหนักข้อดีกับ
ข้อเสียและพิจารณา

20
00:00:55,507 --> 00:00:57,340
ซึ่งโครงสร้างข้อมูล
อาจจะมีข้อมูลที่ถูกต้อง

21
00:00:57,340 --> 00:01:01,440
โครงสร้างสำหรับสถานการณ์เฉพาะของคุณ
สิ่งที่ชนิดของข้อมูลที่คุณเก็บ

22
00:01:01,440 --> 00:01:06,625
คุณไม่จำเป็นต้องเสมอ
ใช้การแทรกเร็วสุดลบ

23
00:01:06,625 --> 00:01:10,761
และการค้นหาของ Trie ถ้าคุณจริงๆ
ไม่สนใจเกี่ยวกับการใส่และการลบ

24
00:01:10,761 --> 00:01:11,260
มากเกินไป

25
00:01:11,260 --> 00:01:13,968
หากคุณต้องการได้อย่างรวดเร็วเพียงแค่สุ่ม
การเข้าถึงอาร์เรย์อาจจะดีกว่า

26
00:01:13,968 --> 00:01:15,340
ดังนั้นขอกลั่นที่

27
00:01:15,340 --> 00:01:18,530
พูดคุยเกี่ยวกับแต่ละแห่งที่สี่
ชนิดที่สำคัญของโครงสร้างข้อมูล

28
00:01:18,530 --> 00:01:21,720
ที่เราได้พูดคุยเกี่ยวกับและ
เพียงแค่เห็นเมื่อพวกเขาอาจจะดี

29
00:01:21,720 --> 00:01:23,340
และเมื่อพวกเขาอาจจะไม่ดีดังนั้น

30
00:01:23,340 --> 00:01:24,610
ดังนั้นขอเริ่มต้นด้วยอาร์เรย์

31
00:01:24,610 --> 00:01:27,300
ดังนั้นการแทรกที่ชนิดของที่ไม่ดี

32
00:01:27,300 --> 00:01:31,350
>> แทรกในตอนท้ายของอาร์เรย์เป็น OK
ถ้าเรากำลังสร้างอาร์เรย์ที่เราไป

33
00:01:31,350 --> 00:01:33,570
แต่ถ้าเราต้องใส่
องค์ประกอบเข้ามาตรงกลาง

34
00:01:33,570 --> 00:01:35,550
คิดว่ากลับไปแทรก
เรียงลำดับมีจำนวนมาก

35
00:01:35,550 --> 00:01:37,510
ของการขยับเพื่อให้พอดีกับองค์ประกอบในการมี

36
00:01:37,510 --> 00:01:41,170
และดังนั้นถ้าเราจะใส่
ที่ใดก็ได้ แต่ในตอนท้ายของอาร์เรย์

37
00:01:41,170 --> 00:01:43,590
ที่อาจไม่ดีดังนั้น

38
00:01:43,590 --> 00:01:46,710
>> ในทำนองเดียวกันการลบเว้นแต่เรา
ลบจากสิ้นอาร์เรย์

39
00:01:46,710 --> 00:01:49,810
อาจจะยังไม่ได้ดังนั้นดีถ้า
เราไม่ต้องการที่จะออกจากช่องว่างที่ว่างเปล่า

40
00:01:49,810 --> 00:01:50,790
ซึ่งโดยปกติเราทำไม่ได้

41
00:01:50,790 --> 00:01:54,700
เราต้องการที่จะลบองค์ประกอบและ
แล้วเรียงลำดับของการทำให้มันสบายอีกครั้ง

42
00:01:54,700 --> 00:01:57,670
และเพื่อให้การลบองค์ประกอบจาก
อาร์เรย์ยังไม่ดีดังนั้น

43
00:01:57,670 --> 00:01:58,820
>> ค้นหา แต่เป็นที่ดี

44
00:01:58,820 --> 00:02:00,920
เรามีการเข้าถึงแบบสุ่ม
ค้นหาเวลาคง

45
00:02:00,920 --> 00:02:03,800
เราก็บอกว่าเจ็ดและที่เราจะไป
การย้ายอาร์เรย์เจ็ด

46
00:02:03,800 --> 00:02:05,907
เราพูดว่า 20 กับไปที่
การย้ายถิ่นฐานอาร์เรย์ 20

47
00:02:05,907 --> 00:02:07,240
เราไม่ได้มีการย้ำข้าม

48
00:02:07,240 --> 00:02:08,630
นั่นเป็นสิ่งที่ดีงาม

49
00:02:08,630 --> 00:02:11,020
>> อะเรย์ยังมีความสะดวกในการจัดเรียง

50
00:02:11,020 --> 00:02:14,040
ทุกครั้งที่เราได้พูดคุยเกี่ยวกับการเรียงลำดับ
ขั้นตอนวิธีการเช่นการจัดเรียงการเลือก

51
00:02:14,040 --> 00:02:18,820
จัดเรียงแทรกเรียงลำดับฟองผสาน
เรียงลำดับอาร์เรย์ที่เราใช้อยู่เสมอที่จะทำมัน

52
00:02:18,820 --> 00:02:21,860
เพราะอาร์เรย์จะสวยง่ายต่อการ
เรียงลำดับเทียบกับโครงสร้างข้อมูล

53
00:02:21,860 --> 00:02:22,970
เราได้เห็นเพื่อให้ห่างไกล

54
00:02:22,970 --> 00:02:24,320
>> พวกเขายังมีขนาดค่อนข้างเล็ก

55
00:02:24,320 --> 00:02:25,695
มีไม่มากพื้นที่พิเศษ

56
00:02:25,695 --> 00:02:29,210
คุณเพียงแค่ว่าการตั้งสำรองมากที่สุดเท่าที่
ตามที่คุณต้องการเก็บข้อมูลของคุณ

57
00:02:29,210 --> 00:02:30,320
และที่มันสวยมาก

58
00:02:30,320 --> 00:02:33,180
ดังนั้นพวกเขากำลังขนาดเล็กสวย
และมีประสิทธิภาพในทางที่

59
00:02:33,180 --> 00:02:36,000
แต่ข้อเสียอีก แต่
ที่พวกเขาได้รับการแก้ไขในขนาด

60
00:02:36,000 --> 00:02:38,630
เรามีการประกาศว่าวิธีการ
ขนาดใหญ่ที่เราต้องการอาร์เรย์ของเราที่จะเป็น

61
00:02:38,630 --> 00:02:39,940
และเราจะได้รับหนึ่งยิงไปที่มัน

62
00:02:39,940 --> 00:02:41,280
เราไม่สามารถเจริญเติบโตและหด

63
00:02:41,280 --> 00:02:44,582
>> ถ้าเราต้องการที่จะเติบโตหรือหดมันเรา
จำเป็นต้องประกาศอาร์เรย์ใหม่ทั้งหมด

64
00:02:44,582 --> 00:02:47,750
คัดลอกทุกองค์ประกอบของ
อาเรย์ครั้งแรกในแถวที่สอง

65
00:02:47,750 --> 00:02:51,410
และถ้าเราคาดคะเนว่า
เวลาที่เราต้องทำมันอีกครั้ง

66
00:02:51,410 --> 00:02:52,760
ไม่ดีดังนั้น

67
00:02:52,760 --> 00:02:58,750
ดังนั้นอาร์เรย์ไม่ให้เรามีความยืดหยุ่น
จะมีจำนวนตัวแปรขององค์ประกอบ

68
00:02:58,750 --> 00:03:01,320
>> กับรายการที่เชื่อมโยง
แทรกเป็นเรื่องง่ายสวย

69
00:03:01,320 --> 00:03:03,290
เราเพียงแค่ตะปูลงบนหน้า

70
00:03:03,290 --> 00:03:04,892
ลบยังเป็นเรื่องง่ายสวย

71
00:03:04,892 --> 00:03:06,100
เราต้องไปหาองค์ประกอบ

72
00:03:06,100 --> 00:03:07,270
ที่เกี่ยวข้องกับการค้นหาบาง

73
00:03:07,270 --> 00:03:10,270
>> แต่เมื่อคุณได้พบธาตุ
คุณกำลังมองหาสิ่งที่คุณต้องทำ

74
00:03:10,270 --> 00:03:12,830
เปลี่ยนเป็นตัวชี้
อาจจะเป็นสองถ้าคุณมี

75
00:03:12,830 --> 00:03:15,151
ที่เชื่อมโยง list-- ทวีคูณ
รายการที่เชื่อมโยง, rather--

76
00:03:15,151 --> 00:03:16,650
และจากนั้นคุณก็สามารถเพิ่มโหนด

77
00:03:16,650 --> 00:03:18,399
คุณไม่จำเป็นต้องที่จะเปลี่ยน
ทุกอย่างรอบตัว

78
00:03:18,399 --> 00:03:22,090
คุณเพียงแค่เปลี่ยนสองตัวชี้
เพื่อให้เป็นอย่างรวดเร็วสวย

79
00:03:22,090 --> 00:03:23,470
>> การค้นหาที่ไม่ดี แต่ใช่มั้ย?

80
00:03:23,470 --> 00:03:26,280
เพื่อที่เราจะได้พบกับ
องค์ประกอบในรายการที่เชื่อมโยง

81
00:03:26,280 --> 00:03:29,154
ไม่ว่าจะเป็นเดี่ยวหรือเชื่อมโยงทวีคูณ
เราจะต้องค้นหามันเชิงเส้น

82
00:03:29,154 --> 00:03:32,320
เราต้องเริ่มต้นที่จุดเริ่มต้นและ
ย้ายจุดสิ้นสุดหรือเริ่มต้นในตอนท้ายการย้าย

83
00:03:32,320 --> 00:03:33,860
ที่จุดเริ่มต้น

84
00:03:33,860 --> 00:03:35,474
เราไม่ได้มีการเข้าถึงแบบสุ่มอีกต่อไป

85
00:03:35,474 --> 00:03:37,265
ดังนั้นหากเรากำลังทำ
จำนวนมากของการค้นหาอาจจะ

86
00:03:37,265 --> 00:03:39,830
รายการที่เชื่อมโยงไม่ได้
ค่อนข้างดีสำหรับเรา

87
00:03:39,830 --> 00:03:43,750
>> พวกเขายังได้จริงๆ
ยากที่จะเรียงลำดับใช่มั้ย?

88
00:03:43,750 --> 00:03:45,666
วิธีเดียวที่คุณสามารถ
จริงๆเรียงลำดับรายการที่เชื่อมโยง

89
00:03:45,666 --> 00:03:47,870
คือการจัดเรียงที่คุณสร้างมัน

90
00:03:47,870 --> 00:03:50,497
แต่ถ้าคุณจัดเรียงตามที่คุณ
สร้างมันคุณไม่ได้

91
00:03:50,497 --> 00:03:51,830
การแทรกอย่างรวดเร็วอีกต่อไป

92
00:03:51,830 --> 00:03:53,746
คุณไม่ได้เป็นเพียงการตรึง
สิ่งบนด้านหน้า

93
00:03:53,746 --> 00:03:55,710
คุณต้องไปหา
จุดที่เหมาะสมที่จะนำมัน,

94
00:03:55,710 --> 00:03:57,820
แล้วแทรกของคุณ
กลายเป็นเพียงเกี่ยวกับการไม่ดีเท่า

95
00:03:57,820 --> 00:03:59,390
ขณะที่ใส่ลงในอาร์เรย์

96
00:03:59,390 --> 00:04:03,130
รายการที่เชื่อมโยงดังนั้นไม่ได้
เพื่อให้ที่ดีสำหรับการเรียงลำดับข้อมูล

97
00:04:03,130 --> 00:04:05,830
>> พวกเขายังสวยขนาดเล็กขนาดที่ชาญฉลาด

98
00:04:05,830 --> 00:04:08,496
รายการที่เชื่อมโยงเป็นทวีคูณเล็กน้อย
มีขนาดใหญ่กว่ารายการที่เชื่อมโยงโดยลำพัง

99
00:04:08,496 --> 00:04:10,620
ที่มีขนาดใหญ่กว่าเล็กน้อย
กว่าอาร์เรย์ แต่ก็ไม่ได้

100
00:04:10,620 --> 00:04:13,330
เป็นจำนวนมากของการสูญเสียพื้นที่

101
00:04:13,330 --> 00:04:18,730
ดังนั้นหากพื้นที่ที่พรีเมี่ยม แต่
ไม่ได้เป็นพรีเมี่ยมที่รุนแรงจริงๆ

102
00:04:18,730 --> 00:04:22,180
นี้อาจจะเป็นวิธีที่จะไป

103
00:04:22,180 --> 00:04:23,330
>> ตารางแฮช

104
00:04:23,330 --> 00:04:25,850
ใส่ลงในตารางแฮช
ตรงไปตรงมาเป็นธรรม

105
00:04:25,850 --> 00:04:26,980
มันเป็นกระบวนการที่สองขั้นตอน

106
00:04:26,980 --> 00:04:30,700
ครั้งแรกที่เราจำเป็นต้องเรียกใช้ข้อมูลของเราผ่าน
ฟังก์ชันแฮชที่จะได้รับรหัสกัญชา

107
00:04:30,700 --> 00:04:37,550
และจากนั้นเราใส่องค์ประกอบเข้าไปใน
ตารางแฮชที่ตั้งรหัสกัญชาที่

108
00:04:37,550 --> 00:04:40,879
>> ลบคล้ายกับรายการที่เชื่อมโยง
เป็นเรื่องง่ายเมื่อคุณพบองค์ประกอบ

109
00:04:40,879 --> 00:04:43,170
คุณต้องไปหามันเป็นครั้งแรก
แต่แล้วเมื่อคุณลบมัน

110
00:04:43,170 --> 00:04:45,128
คุณเพียงแค่ต้องแลกเปลี่ยน
คู่ของตัวชี้ที่

111
00:04:45,128 --> 00:04:47,250
ถ้าคุณกำลังใช้ผูกมัดแยกต่างหาก

112
00:04:47,250 --> 00:04:49,942
หากคุณกำลังใช้แหย่,
หรือถ้าคุณไม่ได้

113
00:04:49,942 --> 00:04:51,650
ใช้ผูกมัดเลย
ในตารางแฮชของคุณ

114
00:04:51,650 --> 00:04:53,040
การลบเป็นจริงเรื่องง่าย

115
00:04:53,040 --> 00:04:57,134
ทั้งหมดที่คุณต้องทำคือกัญชา
ข้อมูลและจากนั้นไปที่ตำแหน่งนั้น

116
00:04:57,134 --> 00:04:58,925
และสมมติว่าคุณทำไม่ได้
มีชนใด ๆ

117
00:04:58,925 --> 00:05:01,650
คุณจะสามารถลบได้อย่างรวดเร็ว

118
00:05:01,650 --> 00:05:04,930
>> ตอนนี้การค้นหาคือสิ่งที่
ได้รับเพียงเล็กน้อยที่ซับซ้อนมากขึ้น

119
00:05:04,930 --> 00:05:06,910
มันเป็นเรื่องเกี่ยวกับค่าเฉลี่ยที่ดีขึ้น
กว่ารายการที่เชื่อมโยง

120
00:05:06,910 --> 00:05:09,560
หากคุณกำลังใช้ผูกมัด,
คุณยังมีรายการที่เชื่อมโยง

121
00:05:09,560 --> 00:05:13,170
ซึ่งหมายความว่าคุณยังคงมี
ค้นหาความเสียหายรายการที่เชื่อมโยง

122
00:05:13,170 --> 00:05:18,390
แต่เนื่องจากคุณกำลังการเชื่อมโยงของคุณ
รายการและแยกมันมากกว่า 100 หรือ 1000

123
00:05:18,390 --> 00:05:25,380
หรือ n องค์ประกอบในตารางแฮชของคุณคุณ
รายการที่เชื่อมโยงทุกคนหนึ่งที่ n ขนาด

124
00:05:25,380 --> 00:05:27,650
พวกเขากำลังทั้งหมดที่มีขนาดเล็กอย่างมีนัยสำคัญ

125
00:05:27,650 --> 00:05:32,080
คุณได้รายการที่เชื่อมโยง n แทน
ของรายการที่เชื่อมโยงเป็นหนึ่งในขนาด n

126
00:05:32,080 --> 00:05:34,960
>> ดังนั้นนี้จริงของโลกอย่างต่อเนื่อง
ปัจจัยซึ่งโดยทั่วไปเรา

127
00:05:34,960 --> 00:05:39,730
ไม่ได้พูดคุยเกี่ยวกับความซับซ้อนในเวลานั้น
ไม่จริงสร้างความแตกต่างที่นี่

128
00:05:39,730 --> 00:05:43,020
ดังนั้นการค้นหายังคงเป็นเชิงเส้น
ค้นหาถ้าคุณกำลังใช้การผูกมัด,

129
00:05:43,020 --> 00:05:46,780
แต่ความยาวของรายการ
คุณกำลังค้นหาผ่าน

130
00:05:46,780 --> 00:05:50,080
เป็นอย่างมากที่สั้นมากโดยเปรียบเทียบ

131
00:05:50,080 --> 00:05:52,995
อีกครั้งถ้าเรียงลำดับเป็นของคุณ
เป้าหมายที่นี่ตารางแฮชของ

132
00:05:52,995 --> 00:05:54,370
อาจจะไม่ได้เป็นวิธีที่จะไป

133
00:05:54,370 --> 00:05:56,830
เพียงแค่ใช้อาร์เรย์ถ้าเรียงลำดับ
เป็นจริงที่สำคัญกับคุณ

134
00:05:56,830 --> 00:05:58,590
>> และพวกเขาสามารถใช้โทนเสียงดนตรีที่มีขนาด

135
00:05:58,590 --> 00:06:01,640
มันยากที่จะพูดว่า
ตารางแฮชมีขนาดเล็กหรือใหญ่

136
00:06:01,640 --> 00:06:04,110
เพราะมันขึ้นอยู่กับ
วิธีการที่มีขนาดใหญ่ตารางแฮชของคุณอยู่

137
00:06:04,110 --> 00:06:07,340
หากคุณเพียง แต่จะได้รับการจัดเก็บ
ห้าองค์ประกอบในตารางแฮชของคุณ

138
00:06:07,340 --> 00:06:10,620
และคุณมีตารางแฮช
10,000 องค์ประกอบในนั้น

139
00:06:10,620 --> 00:06:12,614
คุณอาจสูญเสียพื้นที่มาก

140
00:06:12,614 --> 00:06:15,030
คมชัดเป็นคุณยังสามารถ
มีตารางกัญชาขนาดเล็กมาก

141
00:06:15,030 --> 00:06:18,720
แต่มีขนาดเล็กตารางแฮชของคุณได้
อีกต่อไปแต่ละรายการที่เชื่อมโยงเหล่านั้น

142
00:06:18,720 --> 00:06:19,220
ได้รับ

143
00:06:19,220 --> 00:06:22,607
และเพื่อให้มีจริงๆวิธีที่จะไม่กำหนด
ว่าขนาดของตารางแฮชที่

144
00:06:22,607 --> 00:06:24,440
แต่ก็อาจจะมีความปลอดภัย
จะบอกว่ามันเป็นเรื่องทั่วไป

145
00:06:24,440 --> 00:06:27,990
จะมีขนาดใหญ่กว่าที่เชื่อมโยง
รายการจัดเก็บข้อมูลเดียวกัน

146
00:06:27,990 --> 00:06:30,400
แต่มีขนาดเล็กกว่า Trie

147
00:06:30,400 --> 00:06:32,720
>> และพยายามอยู่ที่สี่
ของโครงสร้างเหล่านี้

148
00:06:32,720 --> 00:06:34,070
ที่เราได้รับการพูดถึง

149
00:06:34,070 --> 00:06:36,450
ใส่ลงใน Trie มีความซับซ้อน

150
00:06:36,450 --> 00:06:38,400
มีจำนวนมากเป็นแบบไดนามิก
จัดสรรหน่วยความจำ

151
00:06:38,400 --> 00:06:40,780
โดยเฉพาะอย่างยิ่งที่จุดเริ่มต้น
ในขณะที่คุณกำลังเริ่มต้นในการสร้าง

152
00:06:40,780 --> 00:06:43,700
แต่มันถึงเวลาที่คงที่

153
00:06:43,700 --> 00:06:47,690
มันเป็นเพียงองค์ประกอบของมนุษย์
ที่นี่ที่ทำให้มันยุ่งยาก

154
00:06:47,690 --> 00:06:53,250
ต้องพบตัวชี้โมฆะ malloc
พื้นที่ไปที่นั่นอาจจะเป็นพื้นที่ malloc

155
00:06:53,250 --> 00:06:54,490
จากที่นั่นอีกครั้ง

156
00:06:54,490 --> 00:06:58,880
เรียงลำดับปัจจัยของการข่มขู่
คำแนะนำในการจัดสรรหน่วยความจำแบบไดนามิก

157
00:06:58,880 --> 00:07:00,130
เป็นอุปสรรค์ในการล้าง

158
00:07:00,130 --> 00:07:04,550
แต่เมื่อคุณได้ล้างมันแทรก
จริงมาค่อนข้างง่าย

159
00:07:04,550 --> 00:07:06,810
และแน่นอนเป็นเวลาที่คงที่

160
00:07:06,810 --> 00:07:07,680
>> การลบเป็นเรื่องง่าย

161
00:07:07,680 --> 00:07:11,330
ทั้งหมดที่คุณต้องทำคือการนำทางลง
คู่ของตัวชี้และโหนดฟรี

162
00:07:11,330 --> 00:07:12,420
เพื่อให้เป็นที่ดีงาม

163
00:07:12,420 --> 00:07:13,930
นอกจากนี้ยังมีการค้นหาอย่างรวดเร็ว

164
00:07:13,930 --> 00:07:16,780
ก็ขึ้นอยู่เฉพาะใน
ความยาวของข้อมูลของคุณ

165
00:07:16,780 --> 00:07:19,924
ดังนั้นหากข้อมูลทั้งหมดของคุณเป็น
ห้าสตริงตัวอักษร

166
00:07:19,924 --> 00:07:22,590
ตัวอย่างเช่นคุณเก็บห้า
สตริงตัวอักษรใน Trie ของคุณ

167
00:07:22,590 --> 00:07:25,439
จะใช้เวลาเพียงห้าขั้นตอน
พบสิ่งที่คุณกำลังมองหา

168
00:07:25,439 --> 00:07:28,480
ห้าเป็นเพียงปัจจัยคงดังนั้น
อีกครั้งแทรกลบและค้นหา

169
00:07:28,480 --> 00:07:31,670
ที่นี่มีตลอดเวลาอย่างต่อเนื่องได้อย่างมีประสิทธิภาพ

170
00:07:31,670 --> 00:07:34,880
>> สิ่งหนึ่งคือว่า Trie ของคุณอยู่
จริงชนิดของการเรียงอยู่แล้วใช่มั้ย?

171
00:07:34,880 --> 00:07:36,800
อาศัยอำนาจตามความของการที่เราอยู่
องค์ประกอบแทรก

172
00:07:36,800 --> 00:07:40,060
โดยไปที่ตัวอักษรตามตัวอักษรของ
ที่สำคัญหรือหลักโดยหลักของที่สำคัญ

173
00:07:40,060 --> 00:07:45,084
โดยทั่วไป Trie ของคุณสิ้นสุดขึ้นเป็น
เรียงชนิดของที่คุณสร้างมัน

174
00:07:45,084 --> 00:07:47,250
มันไม่ได้จริงๆที่ทำให้
ความรู้สึกที่จะคิดเกี่ยวกับการเรียงลำดับ

175
00:07:47,250 --> 00:07:49,874
ในลักษณะเดียวกับที่เราคิดเกี่ยวกับ
กับอาร์เรย์หรือรายการที่เชื่อมโยง

176
00:07:49,874 --> 00:07:51,070
หรือตารางแฮช

177
00:07:51,070 --> 00:07:54,780
แต่ในความรู้สึกบางอย่างของคุณ
Trie เรียงตามที่คุณไป

178
00:07:54,780 --> 00:07:58,630
>> ข้อเสียของหลักสูตรคือ
Trie อย่างรวดเร็วกลายเป็นขนาดใหญ่

179
00:07:58,630 --> 00:08:02,970
จากจุดทางแยกทุกครั้งที่คุณอาจจะ
ถ้า have-- สำคัญของคุณประกอบด้วยตัวเลข

180
00:08:02,970 --> 00:08:04,880
คุณมี 10 อื่น ๆ
สถานที่ที่คุณสามารถไปที่

181
00:08:04,880 --> 00:08:07,490
หมายความว่าทุกโหนด
มีข้อมูล

182
00:08:07,490 --> 00:08:11,440
เกี่ยวกับข้อมูลที่คุณต้องการในการจัดเก็บ
ที่โหนดที่บวก 10 ตัวชี้

183
00:08:11,440 --> 00:08:14,430
ซึ่งใน IDE CS50 เป็น 80 ไบต์

184
00:08:14,430 --> 00:08:17,220
ดังนั้นจึงเป็นอย่างน้อย 80 ไบต์สำหรับ
โหนดที่คุณสร้างทุก

185
00:08:17,220 --> 00:08:19,240
และที่ไม่ได้นับข้อมูล

186
00:08:19,240 --> 00:08:24,950
และถ้าโหนดของคุณ
ตัวอักษรแทนตัวเลข

187
00:08:24,950 --> 00:08:27,825
ตอนนี้คุณมี 26 ตัวชี้
จากทุกสถานที่

188
00:08:27,825 --> 00:08:32,007
และ 26 ครั้งที่ 8 น่าจะเป็น 200
ไบต์หรือสิ่งที่ต้องการ

189
00:08:32,007 --> 00:08:33,840
และคุณมีเงินทุน
และคุณสามารถ lowercase--

190
00:08:33,840 --> 00:08:35,381
ดูว่าฉันจะมีนี้ใช่มั้ย?

191
00:08:35,381 --> 00:08:37,500
โหนดของคุณจะได้รับจริงๆ
ขนาดใหญ่และอื่น ๆ ของ Trie

192
00:08:37,500 --> 00:08:40,470
ตัวเองโดยรวมสามารถ
ได้รับใหญ่มากเกินไป

193
00:08:40,470 --> 00:08:42,630
ดังนั้นหากพื้นที่เป็นที่สูง
พรีเ​​มี่ยมในระบบของคุณ

194
00:08:42,630 --> 00:08:45,830
Trie ไม่อาจจะเป็นวิธีที่ถูกต้อง
ไปแม้ว่าผลประโยชน์อื่น ๆ

195
00:08:45,830 --> 00:08:47,780
มาเล่น.

196
00:08:47,780 --> 00:08:48,710
ฉันลอยด์ดั๊ก

197
00:08:48,710 --> 00:08:50,740
นี่คือ CS50

198
00:08:50,740 --> 00:08:52,316