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

2
00:00:05,760 --> 00:00:08,900
>> டக் 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
தேர்வு மாதிரியான, இதுவரை,
சிறிய கண்டறிய குமிழி கண்டுபிடிக்க

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
ஏனெனில் அந்த சூழ்நிலையில்
நாங்கள் உண்மையில்

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
>> முக்கிய இதுவரை எங்கள் வழிமுறைகளை எந்தவொரு ஒன்றாக்க
இங்கே பிரிந்தது ஒன்றாக்க.

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
நாம் வரிசை கீழ் வரை
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 முறை பதிவு n.

52
00:02:48,410 --> 00:02:52,390
நாம் n உறுப்புகள் இல்லை, ஆனால்
இந்த மீண்டும் சேர்தலின் செயல்முறை

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 log,
n, சிறந்த வழக்கில் n log.

58
00:03:11,610 --> 00:03:13,960
>> நாம் இரண்டு பற்றி பேசினார்
நெறிமுறைகள் தேடி.

59
00:03:13,960 --> 00:03:16,230
எனவே நேரியல் தேடல் தேடி பற்றி.

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
அது அதை பயன்படுத்தி ஒரு முன்நிபந்தனை தான்
நீங்கள் மூலம் தேடும் அந்த வரிசையில்

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 log
ஒருபடி தேடல் 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 எதிராக,

84
00:04:24,030 --> 00:04:27,110
நீங்கள் வேலை மூலம் செல்ல வேண்டும்
முதலில் உங்கள் வரிசை வரிசைப்படுத்த எந்த

85
00:04:27,110 --> 00:04:32,010
பொறுத்து, அது குறைவாக இருக்கும்
வரிசைப்படுத்தப்பட்ட தேடி அளவை.

86
00:04:32,010 --> 00:04:35,250
>> நான் டக் லாயிட் நான், இந்த CS50 உள்ளது.

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