1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] టామీ: ఎంపిక విధమైన పరిశీలించి, ఒక అల్గోరిథం తీసుకుందాం

2
00:00:09,980 --> 00:00:12,800
సంఖ్యల జాబితా తీసుకుని వాటిని క్రమీకరించడానికి.

3
00:00:12,800 --> 00:00:15,750
యాంత్రిక పద్ధతి గుర్తుంచుకోండి కేవలం ఒక దశల అడుగు

4
00:00:15,750 --> 00:00:18,370
ఒక విధిని పూర్తి ప్రక్రియ.

5
00:00:18,370 --> 00:00:21,470
ఎంపిక విధమైన వెనుక ప్రధాన ఆలోచన విభజించాలనే ఉంది

6
00:00:21,470 --> 00:00:23,390
రెండు భాగాలు గా మా జాబితా -

7
00:00:23,390 --> 00:00:26,810
ఒక క్రమబద్ధీకరించబడతాయి భాగం మరియు ఒక క్రమబద్ధీకరించనిది భాగం.

8
00:00:26,810 --> 00:00:30,200
అల్గోరిథం యొక్క ప్రతి దశ, ఒక సంఖ్య నుండి తరలించిన

9
00:00:30,200 --> 00:00:33,800
చివరికి వరకు క్రమబద్ధీకరించబడతాయి భాగానికి క్రమబద్ధీకరించనిది భాగం

10
00:00:33,800 --> 00:00:35,880
మొత్తం జాబితా క్రమీకరించబడింది.

11
00:00:35,880 --> 00:00:38,510
ఇక్కడ ఆరు సంఖ్యల జాబితా ఉంది -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, మరియు 15.

13
00:00:44,010 --> 00:00:47,680
ప్రస్తుతం మొత్తం జాబితా క్రమబద్ధీకరించనిది భావిస్తారు.

14
00:00:47,680 --> 00:00:51,770
16 వంటి అనేక ఇప్పటికే దాని సరైన లో ఉన్నప్పటికీ

15
00:00:51,770 --> 00:00:56,040
నగర, మా అల్గోరిథం వరకు తెలుసుకునేందుకు ఎటువంటి మార్గం ఉంది

16
00:00:56,040 --> 00:00:57,980
మొత్తం జాబితా క్రమీకరించబడింది.

17
00:00:57,980 --> 00:01:01,355
మేము క్రమం వరకు మేము క్రమబద్ధీకరించనిది చేయడానికి ప్రతి సంఖ్య పరిగణనలోకి చేస్తాము

18
00:01:01,355 --> 00:01:03,800
అది మేమే.

19
00:01:03,800 --> 00:01:06,890
మేము జాబితా క్రమంలో ఉండాలనుకుంటున్నాను తెలుసు.

20
00:01:06,890 --> 00:01:10,200
కాబట్టి మేము మా జాబితాలో క్రమబద్ధీకరించబడతాయి భాగాన్ని నిర్మించేందుకు చెయ్యవచ్చును

21
00:01:10,200 --> 00:01:13,280
ఎడమ నుండి కుడికి, అతిపెద్ద చిన్న.

22
00:01:13,280 --> 00:01:17,970
ఆ చేయుటకు మేము కనీసం క్రమబద్ధీకరించనిది మూలకం కనుగొనేందుకు చేయాలి

23
00:01:17,970 --> 00:01:21,350
మరియు క్రమబద్ధీకరించబడతాయి భాగం చివరిలో ఉంచారు.

24
00:01:21,350 --> 00:01:25,370
ఈ జాబితా వర్గీకరించరు కాబట్టి, ఆ విధంగా చేయడానికి ఏకైక మార్గం

25
00:01:25,370 --> 00:01:29,330
గుర్తు, క్రమబద్ధీకరించనిది భాగంలో ప్రతి మూలకం చూడండి

26
00:01:29,330 --> 00:01:32,010
మూలకం అత్యల్ప మరియు పోల్చడం ఇది

27
00:01:32,010 --> 00:01:33,770
ఆ ప్రతి మూలకం.

28
00:01:33,770 --> 00:01:36,150
కాబట్టి మేము మొదటి 23 లో పరిశీలిస్తాము.

