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

2
00:00:05,760 --> 00:00:08,900
>> DOUG 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
ดังนั้นเราจึงเริ่มต้นด้วยหนึ่ง
อาร์เรย์ 1,000 องค์ประกอบ

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 แต่
กระบวนการ recombining นี้

53
00:02:52,390 --> 00:02:56,960
ใช้เวลา log 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
ดังนั้นการค้นหาเชิงเส้นเป็นเรื่องเกี่ยวกับ iterating

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
มที่ดีที่สุดในกรณีที่เราจะพบทันที

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
log 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
อาจจะทำให้มีประสิทธิภาพน้อยขึ้นอยู่กับ
กับขนาดของ iterating เรียง

86
00:04:32,010 --> 00:04:35,250
>> ฉันลอยด์ดั๊กนี้เป็น CS50

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