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
اگلا، دوسرا 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
تو دوسرے iteration کے ساتھ جاری ہیں.

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 تبادلہ، ہم حتمی کے ساتھ ختم

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
تو پہلی ناچھانٹا ہوا عنصر میں جمع 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، ن مربع آپریشن کے ایک 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
ن مربع آپریشن کے.

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 منفی فہرست کی طوالت integers.

153
00:07:49,160 --> 00:07:51,005
ہم ایک summation کے ساتھ اس کی نمائندگی کر سکتے ہیں.

154
00:07:57,980 --> 00:07:59,910
اب ہم نے summations میں یہاں نہیں جانا جائے گا.

155
00:07:59,910 --> 00:08:04,900
لیکن یہ پتہ چلا ہے کہ یہ summation ن بار کے برابر ہے

156
00:08:04,900 --> 00:08:07,540
ن مائنس 2 1.

157
00:08:07,540 --> 00:08:14,220
یا equivalently، ن 2 مائنس ن 2 مربع.

158
00:08:14,220 --> 00:08:18,860
جب asymptotic رن ٹائم کے بارے میں بات کر رہی ہے، اس ن مربع مدت

159
00:08:18,860 --> 00:08:22,070
اس ن مدت غلبہ حاصل کرنے کی جا رہی ہے.

160
00:08:22,070 --> 00:08:27,850
تو انتخاب کی طرح مربع ن O ہے.

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
لہذا انتخاب طرح مربع (ن) کے ایک بہترین کیس کی کارکردگی ہے،

168
00:08:51,470 --> 00:08:56,820
جو ہم ومیگا ن مربع کے ساتھ کی نمائندگی کرتے ہیں.

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 ہے.