29
00:01:36,150 --> 00:01:38,650
ఈ మేము చూసిన మొదటి మూలకం, కాబట్టి మేము గుర్తు చేస్తాము

30
00:01:38,650 --> 00:01:40,050
కనీస గా.

31
00:01:40,050 --> 00:01:42,320
తదుపరి మేము 42 వద్ద పరిశీలిస్తాము.

32
00:01:42,320 --> 00:01:46,720
42 23 కంటే ఎక్కువగా ఉంది, కాబట్టి 23 ఇప్పటికీ కనీస ఉంది.

33
00:01:46,720 --> 00:01:51,210
తదుపరి 23 కంటే తక్కువ 4, కాబట్టి మేము 4 గుర్తు చేస్తాము

34
00:01:51,210 --> 00:01:52,880
కొత్త కనీస వంటి.

35
00:01:52,880 --> 00:01:56,380
తదుపరి కాబట్టి 4, 4 కంటే ఎక్కువగా ఉంది, ఇది 16

36
00:01:56,380 --> 00:01:57,980
ఇప్పటికీ కనీస ఉంది.

37
00:01:57,980 --> 00:02:03,670
8 4 కంటే ఎక్కువగా ఉంది, మరియు 15 4 కంటే ఎక్కువగా ఉంది, 4 చేయాలి

38
00:02:03,670 --> 00:02:05,980
చిన్న క్రమబద్ధీకరించనిది మూలకం.

39
00:02:05,980 --> 00:02:09,350
కాబట్టి అయినప్పటికీ మనుషులుగా మనం వెంటనే 4 అని చూడగలరు

40
00:02:09,350 --> 00:02:12,300
కనీస మూలకం, మా అల్గోరిథం కు అవసరం

41
00:02:12,300 --> 00:02:15,710
మేము 4 దొరకలేదు తర్వాత కూడా ప్రతి క్రమబద్ధీకరించనిది మూలకం, -

42
00:02:15,710 --> 00:02:16,860
కనీస మూలకం.

43
00:02:16,860 --> 00:02:19,900
కాబట్టి ఇప్పుడు మేము కనీసం మూలకం, 4 దొరకలేదు చేసిన, మేము చెయ్యవచ్చును

44
00:02:19,900 --> 00:02:23,410
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం గా తరలించడానికి.

45
00:02:23,410 --> 00:02:27,320
ఈ మొదటి మెట్టు కాబట్టి, ఈ మేము వద్ద 4 ఉంచాలి కావలసిన అర్థం

46
00:02:27,320 --> 00:02:29,680
జాబితా ప్రారంభం.

47
00:02:29,680 --> 00:02:33,040
ప్రస్తుతం 23 కాబట్టి, జాబితా ప్రారంభంలో ఉంది

48
00:02:33,040 --> 00:02:36,080
యొక్క 4 మరియు 23 స్వాప్ తెలియజేయండి.

49
00:02:36,080 --> 00:02:38,870
కాబట్టి ఇప్పుడు మా జాబితా ఈ కనిపిస్తోంది.

50
00:02:38,870 --> 00:02:42,710
ఇది ఎందుకంటే మేము, 4 తుది నగర ఉండాలి తెలుసు

51
00:02:42,710 --> 00:02:45,890
ప్రారంభంలో చిన్న మూలకం మరియు మూలకం రెండు

52
00:02:45,890 --> 00:02:46,960
జాబితా యొక్క.

53
00:02:46,960 --> 00:02:50,650
మేము ఎప్పుడైనా మళ్ళీ తరలించే లేదు ఈ అని చెప్పుకుంటారు.

54
00:02:50,650 --> 00:02:53,910
కాబట్టి యొక్క మరొక మూలకం జోడించడానికి ఈ విధానాన్ని పునరుక్తి తెలియజేయండి

55
00:02:53,910 --> 00:02:55,910
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం.

56
00:02:55,910 --> 00:02:58,950
ఇది ఎందుకంటే మేము, మేము 4 కు లేదు తెలుసు

57
00:02:58,950 --> 00:03:00,000
ఇప్పటికే క్రమబద్ధీకరించబడతాయి.

