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
>> Bubble დალაგების, იდეა, რომ
ერთი სვოპ მიმდებარე წყვილი.

19
00:00:58,910 --> 00:01:01,730
ასე რომ, ეს არის გასაღები, რომელიც დაგეხმარებათ
მახსოვს განსხვავება აქ.

20
00:01:01,730 --> 00:01:04,920
შერჩევა დალაგების არის, ჯერჯერობით,
მოვძებნოთ smallest-- bubble

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
უარესი შემთხვევაში პერსპექტივაში დრო
of bubble sort არის n კვადრატში.

26
00:01:20,180 --> 00:01:23,476
საუკეთესო შემთხვევაში პერსპექტივაში დრო
of bubble sort არის n.

27
00:01:23,476 --> 00:01:25,350
იმის გამო, რომ სიტუაცია
ჩვენ არ რეალურად

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
>> In ჩასმა სახის,
ძირითადი იდეა აქ გადავიდა.

31
00:01:34,600 --> 00:01:36,630
სწორედ სიტყვით Insertion დალაგების.

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
უარესი პერსპექტივაში დრო
Insertion დალაგების არის n კვადრატში.

39
00:01:58,650 --> 00:02:02,380
საუკეთესო შემთხვევაში აწარმოებს დრო n.

40
00:02:02,380 --> 00:02:05,380
>> შერწყმა დალაგების სიტყვით
აქ არის გაყოფილი და შერწყმა.

41
00:02:05,380 --> 00:02:08,949
ჩვენ გაყოფილი სრული მასივი, თუ არა
ეს ექვსი ელემენტები, რვა ელემენტებს,

42
00:02:08,949 --> 00:02:13,790
10,000 ელემენტებს ჩვენ გაყოფილი იგი
ქვემოთ ნახევარი, ნახევარი, ნახევარი,

43
00:02:13,790 --> 00:02:17,720
სანამ ჩვენ გვაქვს ქვეშ მასივი
ო-ერთი ელემენტია მასივები.

44
00:02:17,720 --> 00:02:19,470
კომპლექტი n ერთ ელემენტს მასივები.

45
00:02:19,470 --> 00:02:22,640
ასე რომ, ჩვენ დავიწყეთ ერთი
1000-ელემენტს მასივი,

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 ჯერ შესვლა n.

52
00:02:48,410 --> 00:02:52,390
ჩვენ გვყავს n ელემენტები, მაგრამ
ამ recombining პროცესი

53
00:02:52,390 --> 00:02:56,960
იღებს შესვლა 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 შესვლა N უარეს შემთხვევაში,
N შესვლა 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
უარესი აწარმოებს დრო არის დიდი ო ო.

63
00:03:24,550 --> 00:03:27,610
ეს შეიძლება მიიღოს ჩვენთვის iterating
მასშტაბით თითოეული ელემენტის

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
საუკეთესო შემთხვევაში პერსპექტივაში დრო
ხაზოვანი ძებნა omega 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
შესვლა 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
გაცილებით უკეთესია, ვიდრე ხაზოვანი ძებნა
ძალით მყოფი log n წინააღმდეგ n,

84
00:04:24,030 --> 00:04:27,110
თქვენ უნდა გაიაროს მუშაობა
დახარისხება თქვენი მასივი პირველი, რომელიც

85
00:04:27,110 --> 00:04:32,010
შესაძლოა ეს ნაკლებად ეფექტური დამოკიდებულია
on ზომა iterating გადანაწილებული.

86
00:04:32,010 --> 00:04:35,250
>> მე Doug Lloyd, ეს არის CS50.

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