1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: চলুন নির্বাচন সাজানোর কটাক্ষপাত, একটি অ্যালগরিদম গ্রহণ

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
একটি টাস্ক accomplishing জন্য পদ্ধতি.

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
এর পরে রয়েছে 4 যা 23 তুলনায় কম, তাই আমরা 4 স্মরণ করব

34
00:01:51,210 --> 00:01:52,880
হিসাবে নতুন সর্বনিম্ন.

35
00:01:52,880 --> 00:01:56,380
এর পরে রয়েছে 16, যা 4 অধিক মাপের, তাই 4

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
সুতরাং আমরা পরবর্তী 23 যা 42 এর কম সময়ে, যাতে সন্ধান করব আমরা

61
00:03:08,700 --> 00:03:11,620
মনে রাখবেন 23 নতুন সর্বনিম্ন.

62
00:03:11,620 --> 00:03:14,870
আমরা 16 এর পরে যা কম 23 দেখতে, তাই

63
00:03:14,870 --> 00:03:16,800
16 নতুন সর্বনিম্ন.

64
00:03:16,800 --> 00:03:19,720
এখন 8 যা কম 16 এ আমরা, তাই চেহারা

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
8 পরবর্তী যাও 4.

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
16 এর চেয়ে 42, কিন্তু 15 এর চেয়ে 16, তাই 15 হতে হবে

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, swap আমরা আমাদের চূড়ান্ত সঙ্গে শেষ

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
লাইন তিনটি দ্বিতীয় একটি লুপ যা আমরা উপর পুনরুক্তি করা শুরু

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
সুতরাং প্রথম পাঁচমিশালী উপাদান তোমার প্লাস 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
বড় হে স্বরলিপি সঙ্গে সময়.

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 স্কয়ার্ড কার্যপ্রণালীর এই মত শোনায়.

140
00:07:08,430 --> 00:07:12,050
আমাদের pseudocode এ জন্যে, আমরা একটি লুপ নেস্টেড ভিতর আছে

141
00:07:12,050 --> 00:07:14,420
অন্য একটি হে ভালো লুপ, যা প্রকৃতপক্ষে শোনাচ্ছে

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
কিন্তু এটি সক্রিয় আউট যে এই সঙ্কলন সমান হবে বার যাও

156
00:08:04,900 --> 00:08:07,540
n বিয়োগ 2 উপর 1.

157
00:08:07,540 --> 00:08:14,220
অথবা equivalently, উপর 2 বিয়োগ জন্য 2 উপর n Squared.

158
00:08:14,220 --> 00:08:18,860
Asymptotic রানটাইম সম্পর্কে যখন কথা বলা, এই শব্দটি 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.