58
00:03:00,000 --> 00:03:03,540
కనుక మేము గుర్తుంచుకోవాలి మేము, 42 వద్ద ప్రారంభించవచ్చు

59
00:03:03,540 --> 00:03:05,290
కనీస మూలకం.

60
00:03:05,290 --> 00:03:08,700
తరువాత మేము 42 కంటే తక్కువ 23 చూడండి, అలా చేస్తాము మేము

61
00:03:08,700 --> 00:03:11,620
23 కొత్త కనీస ఉంది గుర్తుంచుకోవాలి.

62
00:03:11,620 --> 00:03:14,870
తదుపరి మేము, కంటే తక్కువ 23 ఇది 16 చూడండి

63
00:03:14,870 --> 00:03:16,800
16 కొత్త కనీస ఉంది.

64
00:03:16,800 --> 00:03:19,720
ఇప్పుడు మేము, కంటే తక్కువ 16 ఇది 8 చూడండి

65
00:03:19,720 --> 00:03:21,130
8 కొత్త కనీస ఉంది.

66
00:03:21,130 --> 00:03:25,900
చివరకు 8 కంటే తక్కువ 15, కాబట్టి మేము 8 కనీసం అని తెలుసు

67
00:03:25,900 --> 00:03:27,780
క్రమబద్ధీకరించనిది మూలకం.

68
00:03:27,780 --> 00:03:30,660
కాబట్టి మేము క్రమబద్ధీకరించబడతాయి నుండి 8 జోడించు ఉండాలి అర్థం

69
00:03:30,660 --> 00:03:32,450
జాబితా యొక్క భాగం.

70
00:03:32,450 --> 00:03:35,990
ప్రస్తుతం 4 మాత్రమే క్రమబద్ధీకరించబడతాయి మూలకం, కాబట్టి మేము ఉంచాలనుకుంటే

71
00:03:35,990 --> 00:03:38,410
4 నుండి 8 తర్వాత.

72
00:03:38,410 --> 00:03:41,920
42 నుంచి క్రమబద్ధీకరించనిది భాగంలో మొదటి అంశం

73
00:03:41,920 --> 00:03:47,260
జాబితా, మేము 42 మరియు 8 స్వాప్ చెయ్యవచ్చును.

74
00:03:47,260 --> 00:03:49,680
కాబట్టి ఇప్పుడు మా జాబితా ఈ కనిపిస్తోంది.

75
00:03:49,680 --> 00:03:53,830
4 మరియు 8 జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం సూచిస్తాయి, మరియు

76
00:03:53,830 --> 00:03:56,440
మిగిలిన సంఖ్యలు క్రమబద్ధీకరించనిది ప్రాతినిధ్యం

77
00:03:56,440 --> 00:03:58,260
జాబితా యొక్క భాగం.

78
00:03:58,260 --> 00:04:00,630
కాబట్టి యొక్క మరొక మళ్ళా కలిసి చెయ్యనివ్వండి.

79
00:04:00,630 --> 00:04:03,850
మేము చూడండి లేదు నుండి మేము, 23 ఈ ప్రారంభమవుతుంది

80
00:04:03,850 --> 00:04:05,770
4 మరియు ఇకపై 8 వారు ఉంచిన ఎందుకంటే

81
00:04:05,770 --> 00:04:07,660
ఇప్పటికే క్రమబద్ధీకరించబడతాయి చేయబడింది.

82
00:04:07,660 --> 00:04:10,270
16 కంటే తక్కువ 23, కాబట్టి మేము గుర్తు చేస్తాము

83
00:04:10,270 --> 00:04:12,070
కొత్త కనీస వంటి 16.

84
00:04:12,070 --> 00:04:18,149
15 చేయాలి, 16 కంటే తక్కువ 42, కానీ 15 కంటే తక్కువ 16

85
00:04:18,149 --> 00:04:20,480
కనీస క్రమబద్ధీకరించనిది మూలకం.

86
00:04:20,480 --> 00:04:24,580
కాబట్టి ఇప్పుడు మేము 15 మరియు 23 మారడానికి కావలసిన

