>> ڈوگ لایڈ تو CS50 میں ہم کے بارے میں سیکھا چھانٹ رہا ہے اور تلاش کی ایک قسم
یلگوردمز.
اور کبھی کبھی یہ ہو سکتا ہے رکھنے کے لئے ایک چھوٹی سی مشکل
کیا الگورتھم کے ٹریک کرتا ہے.
ہم واقعی صرف ہے ، بھی سطح شدہ آمدنی پر مشتمل
بہت سے دوسرے تلاش وہاں ہو اور الگورتھم چھںٹائی.
تو اس ویڈیو میں چلو صرف چند منٹ لے
کوشش کریں اور ہر الگورتھم کشید کرنا اس کے بنیادی عناصر کے نیچے
لہذا آپ کو سب سے زیادہ یاد کر سکتے ہیں ان کے بارے میں اہم معلومات
اور واضح کرنے کے لئے کے قابل ہو جائے اختلافات، اگر ضروری ہو تو.
>> پہلا انتخاب طرح ہے.
انتخاب طرح کے پیچھے بنیادی خیال چھوٹی ناچھانٹا ہوا عنصر تلاش کر رہا ہے
اور ایک صف میں کے ساتھ اس کا تبادلہ اس صف کی پہلی ناچھانٹا ہوا عنصر.
ہم بدترین کیس نے کہا کہ اس کے وقت کو چلانے مربع ن تھا.
اور آپ کو کیوں یاد کرنا چاہتے ہیں تو، لے ایک انتخاب کی طرح ویڈیو دیکھو.
بہترین کیس چلت وقت بھی مربع ن ہے.
>> بلبلا طرح، اس کے پیچھے خیال ایک ملحقہ جوڑوں تبادلہ کرنے کے لئے ہے.
تو ہے کہ آپ کی مدد کرتا ہے کہ اہم ہے یہاں فرق کو یاد.
سلیکشن طرح ہے، اب تک، smallest-- بلبلا مل
قسم ہے ملحقہ جوڑوں تبادلہ.
ہم ملحقہ جوڑوں تبادلہ عناصر میں سے اگر وہ
جو مؤثر طریقے سے، حکم سے باہر ہیں ، درست کرنے کے لئے بڑے عناصر بلبلی
اور ایک ہی وقت میں یہ بھی شروع ہوتا ہے بائیں کرنے کے لئے چھوٹے عناصر کو منتقل کرنے کے لئے.
بدترین کیس چلت وقت بلبلا کی ترتیب کا مربع ن ہے.
بہترین کیس چلت وقت بلبلا کی طرح (ن) ہے.
اس کی وجہ سے صورت حال میں ہم نے واقعی نہیں
ہم کرنے کی ضرورت نہیں کر سکتے ہیں بالکل کسی بھی سویپ.
ہم صرف ایک بنانے کے لئے ہے تمام این عناصر بھر منتقل.
>> اندراج کی طرح میں، یہاں بنیادی خیال منتقل کیا جاتا ہے.
کہ اندراج کی طرح کے لئے مطلوبہ الفاظ کی ہے.
ہم کے ذریعے ایک بار قدم کرنے کے لئے جا رہے ہیں سے صف بائیں سے دائیں.
ہم کرتے ہیں کے طور پر، ہم ہیں عناصر منتقل کی جا
ہم نے پہلے ہی کے لئے کمرے بنانے کے لئے دیکھا ہے کہیں فٹ ہونے کے لئے کی ضرورت ہے کہ چھوٹے
واپس مطابق حصہ میں.
تو ہم کے مطابق صف تعمیر ایک بائیں سے دائیں ایک وقت میں عنصر،،
اور ہم کمرے بنانے کے لئے چیزیں منتقل.
کے سب سے زیادہ کیس چلت وقت اندراج کی طرح مربع ن ہے.
بہترین کیس وقت کو چلانے کے (ن) ہے.
>> مطلوبہ الفاظ sort-- ضم یہاں تقسیم کرنے اور ضم ہے.
ہم چاہے، مکمل صف تقسیم یہ چھ عناصر، آٹھ عناصر ہے،
10،000 elements-- ہم اس تقسیم نیچے نصف کی طرف سے، نصف کی طرف سے، نصف کی طرف سے،
ہم صف کے تحت ہے جب تک (ن) ایک عنصر arrays کے.
(ن) ایک عنصر arrays کے ایک سیٹ.
تو ہم نے ایک کے ساتھ شروع 1،000 عنصر سرنی،
اور ہم نقطہ پر حاصل ہم کہاں 1،000 ایک عنصر arrays ہے.
تب ہم نے ان ذیلی arrays کے ضم کرنے کے لئے شروع واپس مل صحیح ترتیب میں.
تو ہم دو ایک عنصر arrays کے لے اور ایک دو عنصر صف بنانے کے.
ہم نے دو دو عنصر arrays کے لے اور ایک چار عنصر صف بنانے کے
اور اسی طرح اور اسی طرح ہم نے یہاں تک کہ پھر سے ایک (ن) عنصر سرنی دوبارہ تعمیر.
>> کے سب سے زیادہ کیس چلت وقت قسم ہے ضم ن کے اوقات ن لاگ ان کریں.
ہم (ن) کے عناصر ہیں، لیکن اس recombining عمل
لاگ ان ن اقدامات حاصل کرنے کے لئے ایک مکمل سرنی کرنے کے لئے واپس.
وقت کو چلانے کے بہترین کیس بھی لاگ ان ن ہے (ن) اس عمل کو واقعی نہیں ہے کیونکہ
سرنی تھا کہ دیکھ بھال حل یا نہیں کے ساتھ شروع کرنے کے لئے.
عمل ہے، ایک ہی ہے شارٹ سرکٹ چیزوں کے لئے کوئی راستہ.
تو (ن) بدترین صورت میں لاگ ان ن، (ن) بہترین صورت میں لاگ ان ن.
>> ہم دونوں کے بارے میں بات الگورتھم تلاش.
تو لکیری تلاش سب iterating کے بارے میں ہے.
ہم صف میں آگے بڑھنے ایک بار، بائیں سے دائیں کرنے کے لئے،
بڑی تعداد کو تلاش کرنے کی کوشش کہ ہم کے لئے تلاش کر رہے ہیں.
بدترین کیس چلانے کے وقت بڑا این اے ہے.
یہ iterating کر ہمیں لے سکتا ہے ہر عنصر بھر میں
ہم تلاش کر رہے ہیں تلاش کرنے کے لئے عنصر کے لئے، یا تو آخری پوزیشن میں،
یا بالکل نہیں.
لیکن ہم جب تک اس بات کی تصدیق نہیں کر سکتے ہیں ہم سب کچھ میں دیکھا ہے.
بہترین کیس ہوں، ہم فوری طور پر مل جائے.
کی سب سے بہترین کیس چلت وقت لکیری تلاش 1 ومیگا ہے.
>> آخر میں، بائنری تلاش، وہاں تھا جو مختلف سرنی کی ضرورت ہے.
کہ ایک بہت ہی یاد اہم غور
بائنری تلاش کے ساتھ کام کرتے وقت.
یہ اندازہ لگانے والے کا استعمال کرتے ہوئے کے لئے ایک شرط ہے آپ کے ذریعے تلاش کر رہے ہیں اس صف
حل کیا جانا چاہئے.
دوسری صورت میں، مطلوبہ الفاظ تقسیم اور فتح ہے.
نصف میں صف تقسیم اور عناصر میں سے نصف کو ختم
ہر وقت آپ کے ذریعے آگے بڑھنے کے طور پر.
اس کی وجہ سے تقسیم اور فتح کے اور نصف نقطہ نظر میں تیز چیزوں،
بدترین کیس چلت وقت کے بائنری تلاش ہے
کافی ہے جس میں، لاگ ان ن لکیری تلاش کی (ن) سے بہتر.
سب سے مقدمہ چلانے اب بھی وقت ہے.
>> ہمیں فوری طور پر اسے تلاش کر سکتے پہلی بار ہم نے ایک ڈویژن ہے، لیکن
ایک بار پھر، یاد رکھیں کہ بائنری تلاش ہے، اگرچہ
لکیری تلاش کے مقابلے میں کافی بہتر لاگ ان ہونے کی وجہ سے ن بمقابلہ،
آپ کو کام کے ذریعے جانے کے لئے ہو سکتا ہے ، سب سے پہلے اپنے صف چھںٹائی کی جس
منحصر ہے یہ کم مؤثر ہو سکتا ہے حل iterating کی سائز پر.
>> میں ڈوگ لایڈ ہوں، اس CS50 ہے.