1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [கருத்தரங்க: தொழில்நுட்ப செய்திகள்]

2
00:00:02,640 --> 00:00:04,630
[கென்னி யூ, ஹார்வர்ட் பல்கலைக்கழகம்]

3
00:00:04,630 --> 00:00:08,910
[இந்த CS50 உள்ளது.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi அனைவருக்கும், நான் கென்னி இருக்கிறேன். நான் தற்போது ஒரு இளைய படிக்கும் கணினி அறிவியல் தான்.

5
00:00:12,420 --> 00:00:17,310
நான் ஒரு முன்னாள் சிஎஸ் TF இருக்கிறேன், மற்றும் நான் ஒரு underclassman போது நான் இந்த கூறியிருபேன்

6
00:00:17,310 --> 00:00:19,380
நான் இந்த கருத்தரங்கில் தருகிறேன் ஏன் என்று.

7
00:00:19,380 --> 00:00:21,370
அதனால் நான் உங்களுக்கு பிடிக்கும் என்று நம்புகிறேன்.

8
00:00:21,370 --> 00:00:23,470
இந்த கருத்தரங்கு, தொழில் நுட்ப நேர்முக பற்றி

9
00:00:23,470 --> 00:00:26,650
மற்றும் அனைத்து என் வளங்கள், இந்த இணைப்பை காணலாம்

10
00:00:26,650 --> 00:00:32,350
இங்கே இந்த இணைப்பை, வளங்களை ஒரு ஜோடி.

11
00:00:32,350 --> 00:00:36,550
எனவே நான் சில பிரச்சினைகள், உண்மையில், பிரச்சினைகள் பட்டியலை கொடுத்தார்.

12
00:00:36,550 --> 00:00:40,800
நாம் குறிப்புகள் காணலாம் அங்கு ஒரு பொது வளங்கள் பக்கம்

13
00:00:40,800 --> 00:00:42,870
ஒரு பேட்டியில் தயாராக எப்படி,

14
00:00:42,870 --> 00:00:46,470
நீ ஒரு உண்மையான பேட்டி போது என்ன செய்ய வேண்டும் என்பது பற்றிய குறிப்புக்கள்,

15
00:00:46,470 --> 00:00:51,910
அத்துடன் எதிர்கால சிக்கல்கள் மற்றும் வளங்களை அணுக எப்படி.

16
00:00:51,910 --> 00:00:53,980
இது அனைத்து இணைய.

17
00:00:53,980 --> 00:00:58,290
மேலும் இந்த கருத்தரங்கு, ஒரு நிபந்தனைகள், முகவுரையில் வேண்டும்

18
00:00:58,290 --> 00:01:00,690
இந்த கூடாது - உங்கள் பேட்டி தயாரிப்பு

19
00:01:00,690 --> 00:01:02,800
இந்த பட்டியலில் மட்டுமே கூடாது.

20
00:01:02,800 --> 00:01:04,750
இது, ஒரு வழிகாட்டியாக இருக்கும் பொருள்

21
00:01:04,750 --> 00:01:08,890
நீங்கள் நிச்சயமாக, நான் உப்பு ஒரு தானிய சொல்வது எல்லாம் வேண்டும்

22
00:01:08,890 --> 00:01:14,620
ஆனால் நான் உங்கள் பேட்டி தயாரிப்பு நீ உதவுகிறது எல்லாம் பயன்படுத்த.

23
00:01:14,620 --> 00:01:16,400
>> நான் அடுத்த சில ஸ்லைடுகள் மூலம் துரிதப்படுத்த போகிறேன்

24
00:01:16,400 --> 00:01:18,650
எனவே, நாம் உண்மையான வழக்கு ஆய்வுகள் பெற முடியும்.

25
00:01:18,650 --> 00:01:23,630
ஒரு மென்பொருள் பொறியியல் postion ஒரு பேட்டியில் கட்டமைப்பு,

26
00:01:23,630 --> 00:01:26,320
பொதுவாக இது 30 முதல் 45 நிமிடங்கள்,

27
00:01:26,320 --> 00:01:29,810
நிறுவனம் பொறுத்து பல சுற்றுக்கள்.

28
00:01:29,810 --> 00:01:33,090
பெரும்பாலும் நீங்கள் ஒரு வெள்ளை பலகையில் குறியீட்டு.

29
00:01:33,090 --> 00:01:35,960
அதனால் இந்த மாதிரி, ஆனால் பெரும்பாலும் ஒரு சிறிய அளவில் ஒரு வெள்ளை பலகை.

30
00:01:35,960 --> 00:01:38,540
நீங்கள் ஒரு தொலைபேசி பேட்டியில் சிக்கல் இருந்தால், ஒருவேளை நீங்கள் பயன்படுத்தி

31
00:01:38,540 --> 00:01:44,030
collabedit அல்லது ஒரு Google ஆவணம் அல்லது அவர்கள் நீங்கள் குறியீட்டு வாழ முடியும்

32
00:01:44,030 --> 00:01:46,500
நீங்கள் தொலைபேசி மூலம் பேட்டி போது.

33
00:01:46,500 --> 00:01:48,490
ஒரு பேட்டியில் தன்னை பொதுவாக 2 அல்லது 3 பிரச்சினைகள் இல்லை

34
00:01:48,490 --> 00:01:50,620
உங்கள் கணினி அறிவியல் அறிவு சோதனை.

35
00:01:50,620 --> 00:01:54,490
இது கிட்டத்தட்ட கண்டிப்பாக குறியீட்டு உள்ளடக்கம்.

36
00:01:54,490 --> 00:01:59,540
நீங்கள் பார்ப்பீர்கள் என்று கேள்விகள் வகைகள் வழக்கமாக தரவு கட்டமைப்புகள் மற்றும் வழிமுறைகள் உள்ளன.

37
00:01:59,540 --> 00:02:02,210
மற்றும் பிரச்சினைகள் இந்த வகையான செய்து,

38
00:02:02,210 --> 00:02:07,830
அவர்கள் விரும்பினால், நீங்கள் கேட்க வேண்டும், என்ன நேரம் மற்றும் இடத்தை சிக்கலான, பெரிய ஓ இருக்கிறது?

39
00:02:07,830 --> 00:02:09,800
பெரும்பாலும் அவர்கள் உயர் நிலை கேள்விகளை கேட்க,

40
00:02:09,800 --> 00:02:12,530
எனவே, ஒரு கணினி வடிவமைப்பு

41
00:02:12,530 --> 00:02:14,770
எப்படி நீங்கள் உங்கள் குறியீடு வெளியே போட வேண்டும்?

42
00:02:14,770 --> 00:02:18,370
என்ன இடைமுகங்கள், என்ன வகுப்புகள், நீங்கள் உங்கள் கணினியில் என்ன தொகுதிகள் இல்லை,

43
00:02:18,370 --> 00:02:20,900
இந்த எப்படி ஒன்றாக தொடர்பு என்ன?

44
00:02:20,900 --> 00:02:26,130
எனவே தரவு கட்டமைப்புகள் மற்றும் நெறிமுறைகள் மற்றும் வடிவமைத்தல் அமைப்புகள்.

45
00:02:26,130 --> 00:02:29,180
>> எங்கள் வழக்கு ஆய்வுகள் ல் டைவ் முன் சில பொது குறிப்புகள்.

46
00:02:29,180 --> 00:02:32,300
நான் மிக முக்கிய விதி எப்போதும் சத்தமாக நினைத்து என்று.

47
00:02:32,300 --> 00:02:36,980
நேர்காணலில் உங்கள் சிந்தனை செயல்முறை காட்ட வாய்ப்பு இருக்க வேண்டும்.

48
00:02:36,980 --> 00:02:39,820
பேட்டி அளவிடுவதற்கு நேர்காணல் நிலையில் உள்ளது

49
00:02:39,820 --> 00:02:42,660
எப்படி என்று எப்படி நீங்கள் ஒரு சிக்கல் செல்ல.

50
00:02:42,660 --> 00:02:45,210
நீங்கள் என்ன செய்ய முடியும் மோசமான விஷயம் முழு பேட்டி முழுவதும் இருக்கும் அமைதியாக இருக்கிறது.

51
00:02:45,210 --> 00:02:50,090
என்று மட்டும் இல்லை நல்லது.

52
00:02:50,090 --> 00:02:53,230
நீங்கள் ஒரு கேள்வியை கொடுக்கப்பட்ட போது, நீங்கள் கேள்வி புரிந்து உறுதி செய்ய வேண்டும்.

53
00:02:53,230 --> 00:02:55,350
உங்கள் சொந்த வார்த்தைகளை மீண்டும் கேள்வியை மீண்டும்

54
00:02:55,350 --> 00:02:58,920
முயற்சி முழுமையான ஒரு சில எளிய சோதனை நேரங்களில் வேலை

55
00:02:58,920 --> 00:03:01,530
நீங்கள் கேள்வி புரிந்து என்பதை.

56
00:03:01,530 --> 00:03:05,510
ஒரு சில சோதனை வழக்குகள் மூலம் உழைக்கும் நீங்கள் இந்த பிரச்சனையை எப்படி தீர்ப்பது என்று ஒரு உள்ளுணர்வு அளிக்கும்.

57
00:03:05,510 --> 00:03:11,210
நீங்கள் கூட ஒரு சில முறைகள் நீங்கள் இந்த சிக்கலை தீர்க்க உதவும் கண்டறிய வேண்டும்.

58
00:03:11,210 --> 00:03:14,500
அவர்கள் பெரிய முனையில் அலுக்கவில்லை உள்ளது.

59
00:03:14,500 --> 00:03:17,060
அலுக்கவில்லை.

60
00:03:17,060 --> 00:03:19,060
நேர்முக சவால் ஆகும், ஆனால் நீங்கள் என்ன செய்ய முடியும் மோசமான விஷயம்,

61
00:03:19,060 --> 00:03:23,330
அமைதியாக இருப்பது கூடுதலாக, சரா விரக்தி வேண்டும்.

62
00:03:23,330 --> 00:03:27,410
நீங்கள் ஒரு பேட்டி என்று தோற்றத்தை கொடுக்க விரும்பவில்லை.

63
00:03:27,410 --> 00:03:33,960
ஒன்று என்று நீங்கள் - அதனால், பல மக்கள், அவர்கள் ஒரு பேட்டியில் போக போது,

64
00:03:33,960 --> 00:03:37,150
அவர்கள், முதல் சிறந்த தீர்வு காண முயற்சி முயற்சி

65
00:03:37,150 --> 00:03:39,950
போது உண்மையில், ஒரு glaringly தெளிவான தீர்வு வழக்கமாக உள்ளது.

66
00:03:39,950 --> 00:03:43,500
அது மெதுவாக இருக்கலாம், அது பயனற்றதாக இருக்கும், ஆனால் நீங்கள் அதை கூற வேண்டும்

67
00:03:43,500 --> 00:03:46,210
இப்போது நீங்கள் நல்ல வேலை இது ஒரு தொடக்க புள்ளியாக உள்ளது.

68
00:03:46,210 --> 00:03:48,270
மேலும், தீர்வு சுட்டிக்காட்டி வகையில், மெதுவான

69
00:03:48,270 --> 00:03:52,160
பெரிய ஓ சிக்கலான நேரத்தை அல்லது விண்வெளி சிக்கல்,

70
00:03:52,160 --> 00:03:54,450
நீங்கள் புரிந்துகொள்ள பேட்டி என்று நிரூபிக்கும் முடியும்

71
00:03:54,450 --> 00:03:57,510
இந்த பிரச்சினைகள் குறியீடு எழுதும் போது.

72
00:03:57,510 --> 00:04:01,440
எனவே முதல் எளிய வழிமுறையை கொண்டு வர பயப்படவேண்டாம்

73
00:04:01,440 --> 00:04:04,950
பின்னர் அங்கு இருந்து நல்ல வேலை.

74
00:04:04,950 --> 00:04:09,810
எந்த கேள்விகளுக்கு இதுவரை? சரி.

75
00:04:09,810 --> 00:04:11,650
>> எனவே நாம் நமது முதல் பிரச்சனை தொடர்பாக டைவ்.

76
00:04:11,650 --> 00:04:14,790
"N முழுஎண்களின் வரிசை நிலையில், வரிசை shuffles என்று ஒரு செயல்பாடு எழுத

77
00:04:14,790 --> 00:04:20,209
n முழுஎண்களின் அனைத்து வரிசைமாற்றங்கள் சமமாக வாய்ப்பு உள்ளது என்று இந்த இடத்தில். "

78
00:04:20,209 --> 00:04:23,470
நீங்கள் இன்னும் ஒரு சீரற்ற முழு ஜெனரேட்டர் வேண்டும் கருதி

79
00:04:23,470 --> 00:04:30,980
அந்த அரை வீச்சு, 0 இருந்து நான் ஒரு வரம்பில் ஒரு முழு எண் உருவாக்குகிறது.

80
00:04:30,980 --> 00:04:32,970
எல்லோரும் இந்த கேள்வியை புரிந்து?

81
00:04:32,970 --> 00:04:39,660
நான் உன்னை n முழுஎண்களின் வரிசை கொடுக்க, நான் உங்களுக்கு குலைப்பதை அதை விரும்பவில்லை.

82
00:04:39,660 --> 00:04:46,050
என் அடைவில், நான் என்ன என்பதை ஒரு சில திட்டங்கள் எழுதினார்.

83
00:04:46,050 --> 00:04:48,910
நான், குலைப்பதை 20 தனிமங்களின் வரிசை போகிறேன்

84
00:04:48,910 --> 00:04:52,490
-10 இருந்து +9 வேண்டும்,

85
00:04:52,490 --> 00:04:57,050
நான் இந்த மாதிரி ஒரு பட்டியல் வெளியனுப்புவதில் வேண்டும்.

86
00:04:57,050 --> 00:05:02,890
இந்த என் வரிசைப்படுத்தப்பட்ட உள்ளீடு வரிசை உள்ளது, மற்றும் நீ கலக்கு அதை விரும்பவில்லை.

87
00:05:02,890 --> 00:05:07,070
நாம் மீண்டும் அதை செய்கிறேன்.

88
00:05:07,070 --> 00:05:13,780
எல்லோரும் கேள்வி புரிந்து? சரி.

89
00:05:13,780 --> 00:05:16,730
அதை நீங்கள் தான்.

90
00:05:16,730 --> 00:05:21,220
சில யோசனைகள் என்ன? நீங்கள் n ^ 2, n log n, n அதை செய்ய முடியும்?

91
00:05:21,220 --> 00:05:34,400
பரிந்துரைகள் திறக்க.

92
00:05:34,400 --> 00:05:37,730
சரி. எம்மி பரிந்துரைத்த அதனால் ஒரு யோசனை,,

93
00:05:37,730 --> 00:05:45,300
முதல் 0 20 ஒரு சீரற்ற எண், சீரற்ற முழு, ஒரு வரம்பில் கணக்கிட வேண்டும்.

94
00:05:45,300 --> 00:05:49,840
எனவே எங்கள் அணி 20 நீளம் உள்ளது என்று வைத்து கொள்வோம்.

95
00:05:49,840 --> 00:05:54,800
20 உறுப்புகள் எங்கள் வரைபடம்,

96
00:05:54,800 --> 00:05:58,560
இந்த எங்கள் உள்ளீடு வரிசை ஆகும்.

97
00:05:58,560 --> 00:06:04,590
இப்போது, அவரது கருத்து, ஒரு புதிய அணியை உருவாக்க வேண்டும்

98
00:06:04,590 --> 00:06:08,440
இந்த வெளியீடு வரிசை இருக்கும்.

99
00:06:08,440 --> 00:06:12,880
நான் ரேண்ட் வந்தார் அடிப்படையில் -

100
00:06:12,880 --> 00:06:17,580
நான் இருந்தால் அதனால், 17, தான் சொல்கிறேன்

101
00:06:17,580 --> 00:06:25,640
முதல் நிலைக்கு 17 உறுப்பு நகலெடுக்க.

102
00:06:25,640 --> 00:06:30,300
இப்போது நாங்கள் நீக்க வேண்டும் - நாம் இங்கே அனைத்து கூறுகளும் மாற்ற வேண்டும்

103
00:06:30,300 --> 00:06:36,920
மேல் நாம் முடிவில் ஒரு இடைவெளி மற்றும் நடுத்தர எந்த ஓட்டைகள் என்று.

104
00:06:36,920 --> 00:06:39,860
இப்போது நாம் செயல்முறை மீண்டும்.

105
00:06:39,860 --> 00:06:46,360
இப்போது நாம் 0 மற்றும் 19 இடையேயான ஒரு புதிய சீரற்ற முழு எடுக்க.

106
00:06:46,360 --> 00:06:52,510
நாம் இங்கே ஒரு புதிய நான் இல்லை, நாம் இந்த நிலையில் இந்த உறுப்பு நகலெடுக்க.

107
00:06:52,510 --> 00:07:00,960
பின் நாம் பொருட்களை மாற்ற நாம் நமது முழு புதிய வரிசை வரை நாம் செயல்முறை மீண்டும்.

108
00:07:00,960 --> 00:07:05,890
இந்த வழிமுறையின் ரன் நேரம் என்ன?

109
00:07:05,890 --> 00:07:08,110
சரி, இந்த பாதிப்பை கருத்தில் கொள்வோம்.

110
00:07:08,110 --> 00:07:10,380
நாம் ஒவ்வொரு உறுப்பு மாற்றுவதால்.

111
00:07:10,380 --> 00:07:16,800
இந்த நான் நீக்க போது, நாம் இடது அதற்கு பிறகு அனைத்து தனிமங்களுக்கு.

112
00:07:16,800 --> 00:07:21,600
மற்றும் ஒரு ஓ (n) விலை

113
00:07:21,600 --> 00:07:26,100
ஏனெனில் நாம் முதல் உறுப்பு நீக்க வேண்டும்?

114
00:07:26,100 --> 00:07:29,670
எனவே ஒவ்வொரு நீக்க, நாம் நீக்க -

115
00:07:29,670 --> 00:07:32,170
ஒவ்வொரு நீக்கம், ஒரு ஓ (n), செயல்பாடு நிறைவு

116
00:07:32,170 --> 00:07:41,520
நாம் நீக்குதல் n முதல் மற்றும், இந்த ஒரு ஓ (n ^ 2) குலைப்பதை வழிவகுக்கிறது.

117
00:07:41,520 --> 00:07:49,550
சரி. அதனால் நல்ல துவக்கம். நல்ல துவக்கம்.

118
00:07:49,550 --> 00:07:55,290
>> மற்றொரு கருத்து, னத் கலக்கு என்று ஏதாவது பயன்படுத்த வேண்டும்

119
00:07:55,290 --> 00:07:57,540
அல்லது ஃபிஷர்-யேட்ஸ் குலைப்பதை.

120
00:07:57,540 --> 00:07:59,630
அது உண்மையில் ஒரு நேரியல் நேரம் குலைப்பதை தான்.

121
00:07:59,630 --> 00:08:02,200
மற்றும் யோசனை மிகவும் ஒத்ததாக இருக்கிறது.

122
00:08:02,200 --> 00:08:05,160
மீண்டும், நாம், நம் உள்ளீடு வரிசை உள்ளது

123
00:08:05,160 --> 00:08:08,580
ஆனால் அதற்கு பதிலாக நம் உள்ளீடு / வெளியீடு இரண்டு அணிகளை பயன்படுத்தி,

124
00:08:08,580 --> 00:08:13,590
நாம், நமது மாற்றி மாற்றி கலக்கப்பட்டு பகுதியை கண்காணிப்பதற்கு அணி முதல் பகுதியை பயன்படுத்த

125
00:08:13,590 --> 00:08:18,400
நாம் கண்காணிக்க, மற்றும் நாம் unshuffled பகுதி எங்கள் அணியின் மற்ற விட்டு.

126
00:08:18,400 --> 00:08:24,330
எனவே இங்கே நான் சொல்லுகிறேன். நாம் தொடங்குகின்றன - நாம் ஒரு நான் தேர்வு,

127
00:08:24,330 --> 00:08:30,910
0 முதல் 20 வரிசையை.

128
00:08:30,910 --> 00:08:36,150
நமது தற்போதைய சுட்டிக்காட்டி முதல் குறியீட்டு சுட்டி காட்டியது.

129
00:08:36,150 --> 00:08:39,590
நாம் சில நான் இங்கே தேர்வு

130
00:08:39,590 --> 00:08:42,740
இப்போது நாம் பரிமாறிக்கொள்ளலாம்.

131
00:08:42,740 --> 00:08:47,690
இந்த 5 மற்றும் இந்த 4 என்று நீங்கள்

132
00:08:47,690 --> 00:08:57,150
இதன் விளைவாக வரிசை இங்கே 5 இங்கே மற்றும் 4 சாப்பிடும்.

133
00:08:57,150 --> 00:09:00,390
இப்போது நாம் இங்கே ஒரு மார்க்கர் கவனிக்க.

134
00:09:00,390 --> 00:09:05,770
இடது எல்லாம், மாற்றி மாற்றி கலக்கப்பட்டு

135
00:09:05,770 --> 00:09:15,160
வலது எல்லாவற்றையும் unshuffled.

136
00:09:15,160 --> 00:09:17,260
இப்போது நாம் செயல்முறை மீண்டும் முடியாது.

137
00:09:17,260 --> 00:09:25,210
நாம் இப்போது 1 மற்றும் 20 ஆகியவற்றுக்கு இடையே ஒரு சீரற்ற குறியீட்டு தேர்வு.

138
00:09:25,210 --> 00:09:30,650
அதனால் நான் இங்கே நமது புதிய நினைக்கிறேன்.

139
00:09:30,650 --> 00:09:39,370
இப்போது நாம் இங்கே நமது தற்போதைய புதிய நிலையில் இந்த நான் பரிமாறிக்கொள்ளலாம்.

140
00:09:39,370 --> 00:09:44,790
எனவே நாம் ஒரு இப்படி முன்னும் பின்னுமாக மாற்றம்.

141
00:09:44,790 --> 00:09:51,630
எனக்கு அது இன்னும் உறுதியான செய்ய குறியீடு கொண்டு வரவும் விட.

142
00:09:51,630 --> 00:09:55,290
நாம் நான் நம்முடைய தேர்வு தொடங்க -

143
00:09:55,290 --> 00:09:58,370
நான் 0 சமமானதாக நாம் தொடங்க, நாம் ஒரு சீரற்ற இடம் j தேர்வு

144
00:09:58,370 --> 00:10:02,420
வரிசைக்கு unshuffled பகுதியில், நான் n-1.

145
00:10:02,420 --> 00:10:07,280
நான் இங்கே இருக்கிறேன் என்றால், இங்கே மற்றும் வரிசை மற்ற இடையே ஒரு சீரற்ற குறியீட்டு தேர்வு

146
00:10:07,280 --> 00:10:12,410
நாம் பரிமாறிக்கொள்ளலாம்.

147
00:10:12,410 --> 00:10:17,550
இந்த குலைப்பதை உங்கள் வரிசை தேவையான அனைத்து குறியீடு உள்ளது.

148
00:10:17,550 --> 00:10:21,670
எந்த கேள்விகள்?

149
00:10:21,670 --> 00:10:25,530
>> சரி, ஒரு கேள்வி தேவை, ஏன் இந்த சரியான உள்ளது?

150
00:10:25,530 --> 00:10:28,360
ஏன் ஒவ்வொரு வரிசைமாற்ற சமமாக உள்ளது?

151
00:10:28,360 --> 00:10:30,410
நான், இந்த ஆதாரம் மூலம் போக மாட்டேன்

152
00:10:30,410 --> 00:10:35,970
ஆனால் கணினி அறிவியல் பல பிரச்சினைகள் தூண்டல் மூலம் நிரூபிக்கப்பட்டுள்ளது.

153
00:10:35,970 --> 00:10:38,520
எப்படி பல தூண்டல் தெரிந்திருந்தால்?

154
00:10:38,520 --> 00:10:40,590
சரி. Cool.

155
00:10:40,590 --> 00:10:43,610
எனவே, எளிய அறிமுக இந்த வழிமுறையை சரியான நிரூபிக்க முடியும்

156
00:10:43,610 --> 00:10:49,540
உங்கள் அறிமுக கருதுகோள் என்று அங்கு, என

157
00:10:49,540 --> 00:10:53,290
என் குலைப்பதை ஒவ்வொரு வரிசைமாற்ற சமமாக வாய்ப்பு கொடுக்கிறது

158
00:10:53,290 --> 00:10:56,120
வரை முதல் நான் உறுப்புகளை.

159
00:10:56,120 --> 00:10:58,300
இப்போது, நான் + 1 கருதுகின்றனர்.

160
00:10:58,300 --> 00:11:02,550
நாம் நமது குறியீட்டு j இடமாற்றம் தேர்வு மூலம்,

161
00:11:02,550 --> 00:11:05,230
, மற்றும் நீங்கள் விவரங்களை வேலை - இந்த வழிவகுக்கிறது

162
00:11:05,230 --> 00:11:07,390
இந்த வழிமுறை கொடுக்கிறது ஏன் குறைந்தது ஒரு முழு ஆதாரம்

163
00:11:07,390 --> 00:11:12,800
சமமான வாய்ப்பு நிகழ்தகவு ஒவ்வொரு வரிசைமாற்ற.

164
00:11:12,800 --> 00:11:15,940
>> சரி, அடுத்த பிரச்சனை.

165
00:11:15,940 --> 00:11:19,170
எனவே ", எதிர்மறை, பூஜ்ஜியம், நேர் முழு எண்கள் ஒரு வரிசை, கொடுக்கப்பட்ட

166
00:11:19,170 --> 00:11:21,290
அதிகபட்ச தொகையை கணக்கிட்டு ஒரு செயல்பாடு எழுத

167
00:11:21,290 --> 00:11:24,720
உள்ளீடு வரிசைக்கு எந்த continueous subarray வேண்டும். "

168
00:11:24,720 --> 00:11:28,370
இங்கே ஒரு எடுத்துக்காட்டாக, அனைத்து எண்கள் நேர்மறை எங்கே வழக்கில், தான்

169
00:11:28,370 --> 00:11:31,320
பின்னர் தற்போது சிறந்த தேர்வு முழு வரிசை எடுத்து உள்ளது.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, 10 சமமாக.

171
00:11:34,690 --> 00:11:36,780
நீங்கள் அங்கு சில எதிர்மறைகளை போது,

172
00:11:36,780 --> 00:11:38,690
இந்த வழக்கில் நாங்கள் தான் முதல் இரண்டு வேண்டும்

173
00:11:38,690 --> 00:11:44,590
-1 மற்றும் / அல்லது -3 தேர்வு எங்கள் கூட்டுத்தொகையாக கீழே கொண்டுவரும் என்பதால்.

174
00:11:44,590 --> 00:11:48,120
சில நேரங்களில் நாம் வரிசை மத்தியில் தொடங்க வேண்டும்.

175
00:11:48,120 --> 00:11:53,500
சில நேரங்களில் நாம் ஒன்றுமே தேர்வு செய்ய வேண்டும்; இது எதையும் எடுக்க சிறந்ததாகும்.

176
00:11:53,500 --> 00:11:56,490
மற்றும் சில நேரங்களில் அது, இலையுதிர் எடுத்து நல்லது

177
00:11:56,490 --> 00:12:07,510
அதை பிறகு தான் சூப்பர் பெரிய காரணம். எந்த கருத்துக்கள் மிகவும்?

178
00:12:07,510 --> 00:12:10,970
(மாணவர், புரிந்து) >> சரி.

179
00:12:10,970 --> 00:12:13,560
நான் -1 வேண்டாம் என்று நினைக்கிறேன்.

180
00:12:13,560 --> 00:12:16,170
பின்னர் அல்லது நான் 1000 மற்றும் 20,000, தேர்வு

181
00:12:16,170 --> 00:12:18,630
அல்லது நான் 3 பில்லியன் தேர்வு.

182
00:12:18,630 --> 00:12:20,760
நல்ல, சிறந்த தேர்வாக அனைத்து எண்களை எடுத்து உள்ளது.

183
00:12:20,760 --> 00:12:24,350
இந்த -1, எதிர்மறை இருந்தும்,

184
00:12:24,350 --> 00:12:31,340
முழு தொகையை நான் -1 கொள்ள முடியவில்லை விட.

185
00:12:31,340 --> 00:12:36,460
நான் முன்னர் குறிப்பிட்ட குறிப்புகள் ஒரு தெளிவாக வெளிப்படையாக கூற வேண்டும்

186
00:12:36,460 --> 00:12:40,540
முதல் மற்றும் முரட்டு தீர்வு.

187
00:12:40,540 --> 00:12:44,340
இந்த பிரச்சனையில் முரட்டு தீர்வு என்ன? அப்படியா?

188
00:12:44,340 --> 00:12:46,890
[ஜேன்] சரி, நான் முரட்டு தீர்வு என்று

189
00:12:46,890 --> 00:12:52,600
அனைத்து சேர்க்கைகள் (புரிந்து) வரை சேர்க்க வேண்டும்.

190
00:12:52,600 --> 00:12:58,250
[யு] சரி. அதனால் ஜேன் யோசனை ஒவ்வொரு சாத்தியமான எடுத்து உள்ளது -

191
00:12:58,250 --> 00:13:01,470
நான் paraphrasing நான் - ஒவ்வொரு சாத்தியமான தொடர் subarray எடுத்து உள்ளது,

192
00:13:01,470 --> 00:13:07,840
அதன் தொகை கணக்கீடு, மற்றும் அனைத்து தொடர் subarrays அதிகபட்ச எடுத்து.

193
00:13:07,840 --> 00:13:13,310
என்ன தனிப்பட்ட என் உள்ளீடு வரிசையில் ஒரு subarray அடையாளம்?

194
00:13:13,310 --> 00:13:17,380
நான் என்ன இரண்டு விஷயங்கள் வேண்டும், போன்ற? அப்படியா?

195
00:13:17,380 --> 00:13:19,970
(மாணவர், புரிந்து) >> வலது.

196
00:13:19,970 --> 00:13:22,130
ஒரு குறைந்த குறியீட்டு மற்றும் ஒரு மேல் வரம்பையே குறியீட்டு மீது கட்டப்படுகிறது

197
00:13:22,130 --> 00:13:28,300
தனிப்பட்ட ஒரு தொடர்ச்சியான subarray தீர்மானிக்கிறது.

198
00:13:28,300 --> 00:13:31,400
[பெண் மாணவர்] நாம் அது தனிப்பட்ட எண்கள் ஒரு வரிசையில் தான் மதிப்பீடு என்ன?

199
00:13:31,400 --> 00:13:34,280
[யு] இல்லை அவள் கேள்விக்கு எனவே, நாங்கள் எங்கள் அணி அனுமானித்து -

200
00:13:34,280 --> 00:13:39,000
எங்கள் அணி அனைத்து தனிப்பட்ட எண்கள், மற்றும் பதில் இல்லை.

201
00:13:39,000 --> 00:13:43,390
>> நாம் நம் முரட்டு தீர்வு, தொடக்கத்தில் / முடிவில் குறியீடுகள் பயன்படுத்தினால்

202
00:13:43,390 --> 00:13:47,200
தனிப்பட்ட எமது தொடர்ச்சியான subarray தீர்மானிக்கிறது.

203
00:13:47,200 --> 00:13:51,680
நாம் அனைத்து தொடக்க உள்ளீடுகளுக்கு கூறு என்றால்,

204
00:13:51,680 --> 00:13:58,320
மற்றும் அனைத்து இறுதியில் உள்ளீடுகளுக்கு> அல்லது = தொடங்க, மற்றும் <n க்கு

205
00:13:58,320 --> 00:14:05,570
நீங்கள் தொகை கணக்கீடு, பின்னர் நாம் இதுவரை பார்த்த அதிகபட்ச தொகையை எடுத்து.

206
00:14:05,570 --> 00:14:07,880
இந்த தெளிவாக உள்ளது?

207
00:14:07,880 --> 00:14:12,230
இந்த தீர்வு பெரிய ஓ என்ன?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
மிக ^ 2 n.

210
00:14:18,860 --> 00:14:25,250
, நாம் 0 இருந்து n க்கு கூறு என்பதை கவனத்தில்

211
00:14:25,250 --> 00:14:27,520
அதனால் லூப் தான்.

212
00:14:27,520 --> 00:14:35,120
நாம் லூப், கிட்டத்தட்ட தொடக்கத்தில் இருந்து முடிவு வரை மீண்டும் இன்னொரு கூறு.

213
00:14:35,120 --> 00:14:37,640
இப்போது, அந்த நேரத்தில், நாம், ஒவ்வொரு நுழைவு வரை தொகையிடும் வேண்டும்

214
00:14:37,640 --> 00:14:43,810
அதனால் லூப் மற்றொரு. எனவே நாங்கள் மூன்று சுழல்கள் ஒரு காக்கப்பட்ட, n ^ 3 வேண்டும்.

215
00:14:43,810 --> 00:14:46,560
சரி. இந்த தொடக்க புள்ளியாக செல்கிறது.

216
00:14:46,560 --> 00:14:53,180
எங்கள் தீர்வு n ^ 3 விட மோசமாக உள்ளது.

217
00:14:53,180 --> 00:14:55,480
அனைவரும் முரட்டு தீர்வு புரிந்து?

218
00:14:55,480 --> 00:14:59,950
>> சரி. ஒரு நல்ல தீர்வு டைனமிக் நிரலாக்க என்று ஒரு யோசனை பயன்படுத்துகிறது.

219
00:14:59,950 --> 00:15:03,040
நீங்கள் CS124 எடுத்து இருந்தால், அது, நெறிமுறைகள் மற்றும் தரவு கட்டமைப்புகள் இல்லை

220
00:15:03,040 --> 00:15:05,680
இந்த தொழில்நுட்பம் மிகவும் பழக்கமான மாறும்.

221
00:15:05,680 --> 00:15:12,190
மற்றும் யோசனை, முதல் சிறிய பிரச்சினைகளுக்கு தீர்வுகளை கட்டமைக்க முயற்சி.

222
00:15:12,190 --> 00:15:17,990
தொடக்க மற்றும் முடிவு: இது நான் என்ன, நாம் தற்போது இரண்டு விஷயங்களை பற்றி கவலைப்பட வேண்டும்.

223
00:15:17,990 --> 00:15:29,340
அந்த எரிச்சலூட்டும் தான். நாம் அந்த அளவுருக்கள் ஒரு விடுபட முடியும் என்றால் என்ன?

224
00:15:29,340 --> 00:15:32,650
நாங்கள் எங்கள் உண்மையான பிரச்சினை கொடுக்க, - ஒரு யோசனை உள்ளது

225
00:15:32,650 --> 00:15:37,470
ஒரு வரம்பில் எந்த subarray அதிகபட்ச தொகை [ஓ, n-1] காணலாம்.

226
00:15:37,470 --> 00:15:47,400
இப்போது நாம், நமது தற்போதைய குறியீட்டு நான், நாம் என்று ஒரு புதிய subproblem, வேண்டும்

227
00:15:47,400 --> 00:15:52,520
நாம் அங்கு முடிவுக்கு வேண்டும் என்று. எங்கள் subarray தற்போதைய அட்டவணை இறுதி வேண்டும்.

228
00:15:52,520 --> 00:15:57,640
மீதமுள்ள பிரச்சனை எனவே, அங்கு நாங்கள் எங்கள் subarray தொடங்க வேண்டும்?

229
00:15:57,640 --> 00:16:05,160
இந்த உணர்வு ஏற்படுத்தும்? சரி.

230
00:16:05,160 --> 00:16:12,030
அதனால் நான் இந்த வரை குறியாக்கம், என்ன அர்த்தம் பாருங்கள் நாம்.

231
00:16:12,030 --> 00:16:16,230
Codirectory உள்ள, subarray என்று ஒரு திட்டத்தை, அங்கு

232
00:16:16,230 --> 00:16:19,470
இது, பொருட்களை எண்ணிக்கை ஆகும்

233
00:16:19,470 --> 00:16:25,550
அது என் மாற்றி மாற்றி கலக்கப்பட்டு பட்டியலில் அதிகபட்ச subarray தொகையை கொடுக்கிறது.

234
00:16:25,550 --> 00:16:29,920
இந்த வழக்கில், எங்கள் அதிகபட்ச subarray 3.

235
00:16:29,920 --> 00:16:34,850
என்று மட்டும் 2 மற்றும் 1 பயன்படுத்தி எடுக்கப்பட்ட.

236
00:16:34,850 --> 00:16:38,050
அதை மீண்டும் இயக்க வேண்டும். இது 3 தான்.

237
00:16:38,050 --> 00:16:40,950
ஆனால் இந்த நேரத்தில், நாம் 3 கிடைத்தது எப்படி கவனிக்க.

238
00:16:40,950 --> 00:16:46,690
நாம் எடுத்து - நாம் வெறும் 3 தன்னை எடுத்து

239
00:16:46,690 --> 00:16:49,980
அது இருபுறமும் எதிர்மறைகளை சூழப்பட்ட ஏனெனில்,

240
00:16:49,980 --> 00:16:55,080
ஒரு தொகை <3 கொண்டுவரும் எந்த.

241
00:16:55,080 --> 00:16:57,820
10 பொருட்கள் இயங்க அனுமதிக்க.

242
00:16:57,820 --> 00:17:03,200
இது 7 தான் இந்த நேரத்தில், நாம் முன்னணி 3 மற்றும் 4 எடுத்து.

243
00:17:03,200 --> 00:17:09,450
இந்த முறை 8, நாங்கள் 1, 4 மற்றும் 3 எடுத்து அந்த பெற.

244
00:17:09,450 --> 00:17:16,310
நீ எப்படி ஒரு உள்ளுணர்வு கொடுக்க நாங்கள் இந்த மாற்றம் பிரச்சனையை தீர்க்க முடியும்,

245
00:17:16,310 --> 00:17:18,890
இந்த subarray பாருங்கள் நாம்.

246
00:17:18,890 --> 00:17:23,460
இந்த உள்ளீடு வரிசை கொடுக்கப்பட்ட, மற்றும் நாம் பதில் 8 தெரியும்.

247
00:17:23,460 --> 00:17:26,359
நாம் 1, 4, மற்றும் 3 எடுத்து.

248
00:17:26,359 --> 00:17:29,090
ஆனால் நாம் உண்மையில் அந்த பதில் கிடைத்தது எப்படி இருக்கும் என்று.

249
00:17:29,090 --> 00:17:34,160
அது இந்த குறியீடுகள் ஒவ்வொரு மணிக்கு முடிந்தது என்று அதிகபட்ச subarray பார்க்கிறேன்.

250
00:17:34,160 --> 00:17:40,780
முதல் நிலை முடிவுக்கு கொண்டுவரப்பட வேண்டும் என்று அதிகபட்ச subarray என்ன?

251
00:17:40,780 --> 00:17:46,310
[மாணவர்] ஜீரோ. >> ஜீரோ. நான் -5 எடுத்து கொள்ள கூடாது.

252
00:17:46,310 --> 00:17:50,210
இங்கே அது அதே 0 இருக்க போகிறது. அப்படியா?

253
00:17:50,210 --> 00:17:56,470
(மாணவர், புரிந்து)

254
00:17:56,470 --> 00:17:58,960
[யு] ஓ, மன்னிக்கவும், இது ஒரு -3 உள்ளது.

255
00:17:58,960 --> 00:18:03,220
இந்த ஒரு 2 அதனால், இந்த ஒரு -3 உள்ளது.

256
00:18:03,220 --> 00:18:08,690
சரி. எனவே -4, அந்த நிலையை முடிவுக்கு அதிகபட்ச subarray என்ன

257
00:18:08,690 --> 00:18:12,910
-4 நேரத்தில் எங்கே? பூஜ்யம்.

258
00:18:12,910 --> 00:18:22,570
ஒரு? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
இப்போது, நான் -2 நேரத்தில் எங்கே இடத்தில் முடிவுக்கு வேண்டும்.

260
00:18:28,060 --> 00:18:39,330
எனவே 6, 5, 7, மற்றும் கடைசி ஒரு 4.

261
00:18:39,330 --> 00:18:43,480
இந்த என் உள்ளீடுகளை என்று தெரிந்தும்

262
00:18:43,480 --> 00:18:48,130
நான் இந்த குறியீடுகள் ஒவ்வொரு உள்ள முடிவுக்கு வேண்டும், அங்கு மாற்றினர் சிக்கல்,

263
00:18:48,130 --> 00:18:51,410
பிறகு என் இறுதி பதில் தான், முழுவதும் ஒரு ஸ்வீப் எடுத்து

264
00:18:51,410 --> 00:18:53,580
மற்றும் அதிகபட்ச எடுத்து.

265
00:18:53,580 --> 00:18:55,620
இந்த வழக்கில் அது 8 தான்.

266
00:18:55,620 --> 00:19:00,010
இந்த, அதிகபட்ச subarray இந்த குறியீட்டு முடிவடைகிறது என்பதை குறிக்கிறது

267
00:19:00,010 --> 00:19:04,970
அது முன்னர் எங்கோ தொடங்கியது.

268
00:19:04,970 --> 00:19:09,630
அனைவருக்கும் இந்த மாற்றம் subarray புரிந்து?

269
00:19:09,630 --> 00:19:22,160
>> சரி. சரி, இந்த தொடர் கண்டுபிடிக்க வேண்டும்.

270
00:19:22,160 --> 00:19:27,990
இது தான் முதல் சில உள்ளீடுகளை கருத்தில் கொள்வோம்.

271
00:19:27,990 --> 00:19:35,930
இங்கு இது, 8 0, 0, 0, 1, 5 இருந்தது.

272
00:19:35,930 --> 00:19:39,790
பின்னர் அங்கு ஒரு -2, அந்த 6 அதை கொண்டு.

273
00:19:39,790 --> 00:19:50,800
நான் நிலையில் நுழைவு அழைப்பு அதனால் நான் subproblem (i)

274
00:19:50,800 --> 00:19:54,910
எப்படி நான் ஒரு முந்தைய subproblem பதில் பயன்படுத்தலாம்

275
00:19:54,910 --> 00:19:59,360
இந்த subproblem பதில்?

276
00:19:59,360 --> 00:20:04,550
நான் பார்த்தால், இந்த நுழைவு, கூறலாம்.

277
00:20:04,550 --> 00:20:09,190
எப்படி நான் பார்த்து பதில் 6 கணக்கிட முடியாது

278
00:20:09,190 --> 00:20:18,780
இந்த வரிசையில் இந்த வரிசையில் முந்தைய subproblems பதில்களை கலவையை? ஆமாம்?

279
00:20:18,780 --> 00:20:22,800
[பெண் மாணவர்] நீங்கள் பெருக்கத்தின் வரிசை எடுத்து

280
00:20:22,800 --> 00:20:25,430
நிலையில் அதை முன், 8 ஆக

281
00:20:25,430 --> 00:20:32,170
பின்னர் தற்போதைய subproblem சேர்க்க.

282
00:20:32,170 --> 00:20:36,460
[யு], தனது பரிந்துரையை இந்த இரண்டு எண்கள் பார்க்க தான்

283
00:20:36,460 --> 00:20:40,090
இந்த எண்ணிக்கை மேலும் இந்த எண்.

284
00:20:40,090 --> 00:20:50,130
இந்த 8 subproblem பதில் (- 1 நான்) குறிக்கிறது.

285
00:20:50,130 --> 00:20:57,300
மற்றும் என் உள்ளீடு வரிசை ஏ அழைப்பு விடு

286
00:20:57,300 --> 00:21:01,470
நிலையை நான் முடிவடைகிறது என்று ஒரு அதிகபட்ச subarray கண்டுபிடிக்க வேண்டும்,

287
00:21:01,470 --> 00:21:03,980
நான் இரண்டு தேர்வுகள் உள்ளன: நான் ஒன்று subarray தொடரலாம்

288
00:21:03,980 --> 00:21:09,790
முந்தைய சுட்டு மணிக்கு முடிந்தது, அல்லது ஒரு புதிய அணியை தொடங்கும்.

289
00:21:09,790 --> 00:21:14,190
நான், முந்தைய குறியீட்டு மணிக்கு தொடங்கியது என்று subarray தொடர்ந்து இருந்தால்

290
00:21:14,190 --> 00:21:19,260
நான் சாதிக்க முடியும் அதிகபட்ச தொகை முந்தைய subproblem பதில் இல்லை

291
00:21:19,260 --> 00:21:24,120
அத்துடன் தற்போதைய வரிசை இடுகை.

292
00:21:24,120 --> 00:21:27,550
ஆனால், நான் கூட, ஒரு புதிய subarray துவங்கும் தேர்வு

293
00:21:27,550 --> 00:21:30,830
இதில் கூட்டுத்தொகையாக 0 ஆகும்.

294
00:21:30,830 --> 00:21:42,860
1, பிளஸ் தற்போதைய வரிசை இடுகை - அதனால் பதில் 0 அதிகபட்சம், subproblem நான் தான்.

295
00:21:42,860 --> 00:21:46,150
இந்த மீண்டும் பயன்?

296
00:21:46,150 --> 00:21:50,840
எங்கள் மீண்டும், நாம் தான் கண்டுபிடிக்கப்பட்டது என, subproblem நான் இல்லை

297
00:21:50,840 --> 00:21:54,740
முந்தைய subproblem அதிகபட்ச மற்றும் என் தற்போதைய வரிசை நுழைவு சமமாக இருக்கும்

298
00:21:54,740 --> 00:22:01,490
இது, முந்தைய subarray தொடர்ந்து பொருள்

299
00:22:01,490 --> 00:22:07,250
அல்லது 0, என் தற்போதைய குறியீட்டு ஒரு புதிய subarray தொடங்கும்.

300
00:22:07,250 --> 00:22:10,060
ஒருமுறை எங்கள் இறுதி பதில் பின்னர், தீர்வுகள் இந்த அட்டவணை இல்லாதபோது,

301
00:22:10,060 --> 00:22:13,950
வெறும் subproblem வரிசை முழுவதும் ஒரு நேர்கோட்டு ஸ்வீப் செய்ய

302
00:22:13,950 --> 00:22:19,890
மற்றும் அதிகபட்ச எடுத்து.

303
00:22:19,890 --> 00:22:23,330
இந்த நான் என்ன சொன்னேன் என்று ஒரு சரியான நடைமுறை ஆகும்.

304
00:22:23,330 --> 00:22:27,320
நாம் ஒரு புதிய subproblem வரிசை, subproblems உருவாக்க.

305
00:22:27,320 --> 00:22:32,330
முதல் இடுகை 0 அல்லது முதல் இடுகை, அந்த இரண்டு அதிகபட்ச ஒன்று உள்ளது.

306
00:22:32,330 --> 00:22:35,670
மற்றும் subproblems எஞ்சிய

307
00:22:35,670 --> 00:22:39,810
நாம் தான் கண்டுபிடிக்கப்பட்டது சரியான மீண்டும் பயன்படுத்த.

308
00:22:39,810 --> 00:22:49,960
இப்போது நாங்கள் எங்கள் subproblems அணியின் அதிகபட்ச கணக்கிட, மற்றும் நம் இறுதி பதில் தான்.

309
00:22:49,960 --> 00:22:54,130
>> எனவே எவ்வளவு இடத்தை நாம் இந்த வழிமுறையை பயன்படுத்தி?

310
00:22:54,130 --> 00:23:01,470
நீங்கள் மட்டும் CS50 எடுத்து இருந்தால், நீங்கள் மிகவும் இடத்தை பற்றி.

311
00:23:01,470 --> 00:23:07,750
நன்றாக, கவனிக்க ஒன்று நான் அளவு n இங்கு malloc என்று அழைத்தது.

312
00:23:07,750 --> 00:23:13,590
என்று நீங்கள் என்ன ஆலோசனை?

313
00:23:13,590 --> 00:23:17,450
இந்த வழிமுறை நேரான இடத்தை பயன்படுத்துகிறது.

314
00:23:17,450 --> 00:23:21,030
நாம் சிறப்பாக செய்ய முடியும்?

315
00:23:21,030 --> 00:23:30,780
நீங்கள் இறுதி பதில் கணக்கிட தேவையற்ற என்பதை நீங்கள் கவனிக்க வேண்டும் என்று ஏதாவது இருக்கிறதா?

316
00:23:30,780 --> 00:23:33,290
நான் நினைக்கிறேன் ஒரு நல்ல கேள்வி இது, என்ன தகவல்

317
00:23:33,290 --> 00:23:40,680
நாம் இறுதியில் அனைத்து வழிகளிலும் செயல்படுத்த தேவையில்லை?

318
00:23:40,680 --> 00:23:44,280
இப்போது, நாம் இந்த இரண்டு வரிகளை பாருங்கள் என்றால்,

319
00:23:44,280 --> 00:23:47,720
நாம் மட்டுமே, முந்தைய subproblem பற்றி கவலை

320
00:23:47,720 --> 00:23:50,910
நாம் மட்டுமே நாம் எப்போதும் இதுவரை பார்த்த அதிகபட்ச அக்கறை.

321
00:23:50,910 --> 00:23:53,610
நம் இறுதி பதில் கணக்கிடுவதற்கு, நாம் முழு வரிசையில் தேவையில்லை.

322
00:23:53,610 --> 00:23:57,450
நாம் கடந்த பல, கடந்த இரண்டு எண்கள் மட்டுமே தேவை.

323
00:23:57,450 --> 00:24:02,630
அதிகபட்சம் subproblem வரிசை, மற்றும் கடந்த பல கடைசியாக எண்.

324
00:24:02,630 --> 00:24:07,380
எனவே, உண்மையில், நாம் இந்த சுழல்கள் உருக

325
00:24:07,380 --> 00:24:10,460
மேலும் ஒருபடி இடத்தை தொடர்ந்து விண்வெளி சென்று.

326
00:24:10,460 --> 00:24:15,830
தற்போதைய தொகை இதுவரை, இங்கே, subproblem, எங்கள் subproblem வரிசை பங்கு மாற்றப்படும்.

327
00:24:15,830 --> 00:24:20,020
எனவே தற்போதைய தொகை, இதுவரை, முந்தைய subproblem பதில் இல்லை.

328
00:24:20,020 --> 00:24:23,450
அந்த தொகை, இதுவரை, எங்கள் அதிகபட்சம் என்ற நடைபெறுகிறது.

329
00:24:23,450 --> 00:24:28,100
நாம் சேர்ந்து போகலாம் என்று நாம் அதிகபட்ச கணக்கிட.

330
00:24:28,100 --> 00:24:30,890
அதனால் நாம், நிலையான இடத்தில் நேரியல் வெளி செல்ல

331
00:24:30,890 --> 00:24:36,650
நாம் நம் subarray பிரச்சினை ஒரு நேர்கோட்டு தீர்வு வேண்டும்.

332
00:24:36,650 --> 00:24:40,740
>> கேள்விகளை இந்த வகையான ஒரு பேட்டியில் போது வருவீர்கள்.

333
00:24:40,740 --> 00:24:44,450
சிக்கலான நேரத்தை என்ன; விண்வெளி சிக்கல் என்ன?

334
00:24:44,450 --> 00:24:50,600
நீங்கள் நன்றாக செய்ய முடியும்? சுற்றி வைக்க தேவையற்ற என்று விஷயங்கள் உள்ளன?

335
00:24:50,600 --> 00:24:55,270
நான் உங்கள் சொந்த எடுக்க வேண்டும் என்று ஆய்வுகள் முன்னிலைப்படுத்த இதை

336
00:24:55,270 --> 00:24:57,400
இந்த பிரச்சினைகள் மூலம் உழைக்கும் என.

337
00:24:57,400 --> 00:25:01,710
எப்போதும் "நான் நன்றாக செய்ய முடியுமா?", உங்களை கேட்கலாம்

338
00:25:01,710 --> 00:25:07,800
உண்மையில், நாம் இதை விட சிறப்பாக செய்ய முடியும்?

339
00:25:07,800 --> 00:25:10,730
ஒரு தந்திரம் கேள்வி வகையான. நீங்கள் வேண்டும், ஏனெனில் நீங்கள், முடியாது

340
00:25:10,730 --> 00:25:13,590
குறைந்தது பிரச்சனை உள்ளீடு வாசிக்க.

341
00:25:13,590 --> 00:25:15,570
நீங்கள் வேண்டும் என்று உண்மையில் குறைந்தபட்சம் பிரச்சனை உள்ளீடு படிக்க மிகவும்

342
00:25:15,570 --> 00:25:19,580
நீங்கள், நேரியல் நேரம் விட முடியாது என்று அர்த்தம்

343
00:25:19,580 --> 00:25:22,870
நீங்கள் நிலையான இடத்தை விட முடியாது.

344
00:25:22,870 --> 00:25:27,060
இந்த, உண்மையில், இந்த பிரச்சினைக்கு தீர்வு.

345
00:25:27,060 --> 00:25:33,040
கேள்விகள்? சரி.

346
00:25:33,040 --> 00:25:35,190
>> பங்கு சந்தை பிரச்சனை:

347
00:25:35,190 --> 00:25:38,350
"நேர்மறை, பூஜ்யம் அல்லது எதிர்மறையான n இன்டீஜர்கள், ஒரு வரிசை நிலையில்,

348
00:25:38,350 --> 00:25:41,680
என்று, n நாட்களில் ஒரு பங்கின் விலை பிரதிநிதித்துவம்

349
00:25:41,680 --> 00:25:44,080
நீங்கள் செய்ய முடியும் அதிகபட்ச லாபத்தை கணக்கிட ஒரு செயல்பாடு எழுத

350
00:25:44,080 --> 00:25:49,350
இந்த n நாட்களுக்குள் சரியாக 1 பங்கு வாங்க, விற்க என்று கொடுக்கப்பட்ட. "

351
00:25:49,350 --> 00:25:51,690
முக்கியமாக, நாம், குறைந்த விலைக்கு வாங்கி அதிக விலைக்கு விற்க வேண்டும்.

352
00:25:51,690 --> 00:25:58,580
மற்றும் நாம் உருவாக்க முடியும் சிறந்த இலாப கண்டுபிடிக்க வேண்டும்.

353
00:25:58,580 --> 00:26:11,500
என் நுனி செல்கிறேன், என்ன உடனடியாக தெளிவான, எளிய பதில், ஆனால் அது மெதுவாக தான்?

354
00:26:11,500 --> 00:26:17,690
ஆமாம்? (மாணவர், புரிந்து) >> ஆம்.

355
00:26:17,690 --> 00:26:21,470
>> எனவே நீங்கள் தான் என்றாலும் போய் பங்கு விலைகள் பார்ப்பார்கள்

356
00:26:21,470 --> 00:26:30,550
அந்த நேரத்தில் ஒவ்வொரு புள்ளி, (புரிந்து).

357
00:26:30,550 --> 00:26:33,990
[யு] சரி, அவளை தீர்வு - கணினி தனது பரிந்துரை

358
00:26:33,990 --> 00:26:37,380
குறைந்த மற்றும் அதிக கணக்கிடும் அவசியம் வேலை இல்லை

359
00:26:37,380 --> 00:26:42,470
அதிக குறைந்த முன் நிகழலாம் என்பதால்.

360
00:26:42,470 --> 00:26:47,340
எனவே இந்த பிரச்சினைக்கு முரட்டு தீர்வு என்ன?

361
00:26:47,340 --> 00:26:53,150
நான் தனிப்பட்ட நான் செய்ய இலாப தீர்மானிக்க வேண்டும் என்று இரண்டு விஷயங்கள் என்ன? சரி.

362
00:26:53,150 --> 00:26:59,410
முரட்டு தீர்வு - ஓ, அதனால், ஜார்ஜ் பரிந்துரை நாம் இரண்டு நாட்கள் தேவை இல்லை

363
00:26:59,410 --> 00:27:02,880
தனிப்பட்ட அந்த இரண்டு நாட்கள் இலாப தீர்மானிக்க.

364
00:27:02,880 --> 00:27:06,660
எனவே, வாங்க / விற்க போல், ஒவ்வொரு ஜோடி கணக்கிட

365
00:27:06,660 --> 00:27:12,850
எதிர்மறை அல்லது நேர்மறை அல்லது பூஜ்ஜியம் என்று இலாப, கணக்கிட.

366
00:27:12,850 --> 00:27:18,000
நாம் நாட்களில் அனைத்து ஜோடிகள் மீது தேடி பின்னர் செய்யும் அதிகபட்ச லாபத்தை கணக்கிட.

367
00:27:18,000 --> 00:27:20,330
என்று நம் இறுதி பதில் இருக்கும்.

368
00:27:20,330 --> 00:27:25,730
அந்த தீர்வு இல்லை என்பதால், ஓ (n ^ 2) இருக்கும் n இரண்டு ஜோடிகள் தேர்வு -

369
00:27:25,730 --> 00:27:30,270
நீங்கள் இறுதி நாட்களில் மத்தியில் தேர்வு செய்யலாம் என்று நாட்கள்.

370
00:27:30,270 --> 00:27:32,580
சரி, நான் இங்கே முரட்டு தீர்வு மேல் செல்ல போவதில்லை.

371
00:27:32,580 --> 00:27:37,420
நான் ஒரு n log n தீர்வு இல்லை என்று சொல்ல போகிறேன்.

372
00:27:37,420 --> 00:27:45,550
நீங்கள் தற்போது n log n என்று என்ன வழிமுறை தெரியுமா?

373
00:27:45,550 --> 00:27:50,730
இது ஒரு தந்திரம் பிரச்சினை அல்ல.

374
00:27:50,730 --> 00:27:54,790
>> சேர்ப்பு வரிசையாக்கம். ஒன்றாக்க வகையான, n log n ஆகும்

375
00:27:54,790 --> 00:27:57,760
உண்மையில், இந்த சிக்கலை தீர்க்க ஒரு வழி பயன்படுத்த வேண்டும்

376
00:27:57,760 --> 00:28:04,400
என்று யோசனை ஒரு பிணைப்பு வகையான வகையான, பொதுவாக, பிரித்து வெற்றி.

377
00:28:04,400 --> 00:28:07,570
பின்வருமாறு மற்றும் யோசனை.

378
00:28:07,570 --> 00:28:12,400
நீங்கள் சிறந்த வாங்க கணக்கிட / இடது பாதியில் ஜோடி விற்க வேண்டும்.

379
00:28:12,400 --> 00:28:16,480
நீங்கள் இரண்டு நாட்கள் முதல், n, செய்யலாம் சிறந்த இலாபம் தேட.

380
00:28:16,480 --> 00:28:19,780
பிறகு, சிறந்த வாங்க oompute / சரி பாதி மீது ஜோடி விற்க வேண்டும்

381
00:28:19,780 --> 00:28:23,930
இரண்டு நாட்களில் மிகவும் கடைசி n.

382
00:28:23,930 --> 00:28:32,400
இப்போது கேள்வி எப்படி நாம் மீண்டும் ஒன்றாக இந்த தீர்வுகள் ஒன்றாக்க வேண்டாம், இது?

383
00:28:32,400 --> 00:28:36,320
ஆமாம்? (மாணவர், புரிந்து)

384
00:28:36,320 --> 00:28:49,890
சரி >>. என்னை ஒரு படம் வரைய வேண்டும்.

385
00:28:49,890 --> 00:29:03,870
ஆமாம்? (ஜார்ஜ், புரிந்து)

386
00:29:03,870 --> 00:29:06,450
சரியாக >>. ஜார்ஜ் தீர்வு சரியாக இருக்கும்.

387
00:29:06,450 --> 00:29:10,040
அவரது ஆலோசனையை அதனால், முதல், சிறந்த வாங்கி / விற்கும் ஜோடி கணக்கிட

388
00:29:10,040 --> 00:29:16,050
மற்றும் இடது பகுதியில் ஏற்படும் என்று, எனவே இடது, இடது என அழைக்கிறேன்.

389
00:29:16,050 --> 00:29:20,790
சிறந்த சரி பாதி ஏற்படுகிறது என்று ஜோடி வாங்க / விற்க.

390
00:29:20,790 --> 00:29:25,180
நாம் இந்த இரண்டு எண்கள் ஒப்பிடுகையில் ஆனால், நாங்கள் வழக்கு காணவில்லை

391
00:29:25,180 --> 00:29:30,460
நாம் இங்கே வாங்க மற்றும் வலது பகுதியில் எங்காவது விற்க வேண்டும்.

392
00:29:30,460 --> 00:29:33,810
நாம் இடது பாதியில் வாங்க, வலது பாதி விற்க.

393
00:29:33,810 --> 00:29:38,490
இரண்டு பகுதிகளாக பரவியுள்ள சிறந்த வாங்கி / விற்கும் ஜோடி கணக்கிட சிறந்த வழி

394
00:29:38,490 --> 00:29:43,480
இங்கே குறைந்தபட்ச கணக்கிட மற்றும் இங்கே அதிகபட்ச கணக்கிட வேண்டும்

395
00:29:43,480 --> 00:29:45,580
அவர்களது வேறுபாடு எடுக்க.

396
00:29:45,580 --> 00:29:50,850
வாங்க / விற்க ஜோடி மட்டும் இங்கே ஏற்படும் இரண்டு வழக்குகள் எனவே,

397
00:29:50,850 --> 00:30:01,910
இங்கே தான், அல்லது இரண்டு பகுதிகளாக இந்த மூன்று எண்களை வரையறுக்கப்படுகிறது.

398
00:30:01,910 --> 00:30:06,450
, மீண்டும் ஒன்றாக நம் தீர்வுகளை இணைவதற்கு எங்கள் வழிமுறை மிகவும்

399
00:30:06,450 --> 00:30:08,350
நாம் சிறந்த வாங்கி / விற்கும் ஜோடி கணக்கிட வேண்டும்

400
00:30:08,350 --> 00:30:13,120
நாம் இடது பாதி மீது வாங்க மற்றும் வலது பாதி மீது விற்க வேண்டும்.

401
00:30:13,120 --> 00:30:16,740
அதை செய்ய சிறந்த வழி, முதல் பாதி மிகவும் குறைந்த விலை கணக்கிட வேண்டும்

402
00:30:16,740 --> 00:30:20,360
உயர்ந்த வலது பாதி விலை, மற்றும் அவர்களது வித்தியாசத்தை எடுத்து.

403
00:30:20,360 --> 00:30:25,390
இதனால் மூன்று இலாபங்கள், இந்த மூன்று எண்கள், நீங்கள், மூன்று அதிகபட்ச எடுத்து

404
00:30:25,390 --> 00:30:32,720
என்று நீங்கள் இந்த முதல் மற்றும் இறுதி நாட்களில் செய்யலாம் சிறந்த லாபம்.

405
00:30:32,720 --> 00:30:36,940
இங்கே முக்கியமான வரிகளை சிவப்பு உள்ளன.

406
00:30:36,940 --> 00:30:41,160
இந்த இடது பாதியில் பதில் கணக்கிட ஒரு சுழல்நிலை அழைப்பு.

407
00:30:41,160 --> 00:30:44,760
இது சரியான பகுதியில் பதில் கணக்கிட ஒரு சுழல்நிலை அழைப்பு.

408
00:30:44,760 --> 00:30:50,720
இந்த இரண்டு சுழல்கள் ஒரு முறையே, இடது மற்றும் வலது பாதி மீது நிமிடம் மற்றும் அதிகபட்சம் கணக்கிட.

409
00:30:50,720 --> 00:30:54,970
இப்போது நான், இரண்டு பகுதிகளாக பரவியுள்ள இலாப கணக்கிட

410
00:30:54,970 --> 00:31:00,530
இறுதி பதில் இந்த மூன்று அதிகபட்ச உள்ளது.

411
00:31:00,530 --> 00:31:04,120
சரி.

412
00:31:04,120 --> 00:31:06,420
>> எனவே, நிச்சயமாக, நாம் ஒரு வழிமுறை உண்டு, ஆனால் பெரிய கேள்வி

413
00:31:06,420 --> 00:31:08,290
இந்த சிக்கலான நேரத்தை என்ன?

414
00:31:08,290 --> 00:31:16,190
நான் ஒன்றிணைப்பு வகையான குறிப்பிட்டுள்ளார் காரணம் இந்த வடிவம் பதில் பிரித்து என்று

415
00:31:16,190 --> 00:31:19,200
இரண்டு பின் மீண்டும் ஒன்றாக நம் தீர்வுகளை இணைத்தல்

416
00:31:19,200 --> 00:31:23,580
சரியாக ஒன்றிணைப்பு மாதிரி வடிவம்.

417
00:31:23,580 --> 00:31:33,360
என்னை கால மூலம் செல்லலாம்.

418
00:31:33,360 --> 00:31:41,340
நாம் நடவடிக்கைகளை எண்ணிக்கை இருக்கும் ஒரு செயல்பாடு t (n) வரையறுக்கப்பட்ட என்றால்

419
00:31:41,340 --> 00:31:50,010
n நாட்கள்,

420
00:31:50,010 --> 00:31:54,350
எங்கள் இரண்டு சுழல்நிலை அழைப்பு

421
00:31:54,350 --> 00:32:00,460
ஒவ்வொரு t (n / 2), செலவு செய்ய போகிறாய்

422
00:32:00,460 --> 00:32:03,540
இந்த அழைப்புகள் இரண்டு உள்ளது.

423
00:32:03,540 --> 00:32:10,020
இப்போது நான், இடது பாதி குறைந்தபட்ச கணக்கிட வேண்டும்

424
00:32:10,020 --> 00:32:17,050
நான் n / 2 நேரம், மற்றும் வலது பாதி அதிகபட்ச செய்ய முடியும்.

425
00:32:17,050 --> 00:32:20,820
எனவே இந்த n.

426
00:32:20,820 --> 00:32:25,050
பின்னர் சில நிலையான வேலை பிளஸ்.

427
00:32:25,050 --> 00:32:27,770
இந்த மறுநிகழ்வு சமன்பாடு

428
00:32:27,770 --> 00:32:35,560
சரியாக ஒன்றிணைப்பு வகையான தொடர் சமன்பாடு.

429
00:32:35,560 --> 00:32:39,170
நாம் அனைத்து ஒன்றிணைப்பு வகையான n log n நேரம் என்று எனக்கு தெரியும்.

430
00:32:39,170 --> 00:32:46,880
எனவே, எங்கள் வழிமுறையானது பதிவு n நேரம் n.

431
00:32:46,880 --> 00:32:52,220
இந்த மறு செய்கை பயன்?

432
00:32:52,220 --> 00:32:55,780
இந்த ஒரு சிறிய முறையை:

433
00:32:55,780 --> 00:32:59,170
டி (n) அதிகபட்ச லாபத்தை கணக்கிட நடவடிக்கைகளை எண்ணிக்கை

434
00:32:59,170 --> 00:33:02,750
n நாட்களில் படிப்படியாக.

435
00:33:02,750 --> 00:33:06,010
நாம் சுழல்நிலை அழைப்புகள் பிரிந்து வழி

436
00:33:06,010 --> 00:33:11,980
, முதல் n / 2 நாட்களில் எங்கள் தீர்வு கோரி உள்ளது

437
00:33:11,980 --> 00:33:14,490
அதனால் ஒரு அழைப்பு, தான்

438
00:33:14,490 --> 00:33:16,940
மற்றும் நாம் இரண்டாவது பாதி மீண்டும் அழைப்பு.

439
00:33:16,940 --> 00:33:20,440
அதனால் இரண்டு அழைப்புகள் தான்.

440
00:33:20,440 --> 00:33:25,310
பின்னர் நாம், நாம் நேரியல் நேரம் செய்ய முடியும், இடது பாதி ஒரு குறைந்தபட்ச கண்டறிய

441
00:33:25,310 --> 00:33:29,010
நாம் நேரியல் நேரம் செய்ய இது சரியான அரை அதிகபட்ச கண்டுபிடிக்க.

442
00:33:29,010 --> 00:33:31,570
எனவே n / 2 + n / 2 தான் n ஆகும்.

443
00:33:31,570 --> 00:33:36,020
நாம் கணித செய்து போல் சில நிலையான வேலை, இல்லை.

444
00:33:36,020 --> 00:33:39,860
இந்த மறுநிகழ்வு சமன்பாடு சரியாக ஒன்றிணைப்பு வகையான தொடர் சமன்பாடு.

445
00:33:39,860 --> 00:33:55,490
எனவே, எங்கள் குலைப்பதை வழிமுறை உள்ளது n n log.

446
00:33:55,490 --> 00:33:58,520
எனவே எவ்வளவு இடத்தை நாம் பயன்படுத்தும்?

447
00:33:58,520 --> 00:34:04,910
இந்த குறியீடு திரும்பி செல்லலாம்.

448
00:34:04,910 --> 00:34:09,420
>> ஒரு நல்ல கேள்வி, எப்படி பல அடுக்கு சட்டங்களை நாம் எப்போதும் எந்த நேரத்திலும் இல்லை?

449
00:34:09,420 --> 00:34:11,449
நாம் மறுநிகழ்வு பயன்படுத்தி பின்னர்,

450
00:34:11,449 --> 00:34:23,530
ஸ்டாக் பிரேம்கள் எண்ணிக்கை நம் விண்வெளி பயன்பாடு தீர்மானிக்கிறது.

451
00:34:23,530 --> 00:34:29,440
அது n = 8 கருத்தில் கொள்வோம்.

452
00:34:29,440 --> 00:34:36,889
நாம், 8 குலைப்பதை அழைப்பு

453
00:34:36,889 --> 00:34:41,580
முதல் நான்கு உள்ளீடுகளை குலைப்பதை அழைப்பு அது,

454
00:34:41,580 --> 00:34:46,250
இதில் முதல் இரண்டு உள்ளீடுகளை ஒரு கலக்கு அழைக்கும்.

455
00:34:46,250 --> 00:34:51,550
எனவே எங்கள் ஸ்டாக் இல்லை - இந்த எங்கள் ஸ்டாக் இல்லை.

456
00:34:51,550 --> 00:34:54,980
பின்னர் நாம், 1 ம் தேதி மீண்டும் குலைப்பதை அழைப்பு

457
00:34:54,980 --> 00:34:58,070
மற்றும் அது நமது அடிப்படை வழக்கு என்ன ஆகும், எனவே நாம் உடனடியாக திரும்ப.

458
00:34:58,070 --> 00:35:04,700
நாம் எப்போதும் இந்த பல அடுக்கு சட்டங்களை விட வேண்டும்?

459
00:35:04,700 --> 00:35:08,880
இல்லை, நாம் ஒரு பிராத்தனை செய்ய ஒவ்வொரு முறையும் ஏனெனில்,

460
00:35:08,880 --> 00:35:10,770
குலைப்பதை ஒரு சுழல்நிலை பிரார்த்தனையுடன்,

461
00:35:10,770 --> 00:35:13,950
நாம் பாதி நம் அளவு பிரிக்க.

462
00:35:13,950 --> 00:35:17,020
நாம் எப்போதும் எந்த நேரத்திலும் வேண்டும் ஸ்டேக் அதிக பட்ச எண்ணிக்கை மிகவும்

463
00:35:17,020 --> 00:35:28,460
பதிவு n ஸ்டேக் பிரேம்கள் வரிசையில் உள்ளது.

464
00:35:28,460 --> 00:35:42,460
ஒவ்வொரு ஸ்டாக் சட்டகமானது, நிலையான இடம்

465
00:35:42,460 --> 00:35:44,410
இடத்தை எனவே மொத்த அளவு,

466
00:35:44,410 --> 00:35:49,240
நாம் எப்போதும் பயன்படுத்த இடத்தை அதிகபட்ச அளவு ஓ (log n) இடைவெளி இருக்கிறது

467
00:35:49,240 --> 00:36:03,040
அங்கு n நாட்கள் எண்ணிக்கை.

468
00:36:03,040 --> 00:36:07,230
>> இப்போது, எப்போதும் உங்களை கேட்க, "நாங்கள் நன்றாக செய்ய முடியுமா?"

469
00:36:07,230 --> 00:36:12,390
குறிப்பாக, நாம் ஏற்கனவே தீர்க்கப்பட நான் ஒரு பிரச்சனை இந்த குறைக்க முடியும்?

470
00:36:12,390 --> 00:36:20,040
ஒரு குறிப்பை: நாம் இந்த முன் இரண்டு மற்ற பிரச்சினைகள் பற்றி, மற்றும் அது குலைப்பதை இருக்க போகிறது இல்லை.

471
00:36:20,040 --> 00:36:26,200
நாம் அதிகபட்ச subarray பிரச்சனை இந்த பங்கு சந்தை பிரச்சனை மாற்ற முடியும்.

472
00:36:26,200 --> 00:36:40,100
எப்படி இதை செய்ய முடியும்?

473
00:36:40,100 --> 00:36:42,570
நீங்கள் ஒரு? எம்மி?

474
00:36:42,570 --> 00:36:47,680
(எம்மி, புரிந்து)

475
00:36:47,680 --> 00:36:53,860
[யு] சரியாக.

476
00:36:53,860 --> 00:36:59,940
அதிகபட்ச subarray பிரச்சனை,

477
00:36:59,940 --> 00:37:10,610
நாம் ஒரு தொடர் subarray ஒரு தொகை தேடுகிறீர்கள்.

478
00:37:10,610 --> 00:37:16,230
மற்றும் பங்குகள் பிரச்சனை எம்மி ஆலோசனையும்,

479
00:37:16,230 --> 00:37:30,720
மாற்றங்கள், அல்லது கழிமுக கருதுகின்றனர்.

480
00:37:30,720 --> 00:37:37,440
இந்த ஒரு படம் தான் - இந்த ஒரு பங்கு விலை என்பது,

481
00:37:37,440 --> 00:37:42,610
ஆனால் நாம் ஒவ்வொரு தொடர்ச்சியான நாள் வித்தியாசம் எடுத்து என்றால் -

482
00:37:42,610 --> 00:37:45,200
எனவே அதிகபட்ச விலை, அதிகபட்ச லாபம் நாம் செய்ய முடியும் என்று பார்க்க

483
00:37:45,200 --> 00:37:50,070
நாம் இங்கே வாங்க மற்றும் இங்கே விற்க இருக்கிறது.

484
00:37:50,070 --> 00:37:54,240
ஆனால் அது தொடர்ந்து பார்த்து விட்டு - தான் subarray பிரச்சனை பார்க்க வேண்டும்.

485
00:37:54,240 --> 00:38:02,510
எனவே இங்கே, நாம் செய்ய முடியும் - இங்கிருந்து இங்கே சென்று,

486
00:38:02,510 --> 00:38:08,410
நாம் ஒரு நல்ல மாற்றம் வேண்டும், பின்னர் இங்கே இங்கே இருந்து நாம் ஒரு எதிர்மறை மாற்றம் வேண்டும்.

487
00:38:08,410 --> 00:38:14,220
ஆனால் பின்னர், நாங்கள் ஒரு பெரிய நல்ல மாற்றம் இல்லை இங்கிருந்து இங்கே என்ன.

488
00:38:14,220 --> 00:38:20,930
இந்த நாங்கள் எங்கள் இறுதி லாபம் கிடைக்கும் வரை தொகையிடும் வேண்டும் என்று மாற்றங்கள்.

489
00:38:20,930 --> 00:38:25,160
நாம் இன்னும் எதிர்மறை மாற்றங்கள் இங்கே இல்லை.

490
00:38:25,160 --> 00:38:29,990
எங்கள் அதிகபட்ச subarray பிரச்சினை நமது பங்கு சிக்கல் குறைக்கும் முக்கிய

491
00:38:29,990 --> 00:38:36,630
நாட்கள் இடையே கழிமுக கருத்தில் கொள்ள வேண்டும்.

492
00:38:36,630 --> 00:38:40,630
எனவே, கழிமுக என்று ஒரு புதிய அணியை உருவாக்க

493
00:38:40,630 --> 00:38:43,000
, 0 முதல் இடுகை துவக்க

494
00:38:43,000 --> 00:38:46,380
பின்னர் ஒவ்வொரு டெல்டா க்கு (நான்), வேறுபாடு இருக்கும் என்று நாம்

495
00:38:46,380 --> 00:38:52,830
என் உள்ளீடு வரிசை (நான்), மற்றும் வரிசை (நான் - 1).

496
00:38:52,830 --> 00:38:55,530
நாம் ஒரு அதிகபட்ச subarray எங்கள் வழக்கமான நடைமுறை அழைப்பு

497
00:38:55,530 --> 00:39:01,500
ஒரு டெல்டா இன் வரிசையில் செல்லும்.

498
00:39:01,500 --> 00:39:06,440
மற்றும் பெருமதிப்பு subarray நேரியல் நேரம், ஏனெனில்

499
00:39:06,440 --> 00:39:09,370
இந்த குறைப்பு, இந்த டெல்டா வரிசை உருவாக்கும் இந்த செயல்முறை,

500
00:39:09,370 --> 00:39:11,780
, மேலும் ஒருபடி நேரம்

501
00:39:11,780 --> 00:39:19,060
பிறகு பங்குகள் இறுதி தீர்வு ஓ (n) வேலை மற்றும் ஓ (n) வேலை, இன்னும் ஓ (n) வேலை.

502
00:39:19,060 --> 00:39:23,900
எனவே நாம் நமது பிரச்சனை ஒரு நேரியல் நேரம் தீர்வு வேண்டும்.

503
00:39:23,900 --> 00:39:29,610
அனைவருக்கும் இந்த மாற்றத்தை புரிந்து?

504
00:39:29,610 --> 00:39:32,140
>> நீங்கள் எப்போதும் இருக்க வேண்டும் என்று பொதுவாக, ஒரு நல்ல யோசனை

505
00:39:32,140 --> 00:39:34,290
நீங்கள் காண்கிறீர்கள் என்று ஒரு புதிய சிக்கல் குறைக்க முயற்சி.

506
00:39:34,290 --> 00:39:37,700
அது ஒரு பழைய சிக்கல் நன்கு தெரிகிறது என்றால்,

507
00:39:37,700 --> 00:39:39,590
ஒரு பழைய பிரச்சனை அதை குறைக்கும் முயற்சி.

508
00:39:39,590 --> 00:39:41,950
நீங்கள் பழைய பிரச்சனை பயன்படுத்தப்படும் என்று அனைத்து கருவிகள் பயன்படுத்த முடியும் என்றால்,

509
00:39:41,950 --> 00:39:46,450
புதிய சிக்கலை தீர்க்க.

510
00:39:46,450 --> 00:39:49,010
எனவே மடிக்க வேண்டும், தொழில்நுட்ப நேர்முக சவால்.

511
00:39:49,010 --> 00:39:52,280
இந்த சிக்கல்கள் பெரும்பாலும் கடினமான பிரச்சினைகள் சில

512
00:39:52,280 --> 00:39:54,700
நீங்கள், ஒரு பேட்டியில் பார்க்க என்று

513
00:39:54,700 --> 00:39:57,690
நீங்கள் நான் மூடப்பட்டிருக்கும் என்று அனைத்து பிரச்சினைகள் புரியவில்லை என்றால், அது பரவாயில்லை.

514
00:39:57,690 --> 00:40:01,080
இந்த சவாலான சிக்கல்கள் உள்ளன.

515
00:40:01,080 --> 00:40:03,050
நடைமுறையில், நடைமுறையில், நடைமுறையில்.

516
00:40:03,050 --> 00:40:08,170
நான் துண்டு பிரசுரம் பிரச்சினைகள் நிறைய கொடுத்து, அதனால் நிச்சயமாக அந்த பாருங்கள்.

517
00:40:08,170 --> 00:40:11,690
உங்கள் நேர்முக நல்ல அதிர்ஷ்டம். என் வளங்கள், இந்த இணைப்பை இடப்பட்டவை

518
00:40:11,690 --> 00:40:15,220
என் மூத்த நண்பர் ஒருவர், போலி தொழில்நுட்ப நேர்முக செய்ய முன்வந்தார்

519
00:40:15,220 --> 00:40:22,050
நீங்கள் ஆர்வம் நீங்கள், மின்னஞ்சல் அந்த மின்னஞ்சல் முகவரியில் யோ வில்.

520
00:40:22,050 --> 00:40:26,070
உங்களிடம் சில கேள்விகள் இருந்தால், நீங்கள் என்னை கேட்கலாம்.

521
00:40:26,070 --> 00:40:28,780
நீங்கள் தொழில்நுட்ப நேர்முக தொடர்பான குறிப்பிட்ட கேள்விகள்

522
00:40:28,780 --> 00:40:38,440
அல்லது நாம் இதுவரை பார்த்த எந்த பிரச்சினைகள்?

523
00:40:38,440 --> 00:40:49,910
சரி. சரி, உங்கள் நேர்முக நல்ல அதிர்ஷ்டம்.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]