87
00:04:24,580 --> 00:04:26,310
మాకు ఈ జాబితా ఇవ్వండి.

88
00:04:26,310 --> 00:04:30,500
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం 4, 8 మరియు 15 ఉన్నాయి, మరియు

89
00:04:30,500 --> 00:04:33,210
ఈ అంశాలను ఇప్పటికీ క్రమబద్ధీకరించనిది ఉంటాయి.

90
00:04:33,210 --> 00:04:36,900
కానీ ఇది కేవలం కాబట్టి జరుగుతుందని తదుపరి క్రమబద్ధీకరించనిది మూలకం, 16,

91
00:04:36,900 --> 00:04:38,480
ఇప్పటికే క్రమబద్ధీకరించబడింది.

92
00:04:38,480 --> 00:04:42,060
అయితే, తెలిసి మా అల్గోరిథం కోసం మార్గం లేదు అని 16

93
00:04:42,060 --> 00:04:45,230
ఇప్పటికే దాని సరైన స్థానంలో, కాబట్టి మేము ఇంకా అవసరం

94
00:04:45,230 --> 00:04:47,870
అదే విధానాన్ని పునరుక్తి.

95
00:04:47,870 --> 00:04:53,750
కాబట్టి, మేము 16 కంటే తక్కువ 42 ఉందని, మరియు 16 కంటే తక్కువ 23 ఉంది

96
00:04:53,750 --> 00:04:56,230
16 కనీస మూలకం ఉండాలి.

97
00:04:56,230 --> 00:04:59,010
ఇది కూడా ఈ మూలకం మారడానికి అసాధ్యం, మేము చేయగలరా

98
00:04:59,010 --> 00:05:01,780
కేవలం ఈ ప్రదేశంలో వదిలి.

99
00:05:01,780 --> 00:05:04,660
కాబట్టి మేము మా అల్గోరిథం యొక్క మరొక పాస్ అవసరం.

100
00:05:04,660 --> 00:05:09,370
42 23 కంటే ఎక్కువ, కాబట్టి 23 ఉండాలి

101
00:05:09,370 --> 00:05:10,970
కనీస క్రమబద్ధీకరించనిది మూలకం.

102
00:05:10,970 --> 00:05:17,410
ఒకసారి మేము మా చివరి ముగిసేవి, 23 మరియు 42 స్వాప్

103
00:05:17,410 --> 00:05:18,530
పేర్చిన జాబితా -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
మేము ఇది నుంచి 42 సరైన స్థానంలో ఉండాలి తెలుసు

106
00:05:26,830 --> 00:05:30,210
మాత్రమే మూలకం వదిలి, మరియు ఎంపిక విధమైన ఉంది.

107
00:05:30,210 --> 00:05:32,100
లెట్ యొక్క కొన్ని ఇప్పుడు మన అల్గోరిథం ప్రమాణీకరించవల్సిన

108
00:05:32,100 --> 00:05:34,540
pseudocode.

109
00:05:34,540 --> 00:05:37,760
రేఖ ఒక న, మేము పైగా ఇంటిగ్రేట్ అవసరమైన చూడగలరు

110
00:05:37,760 --> 00:05:39,530
జాబితా యొక్క ప్రతీ మూలకం.

111
00:05:39,530 --> 00:05:42,150
గత మూలకం తప్ప, ఎందుకంటే 1 మూలకం

112
00:05:42,150 --> 00:05:44,230
జాబితా ఇప్పటికే క్రమబద్ధీకరించబడింది.

113
00:05:44,230 --> 00:05:48,100
లైన్ రెండు న, క్రమబద్ధీకరించనిది మొదటి మూలకం పరిగణలోకి

114
00:05:48,100 --> 00:05:51,080
మేము మా వలె జాబితా యొక్క భాగం, కనీస అని

115
00:05:51,080 --> 00:05:53,750
ఉదాహరణకు, కాబట్టి మేము పోల్చడానికి ఏదైనా కలిగి.

116
00:05:53,750 --> 00:05:57,260
లైన్ మూడు మేము పైగా iterate రెండవ లూప్ ప్రారంభమవుతుంది

