[Powered by Google Translate] ٹامی: انتخاب کی طرح پر ایک نظر، ایک الگورتھم
اعداد کی ایک فہرست لے اور انہیں حل کرنے کے لئے.
ایک الگورتھم، یاد صرف ایک قدم کی طرف سے قدم ہے
کام کی تکمیل کے لئے طریقہ کار.
انتخاب طرح کے پیچھے بنیادی خیال کی تقسیم ہے
دو حصے میں ہماری فھرست -
کے مطابق حصہ اور ایک ناچھانٹا ہوا حصہ.
الگورتھم میں سے ہر ایک قدم پر ایک نمبر سے منتقل کر دیا گیا ہے
ناچھانٹا ہوا کے مطابق حصہ کے آخر میں جب تک حصہ
کی مکمل فہرست کے مطابق ہے.
تو یہاں چھ کی تعداد کی ایک فہرست ہے -
23، 42، 4، 16، 8، اور 15.
ابھی مکمل فہرست ناچھانٹا ہوا تصور کیا جاتا ہے.
اگرچہ 16 کی طرح ایک بڑی تعداد پہلے سے ہی اس کے صحیح میں ہو سکتا ہے
محل وقوع، ہماری الگورتھم تک کہ جاننے کا کوئی راستہ نہیں ہے
کی مکمل فہرست کے مطابق ہے.
تو ہم ہر نمبر پر غور ناچھانٹا ہوا رکھا جائے جب تک ہم الگ الگ ہوں گے
خود.
ہم جانتے ہیں کہ ہم فہرست صعودی میں کرنا چاہتے ہیں.
تو ہم نے ہماری فہرست کے مطابق حصہ بنانے چاہیں گے
بائیں سے دائیں جانب سب سے بڑا پر سب سے چھوٹی ہے.
ایسا کرنے کے لئے، ہم کم از کم ناچھانٹا ہوا عناصر کو تلاش کرنے کے لئے کی ضرورت ہو گی
اور اس کے مطابق حصہ کے آخر میں ڈال دیا ہے.
چونکہ اس فہرست کے مطابق ہے، صرف ایسا کرنے کا طریقہ ہے
ناچھانٹا ہوا حصہ میں ہر عنصر کو دیکھو، یاد
جو عنصر سب سے کم اور موازنہ ہے
اس کے ہر عنصر.
تو ہم نے 23 میں سب سے پہلے دیکھتا ہوں.
یہ پہلا عنصر ہے ہم نے دیکھا ہے، تو ہمیں یاد کریں گے
کم از کم کے طور پر یہ.
پیچھے اگلا، دوسرا ہم نے 42 میں دیکھتا ہوں.
42 23 سے بڑا ہے، اس لئے 23 ابھی تک کم از کم ہے.
اگلا، دوسرا 4 جو 23 سے کم ہے، تو ہم 4 یاد کریں گے
نئی کم از کم کے طور پر.
اگلا، دوسرا 16 جو 4 سے بڑا ہے ہے، تو 4
ابھی تک کم از کم ہے.
8 4 سے بڑا ہے، اور 15 4 سے بڑا ہے، 4 کا ہونا لازمی ہے
سب سے چھوٹی ناچھانٹا ہوا عنصر.
تو اگرچہ ہم انسانوں کے طور پر فوری طور پر کہ 4 ہے دیکھ سکتے ہیں
کم از کم عنصر، ہماری الگورتھم کو دیکھنے کے لئے کی ضرورت ہے
ہر ناچھانٹا ہوا عنصر، کے بعد بھی ہم نے 4 ملا ہے -
کم از کم عنصر.
تو اب ہے کہ ہم کم از کم عنصر، 4 مل گیا ہے، ہم چاہتے ہیں کریں گے،
اس فہرست کے مطابق حصہ میں منتقل.
چونکہ یہ پہلا قدم ہے، اس کا مطلب یہ ہے کہ ہم میں 4 کرنا چاہتے
فہرست کے آغاز.
ابھی 23 کی فہرست کے شروع میں ہے، تو
4 اور 23 تبادلہ.
تو اب ہماری فہرست میں اس طرح لگ رہا ہے.
ہم جانتے ہیں کہ 4 اس کے آخری مقام پر ہونا ضروری ہے، کیونکہ یہ ہے
دونوں شروع میں سب سے چھوٹی عنصر اور عنصر
فہرست.
تو اس کا مطلب ہے کہ ہم اسے دوبارہ منتقل کبھی ضرورت نہیں ہے.
تو اس عمل کو کسی دوسرے عنصر شامل کرنے کے لئے دوبارہ
فہرست کے مطابق حصہ.
ہم جانتے ہیں کہ ہم 4 کو دیکھنے کے لئے کی ضرورت نہیں ہے، کیونکہ یہ ہے
پہلے ہی حل ہے.
تو ہم نے 42 میں شروع، جو ہم یاد کریں گے کر سکتے ہیں
کم از کم عنصر.
اگلے تو ہم 23 جو 42 سے کم ہے کو دیکھو گے، تو ہم
یاد 23 نئے کم از کم ہے.
<پیچھے اگلا، دوسرا ہم 16 نظر آتا ہے جس میں 23 سے بھی کم ہے تو، ہو، تو
16 نئے کم از کم ہے.
اب ہم نے 8 جس میں سے کم 16 ہے، دیکھو تو
8 نئے کم از کم ہے.
اور آخر میں 8 سے کم از کم 15 ہے، تو ہم جانتے ہیں کہ 8 کم از کم ہے
ناچھانٹا ہوا عنصر.
تو اس کا مطلب ہے کہ ہم کے مطابق 8 ملحق کرنا چاہئے
فہرست کا حصہ ہے.
ابھی 4 ہی کے مطابق عنصر ہے، تو ہم چاہتے ہیں کہ رکھنے
8 اگلا 4.
42 چونکہ کے ناچھانٹا ہوا حصہ میں پہلا عنصر ہے
فہرست میں، ہم 42 اور 8 تبادلہ کرنا چاہتے ہیں کریں گے.
تو اب ہماری فہرست میں اس طرح لگ رہا ہے.
4 اور 8 کی فہرست کے مطابق حصہ کی نمائندگی کرتے ہیں، اور
باقی تعداد ناچھانٹا ہوا کی نمائندگی کرتے ہیں
فہرست کا حصہ ہے.
تو دوسرے iteration کے ساتھ جاری ہیں.
ہم 23 کے ساتھ اس وقت شروع کرتے ہیں، کیونکہ ہم کو دیکھنے کے لئے کی ضرورت نہیں ہے
4 اور اب 8 کیونکہ وہ ہے
پہلے ہی کے مطابق کیا گیا ہے.
16 23 سے بھی کم ہے، تو ہمیں یاد کریں گے
نئی کم از کم کے طور پر 16.
16 سے کم 42 ہے، لیکن 15 سے کم 16 ہے، تو 15 ہونا چاہیے
کم از کم ناچھانٹا ہوا عنصر.
تو اب ہم 15 اور 23 پر تبادلہ کرنا چاہتے ہیں
ہمیں اس فہرست دے.
فہرست کے مطابق حصہ 4، 8 اور 15 کے پر مشتمل ہوتا ہے، اور
ان عناصر اب بھی ناچھانٹا ہوا کر رہے ہیں.
لیکن یہ صرف اس لئے ہوتا ہے کہ اگلے ناچھانٹا ہوا عنصر، 16،
پہلے ہی حل ہے.
تاہم، ہماری الگورتھم کے لئے کوئی راستہ نہیں ہے، یہ جاننا ہے کہ 16
پہلے ہی اس کی صحیح جگہ میں ہے، تو ہم اب بھی کرنے کی ضرورت ہے
بالکل اسی عمل کو دہرائیں.
تو ہم دیکھتے ہیں کہ 16 سے کم 42 ہے، اور 16 23 سے بھی کم ہے، تو
16 کم از کم عنصر ہونا چاہیے.
ہے تو یہ ناممکن ہے خود کے ساتھ اس عنصر پر تبادلہ، ہم کر سکتے ہیں
صرف اسے اس جگہ میں چھوڑ.
تو ہم ہمارے الگورتھم کی ایک اور پاس کی ضرورت ہے.
42 23 سے بڑھ کر ہے، تو 23 ہونا چاہیے
کم از کم ناچھانٹا ہوا عنصر.
ایک بار جب ہم 23 اور 42 تبادلہ، ہم حتمی کے ساتھ ختم
کے مطابق کی فہرست -
4، 8، 15، 16، 23، 42.
ہم جانتے ہیں کہ 42 صحیح جگہ پر ہو کیونکہ یہ ضروری ہے
صرف عنصر کو چھوڑ دیا ہے، اور یہ کہ انتخاب طرح ہے.
چلو اب کچھ کے ساتھ ہمارے الگورتھم کو رسمی طور
pseudocode.
ایک آن لائن ہم دیکھتے ہیں، کہ ہم ضم کرنے کی ضرورت ہے کر سکتے ہیں
فہرست کے ہر عنصر.
آخری عنصر کے علاوہ کے بعد، 1 عنصر
فہرست میں پہلے ہی کے مطابق ہے.
دو آن لائن کو ہم ناچھانٹا ہوا کے پہلے عنصر پر غور
فہرست کا حصہ کم از کم، جیسا کہ ہم نے ہمارے ساتھ کیا تھا
مثال کے طور پر، تو ہم موازنہ کرنے کے لئے کچھ ہے.
لائن تین ایک لوپ جس میں ہم ختم iterate شروع ہوتا ہے
ہر ناچھانٹا ہوا عنصر.
ہم جانتے ہیں کہ تکرار کے بعد میں، کے مطابق حصہ
ہماری فہرست میں ہونا ضروری ہے کہ وہ ہر قدم کے بعد سے میں نے اس میں عناصر
قسم ایک عنصر.
تو پہلی ناچھانٹا ہوا عنصر میں جمع 1 کی پوزیشن میں ہونا ضروری ہے.
چار آن لائن کو ہم کم از کم موجودہ عناصر کا آپس میں موازنہ
عنصر ہے کہ ہم اب تک دیکھا ہے.
اگر موجودہ عنصر کم از کم سے چھوٹا ہے
عنصر، پھر ہم نئی کے طور پر موجودہ عنصر یاد
لائن پر کم از کم پانچ.
آخر میں، چھ لائنوں اور سات پر، ہم کم از کم تبادلہ
پہلے ناچھانٹا ہوا عناصر کے ساتھ عنصر ہے، اس طرح
فہرست کے مطابق حصہ انہوں نے مزید کہا.
ایک بار جب ہم ایک الگورتھم ہے ایک اہم سوال پوچھ،
خود کو کتنی دیر تک کہ پروگرامرز کے طور پر کیا ہے؟
ہم نے سب سے پہلے سوال پوچھیں گے کہ یہ کس طرح دیر اس کے لئے لے کرتا ہے
الگورتھم کو بدترین صورت میں چلانے کے لئے ہے؟
یاد ہے ہم اس دوڑ کی نمائندگی کرتے ہیں
بڑا O سنکیتن کے ساتھ وقت.
ہم کے لئے کم از کم ناچھانٹا ہوا عناصر کا تعین کرنے
بنیادی طور پر فہرست میں ہر عنصر موازنہ کرنا پڑا
فہرست میں ہر دوسرے عنصر ہے.
Intuitively، ن مربع آپریشن کے ایک O کی طرح اس تصوراتی، بہترین.
کی تلاش میں ہمارے pseudocode میں، ہم بھی ایک کے اندر اندر در اندر لوپ ہے
ایک O کی طرح ایک لوپ، جو یقینا آواز
ن مربع آپریشن کے.
تاہم یاد، کہ ہم تلاش کرنے کی ضرورت نہیں تھی
مکمل فہرست ہے جب کم از کم ناچھانٹا ہوا عناصر کا تعین کرنے؟
ایک بار جب ہم جانتے تھے کہ 4 کے مطابق کیا گیا تھا، مثال کے طور پر، ہم نے نہیں کیا
اس کو دوبارہ دیکھنے کی کیا ضرورت ہے.
تو یہ رننگ ٹائم کرتا ہے کم ہے؟
6 کی لمبائی کی ہماری فہرست کے لئے، ہم نے پانچ بنانے کے لئے کی ضرورت ہے
پہلے عنصر کے لئے آپس میں موازنہ کے لئے چار موازنہ
دوسرا عنصر، تو اور
اس کا مطلب یہ ہے کہ اقدامات کی کل تعداد کا مجموعہ ہے
1 سے 1 منفی فہرست کی طوالت integers.
ہم ایک summation کے ساتھ اس کی نمائندگی کر سکتے ہیں.
اب ہم نے summations میں یہاں نہیں جانا جائے گا.
لیکن یہ پتہ چلا ہے کہ یہ summation ن بار کے برابر ہے
ن مائنس 2 1.
یا equivalently، ن 2 مائنس ن 2 مربع.
جب asymptotic رن ٹائم کے بارے میں بات کر رہی ہے، اس ن مربع مدت
اس ن مدت غلبہ حاصل کرنے کی جا رہی ہے.
تو انتخاب کی طرح مربع ن O ہے.
کو یاد ہوگا کہ ہماری مثال میں، انتخاب کی طرح اب بھی کرنے کی ضرورت ہے
اگر چیک کرنے کے لیے ایک بڑی تعداد ہے جو پہلے ہی کے مطابق کیا گیا تھا
منتقل کر دیا جائے گا کی ضرورت ہے.
تو اس کا مطلب ہے کہ اگر ہم نے پہلے سے ہی ایک انتخاب کی طرح دوڑ
فہرست کے مطابق، اس کے طور پر اقدامات کے اسی نمبر کی ضرورت پڑے گی
جب ایک مکمل طور پر ناچھانٹا ہوا کی فہرست پر چل رہا ہوگا.
لہذا انتخاب طرح مربع (ن) کے ایک بہترین کیس کی کارکردگی ہے،
جو ہم ومیگا ن مربع کے ساتھ کی نمائندگی کرتے ہیں.
اور یہ کہ اس انتخاب کی طرح کے لئے ہے.
کئی الگورتھم ہم کر سکتے ہیں میں سے ایک
ایک فہرست ترتیب کا استعمال کریں.
میرا نام ٹومی ہے، اور اس cs50 ہے.