117
00:05:57,260 --> 00:05:59,170
ప్రతి క్రమబద్ధీకరించనిది మూలకం.

118
00:05:59,170 --> 00:06:02,150
మేము తెలిసిన నేను నిద్రావస్థ తర్వాత, క్రమబద్ధీకరించబడింది భాగం

119
00:06:02,150 --> 00:06:05,330
మా జాబితా ప్రతి అడుగు నుండి అది నేను అంశాలను కలిగి ఉండాలి

120
00:06:05,330 --> 00:06:06,890
రకాల ఒక మూలకం.

121
00:06:06,890 --> 00:06:11,770
కాబట్టి మొదటి క్రమబద్ధీకరించనిది మూలకం స్థానం i ప్లస్ 1 ఉండాలి.

122
00:06:11,770 --> 00:06:15,440
లైన్ నాలుగు న, కనీస ప్రస్తుత మూలకం పోల్చి

123
00:06:15,440 --> 00:06:17,750
మేము ఇప్పటివరకు చూసిన ఆ మూలకం.

124
00:06:17,750 --> 00:06:20,560
ప్రస్తుత మూలకం కనీస తక్కువైతే

125
00:06:20,560 --> 00:06:23,870
మూలకం, అప్పుడు మేము కొత్త గా ప్రస్తుత మూలకం గుర్తు

126
00:06:23,870 --> 00:06:26,250
లైన్ ఐదు న కనిష్ట.

127
00:06:26,250 --> 00:06:29,900
చివరగా, పంక్తులు ఆరు మరియు ఏడు న, కనీస మార్పిడి

128
00:06:29,900 --> 00:06:33,080
తద్వారా మొదటి క్రమబద్ధీకరించనిది మూలకం తో మూలకం,

129
00:06:33,080 --> 00:06:36,990
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం జోడించడం.

130
00:06:36,990 --> 00:06:40,030
మేము ఒక అల్గోరిథం తర్వాత, ఒక ముఖ్యమైన ప్రశ్న అడగడానికి

131
00:06:40,030 --> 00:06:43,370
మేమే ప్రోగ్రామర్లు ఆ ఎంత సమయం పడుతుంది లేదు ఉంది?

132
00:06:43,370 --> 00:06:46,970
మేము మొదటి ప్రశ్న అడుగుతాము ఎంత ఈ కోసం పడుతుంది

133
00:06:46,970 --> 00:06:50,070
అల్గోరిథం విషయంలో అమలు చెయ్యడానికి?

134
00:06:50,070 --> 00:06:51,640
మేము ఈ పరుగు ప్రాతినిధ్యం రీకాల్

135
00:06:51,640 --> 00:06:55,060
పెద్ద O సంజ్ఞామానం సమయం.

136
00:06:55,060 --> 00:06:58,650
కనీస క్రమబద్ధీకరించనిది మూలకం నిర్ధారించేందుకు, మేము

137
00:06:58,650 --> 00:07:01,880
ముఖ్యంగా జాబితా ప్రతి మూలకం పోల్చి వచ్చింది

138
00:07:01,880 --> 00:07:04,040
జాబితాలో ప్రతి ఇతర మూలకం.

139
00:07:04,040 --> 00:07:08,430
Intuitively, n స్క్వేర్డ్ ఆపరేషన్ యొక్క O వంటి ఈ శబ్దాలు.

140
00:07:08,430 --> 00:07:12,050
మా pseudocode వద్ద గురించి, మేము కూడా లోపల యున్న ఒక లూప్ కలిగి

141
00:07:12,050 --> 00:07:14,420
ఒక O వంటి నిజానికి వినిపిస్తుంది మరొక లూప్,

142
00:07:14,420 --> 00:07:16,480
n స్క్వేర్డ్ ఆపరేషన్.

143
00:07:16,480 --> 00:07:19,250
అయితే, మేము చూసి అవసరం లేదు గుర్తుంచుకోవాలి

144
00:07:19,250 --> 00:07:23,460
కనీస క్రమబద్ధీకరించనిది మూలకం నిర్ణయించేటప్పుడు మొత్తం జాబితా?

145
00:07:23,460 --> 00:07:26,600
మేము 4 క్రమబద్ధీకరించబడతాయి అని తెలుసు ఒకసారి, ఉదాహరణకు, కాదు

146
00:07:26,600 --> 00:07:28,170
దాన్ని మళ్ళీ వద్ద చూడవలసిన అవసరం.

147
00:07:28,170 --> 00:07:31,020
ఈ నడుస్తున్న సమయంలో తక్కువ చేస్తుంది?

148
00:07:31,020 --> 00:07:34,510
పొడవు 6 మా జాబితా కోసం, మేము ఐదు అవసరమైన

149
00:07:34,510 --> 00:07:37,990
మొదటి మూలకం కోసం పోలికలు, నాలుగు పోలికలు

150
00:07:37,990 --> 00:07:40,750
రెండవ మూలకం, అందువలన న.

151
00:07:40,750 --> 00:07:44,690
ఆ దశలను మొత్తం మొత్తానికి అర్థం

152
00:07:44,690 --> 00:07:49,160
1 నుండి జాబితా మైనస్ 1 యొక్క పొడవు వరకు పూర్ణాంకాల.

153
00:07:49,160 --> 00:07:51,005
మేము ఒక సమ్మషన్ ఈ సూచిస్తుంది.

154
00:07:57,980 --> 00:07:59,910
మేము ఇక్కడ summations లోకి కాదు.

155
00:07:59,910 --> 00:08:04,900
కానీ ఈ సమ్మషన్ n సార్లు సమానంగా ఉంటుంది అవుతుంది

156
00:08:04,900 --> 00:08:07,540
n మైనస్ 2 పైగా 1.

157
00:08:07,540 --> 00:08:14,220
లేదా సమానమైన, n 2 పై మైనస్ n 2 పై Squared.

158
00:08:14,220 --> 00:08:18,860
Asymptotic runtime గురించి మాట్లాడుతూ, ఈ n స్క్వేర్డ్ పదం

159
00:08:18,860 --> 00:08:22,070
ఈ n పదం ఆధిపత్యం అన్నారు.

160
00:08:22,070 --> 00:08:27,850
కాబట్టి ఎంపిక విధమైన n స్క్వేర్డ్ ఓ ఉంటుంది.

161
00:08:27,850 --> 00:08:31,460
మా ఉదాహరణ లో, ఎంపిక విధమైన ఇప్పటికీ అవసరమైన గుర్తుచేసుకున్నారు

162
00:08:31,460 --> 00:08:33,850
తనిఖీ ఉంటే ఇప్పటికే క్రమబద్ధీకరించబడతాయి ఒక సంఖ్య

163
00:08:33,850 --> 00:08:35,450
తరలించేందుకు అవసరమైన.

164
00:08:35,450 --> 00:08:38,929
కాబట్టి అని మేము ఇప్పటికే పైగా ఎంపిక విధమైన నడిచింది ఉంటే

165
00:08:38,929 --> 00:08:43,070
జాబితా క్రమబద్ధీకరించిన అది వంటి దశలను అదే నెంబర్ కావాలి

166
00:08:43,070 --> 00:08:46,340
పూర్తిగా క్రమబద్ధీకరించనిది జాబితా పైగా పరిగెడుతున్నప్పుడు చేస్తాను.

167
00:08:46,340 --> 00:08:51,470
కాబట్టి ఎంపిక విధమైన, స్క్వేర్డ్ n యొక్క ఒక ఉత్తమ కేసు ప్రదర్శన ఉంది

168
00:08:51,470 --> 00:08:56,820
ఇది మేము ఒమేగా n స్క్వేర్డ్ తో సూచిస్తాయి.

169
00:08:56,820 --> 00:08:58,600
మరియు ఎంపిక విధమైన కోసం ఇది.

170
00:08:58,600 --> 00:09:00,630
మేము అనేక అల్గోరిథంలు ఒకటి

171
00:09:00,630 --> 00:09:02,390
ఒక జాబితాను క్రమబద్దీకరించేందుకు ఉపయోగించండి.

172
00:09:02,390 --> 00:09:05,910
నా పేరు టామీ, మరియు ఈ cs50 ఉంది.