[Powered by Google Translate] [3 ہفتے جاری]
>> [ڈیوڈ J. Malan - ہارورڈ یونیورسٹی]
>> یہ [CS50 ہے. CS50.TV] -
>> ٹھیک ہے. واپسی پر خوش آمدید. یہ CS50 ہے اور اس کے 3 ہفتے کے آخر ہے.
>> تو ان مجریچت، اور گزشتہ سال کے لئے ہارورڈ شروع انوویشن لیب کیا کہتے ہیں،
یا میں لیب، جو HBS کیمپس پر ایک دریا کے پار شاندار عمارت ہے
ہے کہ کالج کے طلباء، GSAS طالب علموں، تمام بھر میں کیمپس سے طلباء کے لئے کھلے ہے،
اساتذہ بھی شامل ہیں، اور اسے جدید چیزوں پر مل کر کام کرنے کے لئے آنے کی جگہ ہے،
خاص طور پر ملکیت چیزیں
اگر آپ اور 0 یا اس سے زیادہ دوست ملکیت کچھ کرنے کے بارے میں سوچ رہے ہیں
یا تو اس کلاس کے دوران، اس کلاس کے بعد، سے باہر یا.
>> تو چیزیں وہ J اصطلاح پر کیا میں سے ایک ان دوروں کا ہے،
جن میں سے ایک نیو یارک، جن میں سے ایک سلیکن ویلی ہے.
خلائی بہت محدود ہے، لیکن یہ ایک یمبیی کے ساتھ کندھوں پر مسح کا موقع ہے
اور کیمپس بھر میں اور اصل میں گریجویٹ طالب علموں کو ان کے متعلقہ علاقوں میں وقت بتانا
startups چیٹنگ، ادیمیوں کی چیٹنگ اور طرح.
تو اگر دلچسپی رکھنے والے، اس یو آر ایل کو یہاں چیک کریں.
یہ بھی آن لائن سلائڈ پر دستیاب ہے.
>> ہم گھر آڈیو سر صرف تھوڑا سا سکتے ہیں؟
اگر آپ اس جمعہ ہمیں دوپہر کے کھانے کے لئے اپنے ساتھ شامل ہونے کی چاہتے ہیں، آگ اور برف میں 1:15 بجے، براہ مہربانی، وہاں کی قیادت.
اگر مستثنی تقاضہ فارم پہلے ہی وقت تم وہاں پہنچ بھری ہوئی ہے.
لیکن ہم اس روایت کو آگے بھی جاری رکھیں گے.
>> آج ہم مختلف مسائل ہم حل کر سکتے ہیں کے اعلی سطح پر بحث جاری ہے،
بہت کم توجہ مرکوز آج، کم از کم، کوڈ پر بہت زیادہ اور خیالات پر.
تو 0 ہفتے میں واپس لگتا ہے جب ہم نے نصف میں ایک فون کتاب پھاڑ،
جس کا مقصد کچھ کرنا تھا، اس کا اقرار، تھوڑا سا ڈرامائی
لیکن نقطہ بھیجنے کے لئے کہ تلاش پر نہیں ہے، ضروری،
پہلی نظر جیسا کہ آپ یہ سمجھتے ہیں کہ ہو سکتا ہے کے طور پر واضح ہے.
اور عام طور پر مسائل کو حل کرنے کے ضروری ہمیشہ نہیں سب سے بہتر ہو سکتا ہے -
سب سے زیادہ واضح حل ضروری سب سے بہتر نہیں ہو سکتا ہے.
تو ہم نے اس فون کی کتاب ہے، اور سچ کہوں تو، اس کمرے میں ہم سب کے instincts تھا،
سب سے زیادہ ہونے کا امکان ہے، درمیان میں جب مائیک سمتھ کی تلاش میں شروع کرنے کے لئے اور اس کے بعد بائیں یا دائیں جا
حروف تہجی کے جو خط ہم پر ختم ہوا کی بنیاد پر ہے.
>> لیکن اس سادہ خیال ہے کہ ہم انسانوں کے لئے لے لیا ہے اتنی دیر کے لئے حاصل کی جاچکی
واقعی آپ کے دماغ کے استعمال میں صف میں آنا شروع کر دینا چاہئے
، کے طور پر مسائل کو ایک فون کی کتاب سے کہیں زیادہ پیچیدہ جاؤ کیونکہ
وہی آسان، شاندار بصیرت ہیں جو ہمیں کرنے کی اجازت دینے جا رہے ہیں
بہت زیادہ پیچیدہ اور زیادہ دلچسپ مسائل کو حل کرنے،
چیزوں میں سے کچھ کو ان کے درمیان ہم لگ ان دنوں پہلے ہی حاصل کی جاچکی ہے.
وہاں ویب صفحات، اور ابھی تک گوگل اور بنگ اور طرح کے اربوں
اس طرح ہمارے لئے چیزیں تلاش کرنے کے قابل ہیں.
یہ ایک لکیری تلاش کا استعمال کرتے ہوئے کی طرف سے نہیں ہو رہا ہے، ہر ممکن ویب صفحات کے ذریعے تلاش.
فیس بک آپ کو بتانا جو آپ کے دوستوں میں سے تمام یا دوستوں کے دوست ہیں کے قابل ہے،
اور وہ بھی بظاہر ایک پل میں کیا ان دنوں کیا جا سکتا ہے
اگرچہ وہ لاکھوں صارفین کی ہے.
>> اور اس طرح بالآخر کو کم کس طرح ہم اس پیمانے پر اصل مسائل کو حل کریں گے
ہم 0 ہفتے میں خیالات کی طرف دیکھ رہے تھے آج اور تھوڑی ہے.
ہم اس الگورتھم نہیں دوبارہ پھانسی، جائے گا، لیکن یاد ہم نے بھی 0 ہفتے اس مشق میں کیا
جہاں ہم سب نے کھڑے تھے، 1 نمبر پر لے،
اور پھر ہم نے جوڑا بنانے کی طرف سے سب کو خود شمار تھے، اپنے تعداد کو ایک ساتھ مل کر انہوں نے مزید کہا،
تو گروہ کے نصف ہر iteration پر بیٹھ گیا.
تو ہم 500 طالب علموں میں سے 250 سے 125 گئے اور وغیرہ.
لیکن جیسا کہ ہم نے کہا کہ پیر کو، طاقتور وہاں خیال
یہ تھی کہ اگر ہم اس مسئلہ کا سائز دگنا
اور جسٹس یا EC 10 سے تمام بچوں کے کمرے میں واپس آئے اور ہمیں میں شمولیت اختیار کی،
ٹھیک ہے، ہم شاید تاکہ اسے تمام اجماع گروپ شمار کر سکتے ہیں
لوپ صرف 1 اور بڑے iteration کے ساتھ کیونکہ وہ سائز صرف شاید دوگنا ہوگا
یا الیکشن کمیشن 10 تھوڑی ڈبل سائز سے زیادہ کیس میں.
اور اس طرح ہم تھوڑا سا زیادہ وقت خرچ ہوگا،
لیکن ہم 400 یا 700 مزید اقدامات پر خرچ کرنے کی ضرورت نہیں کریں گے.
>> صرف ایک طریقہ ہے کہ تھوڑا کم خلاصہ ہے میں اس تصویر کو پینٹ، ہر کھڑے ہونے کے لئے ہے چلو.
لیکن اگر تم میں سے ان لوگوں کو برا نہیں لگے گی جو آج آرکسٹرا میں بیٹھ کا انتخاب کیا ہے کھڑے
چلو دیکھتے ہیں اگر ہم تم میں سے اعداد و شمار کر سکتے ہیں جو سب سے بلند انسان ہے
تقابلی الگورتھم کے اسی طرح کام کرتے ہوئے.
تو اگر آپ آرکسٹرا، میرے مستثنی تقاضہ، لیکن مرحلہ نمبر 1 میں بیٹھے رہے ہیں، کھڑے ہو جاؤ؛
2 قدمی، قریبی تم نے کسی کے ساتھ جوڑی،
شخصیت جو طویل ہے، اور اگر آپ چھوٹے ہیں بیٹھ.
پھر دہرائیں.
[طالب علموں بڑبڑا]
>> ٹھیک ہے.
ٹھیک ہے. ایک کھڑے رہ گیا ہے. آپ کا نام کیا ہے؟ >> اینڈریو.
>> اینڈریو، آپ آرکسٹرا کے حصے میں بلند ترین شخص آج ہیں.
>> مبارک ہو. [تعریف اور اتساہی] ٹھیک ہے. ایک سیٹ ہے. تو ہم اینڈریو پایا.
لیکن مثال کے طور پر میں کتنا وقت آپ کے وزٹرز کا ریکارڈ رکھا ہوتا،، اینڈریو تلاش کرنے کے لئے
50 + یا تو افراد کے اس آرکسٹرا کے سیکشن میں؟
میں ایک کافی آسان نقطہ نظر لیا جا سکتا ہے اور یہاں شروع.
اور میں 2 افراد نے کھڑے ہیں اور میں صرف ان کا آپس میں موازنہ،
اور اس کے بعد میں جس نے تھوڑا سا چھوٹا ہے کا کہنا ہے کہ، "ٹھیک ہے، آپ بیٹھ جاؤ،
اور مجھے یاد لمبے شخص کون تھا کے لئے جا رہا ہوں.
پھر میں دوبارہ دوبارہ، دوبارہ، اور میں بلند شخص کو پھانسی
جب تک میں کسی کو تھوڑا سا ان سے لمبے کس موڑ پر ملے ہیں،
تھوڑا سا چھوٹا شخص تو نیچے بیٹھ ہے.
لیکن اس آرکسٹرا کے سیکشن میں اس الگورتھم میں، اگر تم میں سے (ن) ہے،
کتنے قدم لینے والے الگورتھم ہے؟ >> [طالب علم] N.
>> ن لے، ٹھیک ہے، کیونکہ بدترین صورت میں، تو بات کرنے کی جا رہی ہے،
بلند شخص کو آخری شخص ہے کہ میں صرف بے ترتیب بدقسمتی کی طرف سے حاصل کرنے کے لئے ہے.
تو بدترین صورت میں، اس الگورتھم کی رننگ ٹائم لکیری ہے، (ن) ہے،
N خلا میں لوگوں کی کل تعداد، اس مسئلے کے سائز کہاں ہے.
اس الگورتھم کے بارے میں کیا خیال ہے؟
حقیقت یہ ہے کہ آپ سب کھڑے ہو اور پھر تم میں سے دوبارہ نصف بیٹھ
تم میں سے نصف بیٹھ، تم میں سے نصف بیٹھ گیا.
کس طرح بہت سے اقدامات ہیں جو کیا جانا چاہئے اگر تم میں سے (ن) کے یہاں ہے؟
[طالب علم] N لاگ ان ن. >> اس کا برا ہو گا. ن لاگ ان کریں.
>> تو لاگ ان ن، یہاں تک کہ اگر آپ کافی نہیں کیا لاگرتھم ہے یاد،
اب کے لئے، کی تعریف کرتے ہیں کہ یہ halving اور اس halving اور halving پر کسی نہ کسی طرح سے متعلق ہے.
2 ایک عنصر نہیں ہے. یہ 3 کا ایک عنصر ہو سکتا ہے.
لیکن یہ ایسے عنصر کے اسی قسم کی یہ تکرار ہے کہ اس مسئلے کے سائز یہاں سے شروع ہوتا ہے
لیکن اس وقت فوری طور پر یہاں ہے، تو یہاں، تو، تو یہاں ہے.
آپ چھوٹے کاٹنے نہیں لے رہے ہیں مسئلہ سے باہر، آپ واقعی اس کو دور کر رہے ہیں کاٹ
ایک بڑے کے ساتھ جھپٹا ہر وقت گر گئی.
تو ہم 50 افراد تھے، پھر 25، پھر 12 ½ یا 13 لوگ کھڑے،
آخر میں صرف اینڈریو چھوڑ دیا گیا تھا کھڑے تک تو 6 ½ وغیرہ.
تو ہم ہے کہ (ن) کے لاگ ان کو فون کر رہے ہیں، اور آپ کو دیکھ اس کے طور پر مندرجہ ذیل کر سکتے ہیں.
اس تصویر کو یہاں یاد جہاں ایک لکیری کا الگورتھم سرخ لکیر کی طرح ہے،
پیلے رنگ لائن 2s الگورتھم کی طرف سے شمار یہ تھا کہ ہم نے گنتی کے طالب علموں کے لئے استعمال کیا جاتا ہے
ماضی میں، لیکن آج مقدس grail اس سبز لائن رہنے کی جا رہی ہے
اگر ہم آرکسٹرا کے حصے میں لوگوں کی تعداد دگنی ہو یا صرف جہاں نے کہا کہ،
جہنم، دو پورے کمرے میں سب کھڑے ہو جاؤ، اتنا بڑا سودا نہیں
کیونکہ ہم تقریبا دوگنا کتنے لوگ یہاں ہیں،
1 مزید iteration، کوئی مسئلہ نہیں ہے.
>> ہم نے محسوس کیا ہے اینڈریو یا جس اینڈریو سے طویل ہوتا ہے
mezzanine ان کریں یا بالکنی میں.
تو اس سادہ خیال ہے کہ ہمیں اتنی زیادہ لیا کے لئے ایک فون کی کتاب میں حاصل کی جاچکی ہے،
احساس ہے کہ بہت سے مختلف مقامات پر جس میں ہم اسے درخواست دے سکتے ہیں.
اصل میں، بجائے شبدجال پہلے - بس کچھ شبدجال تپپڑ مارنے کی
مجھے اس تصویر میں یہاں.
ابھی تو ہم نے (ن) اور (ن) / 2 کے بارے میں بات کی اور (ن) کی لاگ ان کریں،
لیکن ہم یقینی طور پر کے ساتھ آئے جیسا کہ ہم سمسٹر کے دوران کر سکتے ہیں،
ریاضیاتی فارمولوں کے دیگر طرح وقت چلانے کے اس عام تصور کی وضاحت.
یہ اب کے لئے سیاق و سباق سے باہر ہیں کیونکہ ہم دیکھتے سے بہت پہلے کریں گے
یلگوردمز کہ یہ اصل کی نمائندگی.
>> لیکن یہاں لکیری لائن (ن)، براہ راست لائن، اصل میں بہت کم ہے کی طرف اشارہ کرتے ہوئے ابھی نوٹس
یہ ایک نظری برم کی طرح ہے کہ ہم صرف تبدیل کیا x محور کی نمائندگی کرتا ہے ہے
اور Y محور، اور ہم کسی بھی سمت ہم چاہتے ہیں میں ایک براہ راست لائن کے نقطہ بنا سکتے ہیں.
لیکن وجہ یہ ہے کہ یہ اتنا بظاہر فلیٹ اب
کیونکہ ہم بہت سست چل رہا ہے وقت کے لئے اس گراف پر جگہ بنانے کی ضرورت ہے ہے.
اب پتہ ہے کہ زندگی میں کچھ بہت برا یلگوردمز ہیں،
ن اقدامات کو جن میں سے کچھ نہیں لے کرتے ہیں یا بہتر ابھی تک، ن اقدامات لیکن اس سے زیادہ لاگ ان کریں.
تو کی لکیر سے اوپر (ن) یہاں نیچے نوٹس N ن کے اوقات لاگ ان کریں
ہم دیکھتے ہیں اور کیا اس کا مطلب یہ ہے کہ پہلے طویل گے.
جو اوپر ہے مربع ن اور ہم کسی ن مربع یلگوردمز نہیں دیکھا ہے ابھی تک لیکن ہم کرنے کے بارے میں ہیں.
اور یہ بہت برا لگتا ہے.
ن 2 ہے، اسیاتی کچھ، جو بھی برا محسوس ہوتا ہے.
اور ابھی تک، دلچسپ، تو پھر این cubed، جو اگر تم آگے سوچنے کی طرح ہیں،
اگر آپ کی قسم (ن) ریاضی، 2 اصل straighter زیادہ ہو جاتا ہے،
(ن) سے زیادہ cubed اگر آپ محور پر نظر اب تک کافی باہر ہے.
تو اب محسوس یہ کلہاڑی منمانے 2 x محور پر 10 ہیں.
>> اور اس کا کیا مطلب ہے؟
اس کمرے میں 2 افراد سے 10 لوگوں کو مطلب ہے.
اس مسئلے کے سائز، جو سیاق و سباق ہے: یہ تمام ایکس کا مطلب ہے.
اور ایک عمودی محور ابھی اور یا اقدامات کی تعداد کی تعداد ہے -
وقت میں سے کچھ یونٹ ہے.
نوٹس لیکن کہ یہ 0 60 0 10.
لیکن اگر باہر زوم ہم کے طور پر آپ کو ایکسل یا کسی چارٹنگ سافٹ ویئر میں طاقت، قسم،
اور ہم نے 200،000 تک جاؤ، نوٹس ہے کہ 2 کی طرح ن سے کچھ
، مربع ن کے مکمل طور پر چل رہا بار مغلوب جا
ن cubed، ن لاگ ان N - سب کچھ کے بارے میں ہم بات ابھی تک ہے.
اور ابھی تک پکڑنے یہ ہے کہ آپ فیس بک کی طرح چیزوں کے بارے میں بات کرنا شروع کر
آپ کو بہت سے، بہت سے، بہت سے لوگ جہاں سب باہم ہے،
تم لوگوں کو ن ہے، جن میں سے ہر ایک (ن) کے دوستوں کی طرح بہت سے ہو سکتے ہیں
اگر ہر کسی کو دنیا میں یار دوست کی طرح ہے،
ٹھیک ہے، یہ (ن) کے اوقات (ن) پہلے ہی، تاکہ مربع ممکن دوستی کو ن ہے،
کم از کم 1، سمت، ن مربع ممکن دوستی میں.
، تو وہ پہلے ہی تجویز کیا گیا ہے کہ فیس بک کے سماجی گراف کی تلاش، تو بات
فارمولوں کی اس قسم میں ظاہر کیا جائے شروع کر سکتے ہیں.
>> ہم واپس آئے اور یہ بہت زیادہ ٹھوس بنا دیں گے،
لیکن اگلے کئی ہفتوں کے لئے اب، اس کا مقصد
پر عملدرآمد الگورتھم یا کوڈ کے بارے میں نہیں جانے کے لئے اس بات کا یقین ہو جا
جو کچھ اس طرح کے طور پر زیادہ سے زیادہ وقت لے رہا ہے آخر.
لیکن کمپیوٹر سائنس کے بارے میں دلچسپ بات ہے اگر آپ نے اس شعبے میں جاری
، CS121 CS124 طرح کلاس لے رہا ہے، جن میں سے دونوں نظریہ کورس
یہ ہے کہ اصل میں کچھ مسائل ہیں جو اس دنیا میں موجود ہیں
کہ بنیادی طور پر، جہاں تک ہم جانتے ہیں، تیزی سے کسی بھی نہیں کیا جا سکتا ہے حل
سے ان گراف کے سب سے زیادہ اصل میں پتہ چلتا ہے.
تو اس دنیا میں کھلا مسائل، بہت سے بہتر انسان اس طرح اب تک ہے کی ایک بہت ہے.
>> تو اس مثال سے تو شروع.
ہم اس پر کیمرے کے ساتھ شان جدوجہد بھی awkwardly ویڈیو پر دیکھا تھا.
لیکن حقیقت تھی جب شان یہ نمبر 7 کی طرح ایک بورڈ پر تلاش کرنے کا کام سومپا گیا تھا،
کو یاد ہوگا کہ میں نے کہا کہ، "کاغذ کے یہ ٹکڑے ٹکڑے یا سفید دروازے کے پیچھے کہیں ہے
"نمبر 7 شان، ہمارے لئے اسے تلاش."
اور یہ wonderfully دیکھنے عجیب تھا
کیونکہ وہ واقعی اس مسئلے کے ساتھ جدوجہد کر رہا تھا.
لیکن حقیقت تھی شان کے ساتھ ساتھ کیا ہے کمرے میں کسی کو بھی کیا کر سکتے ہیں.
وہ تھوڑی دیر ایک عام شخص کے مقابلے میں لیا ہو سکتا ہے،
لیکن انہوں نے فرض کر لیا گیا ہے کہ اس مسئلے کا کچھ چال تھی،
انہوں نے مانا ہے کہ انہوں نے کچھ یاد آ رہی تھی.
مدد اور نہیں تھا کہ سینکڑوں کی آنکھوں کی اس کو برداشت کر رہے تھے.
>> لیکن حقیقت تھی اگر مسئلہ ان پٹ بے ترتیب اعداد کی ایک گروپ ہے
اور آپ جا رہا ہے 1 ایسے نمبر کو تلاش کرنے کے لئے کہا،
سب سے بہتر آپ کر سکتے ہیں لکیری تلاش ہے.
بائیں سے شروع، حق پر منتقل کرنے کے لئے، یا حق میں شروع، بائیں منتقل کریں.
Retroactively، ہم سوچ رکھا جائے ہو سکتا ہے، "شان؛، تمہیں صرف دوسرے سرے سے کیوں نہیں کیا شروع کریں؟"
ٹھیک ہے، 7 کے طور پر آسانی سے کر سکتے ہو تصادفی ہے،
لیکن میں جان بوجھ کر اسے وہاں ڈال دیا کیونکہ میں نے سوچا وہ جا رہا آخر میں شروع کرنے کے لئے نہیں ہے.
لہذا میں نے اس قسم کی صورت حال ہیرا پھیری، لیکن بے ترتیب 7 موقع کی طرف سے کسی بھی جگہ ہو سکتا ہے.
تو صحیح آخر سے شروع ہونے والے بہتر رہی ہے تو ہو سکتا ہے،
لیکن اگر اگلے سال میں 7 دوسری جگہوں پر منتقل کیا ہے؟
یہ ایک بنیادی طور پر نئے مسئلے کا حل نہیں ہے -
1 آخر یا دوسرے سے شروع - جب آپ کے پاس کوئی دیگر مفروضات دی کر رہے ہیں.
تو شان نمبرز کے ذریعے تلاش کرنا شروع کر دیا اور انہوں نے کہا کہ، "5 وہ یہاں نہیں ہے."
پھر وہ یہاں چلا گیا اور 19 نے دیکھا، اس کے بعد انہوں نے تقریبا 20 سیکنڈ کے لئے روک دیا گیا،
اس کے بعد انہوں نے 13 کے لئے کھول دیا، اور پھر یہ ظاہر بن گیا
کہ ایک نمونہ یہاں نہیں لگتا ہے.
1، 2، 3، 4 یا جیسا نہیں تھا. تعداد میں فرق، جو مدد نہیں تھا.
اور بھی حقیقت یہ ہے کہ میں کاغذ کے ان سستے ٹکڑوں کا استعمال کیا تعداد کو پورا کرنے کے
اصل میں جان بوجھ کر، کیونکہ اگر میں کاغذ کے ان تمام ٹکڑے ٹکڑے کو خارج کر دیا، ہے،
ہم میں سے سب سے زیادہ، شان، شاید طرح macroscopically glanced گے
بلیکبورڈ اور نے کہا، "اوہ، 7 ظاہر ہے وہاں." ہم نے اسے فوری طور پر کیا ہے.
>> اور اس طرح انسانی دماغ کسی حد تک کام ہو سکتا ہے،
لیکن حقیقت میں، اس کی آنکھوں یا ذہن شاید دائیں سے بائیں تعداد skimming
باہر صحیح درمیان چھوڑ دیا - کچھ physiologically جا رہا تھا
ایسی ہے کہ یہ محسوس کیا جیسے اسے فوری طور پر ہو رہا ہے،
لیکن مشکلات بھی ہیں اندرونی 7 تلاش کرنے کے طریقہ کار کے کچھ قسم ہے.
اور یقینا، اب کہ ہم arrays اور ڈیٹا ڈھانچے کے بارے میں بات کر رہے ہیں
اور ایک کمپیوٹر کی یاد کے اندر صرف ایک ہی چیز ہم انسان کرتے ہیں، کر سکتے ہیں
انفرادی میموری مقامات پر ایک وقت میں 1 دیکھو.
>> تو ہر دوسرے مقام کے طور پر اچھی طرح سے کاغذ کے کچھ ٹکڑے کے ساتھ ہو سکتا ہے کو احاطہ کرتا ہے
کیونکہ ہم اسے دیکھ نہیں ویسے بھی کر سکتے ہیں. ہم ایک وقت میں 1 بات ہی کر سکتے ہیں.
تو اس معاملے میں، کی شان کے معاملے میں، ہم یہاں چلے گئے اور اس کے بعد ہم یہاں گئے
اور اس کے بعد ہم یہاں گئے، یہاں، یہاں، یہاں، آخر تک ہوشیار ہے
اور صرف کی قسم یہ ایک منمانے چھوڑا اور وہاں 7 پایا.
یہ ایک خاص طور پر خاص نہیں تھا. یہ بھی حکم سے باہر تھا.
لیکن انہوں نے آخر میں 7 پایا.
لیکن اب takeaway واقعی یہ ہے کہ سب سے بہتر آپ کر سکتے ہیں جب کوئی معلومات نہیں دی
تصادفی کے مطابق تعداد کے علاوہ بائیں سے شروع کرنے کے لئے یا حق سے شروع کی ہے.
یا heck، آپ کو تصادفی دروازے کھول، پھر بھی سکتے ہیں لیکن کیا یہ بے ترتیب ہو کا مطلب ہے؟
ٹھیک ہے، ہم کسی نہ کسی طرح سے رسمی طور پر پڑے گا جو اسے یہاں شروع کرنے کا مطلب،
تو جاؤ، تو یہاں جانا. شان بہت اچھا کیا، اور یہ صرف مذاق تھا دیکھنے.
کیا بجائے اگر ہم اس مسئلے کو تھوڑا سا تبدیل کرنے اور اس سال کے شان لانے کے لئے، اگر آپ؟
آرام دہ اور پرسکون کسی کو بھی اسٹیج پر آ رہے ہیں اور ایک تھوڑا سا مختلف مسئلہ کے حل کی جائے گی
اور کیمرے پر دکھائے جانے؟
>> چلو آرکسٹرا سے باہر کیونکہ تم لوگ آج بہت پہلے ہی شامل ہیں.
گلابی میں کے بارے میں کیا ہے، ٹوپی میں؟ ذیل آو. آپ کا نام کیا ہے؟ >> یلیکس. >> یلیکس. ٹھیک ہے.
تو یلیکس نے اس سال کے شان ہو جائے گا اور اگلے چند سال میں دکھایا جائے گا
CS50 لیکچر کے قابل ہے.
یلیکس، آپ سے مل کر اچھا لگا. >> تم بھی ملنے کر اچھا لگا.
آپ کے لئے ہاتھ میں چیلنج ہے کہ آپ اسے تھوڑا سا آسان ہے
کہ میں تم سے کہہ ایک ہی تعداد رہا ہوں یہاں، لیکن وہ اب کے مطابق ہیں.
لہذا اب آپ کا مقصد یہ ہے کہ نمبر 7 کو تلاش کرنے کے لئے ہے.
، you're طرح کی دھوکہ دہی کا ایک کمپیوٹر کی مانند نہیں کرے گی - اور اصل میں، ہم نے یہ واقعی کرنا چاہئے
کیا دیکھ کے ذریعے کی تعداد ایک لمحے پہلے تھے.
چاک کے ساتھ اس اصل میں یہ سب زیادہ مدد کرنے کے لئے نہیں ہے،
لیکن دکھاوا کہ تم نہیں جانتے کہ اصل صف ہے.
اب آپ جانتے ہے کہ آپ کے مطابق تعداد کے ایک صف ہے
ہے جو ان دونوں کے درمیان فرق ہے، اور آپ کا مقصد یہ ہے کہ نمبر 7 کو تلاش کرنے کے لئے ہے ہے.
، تم کس طرح ایک معقول انسان نمبر 7 کی تلاش کے بارے میں، جاؤ گے؟
>> ہائی کم سے چلے جاؤ؟ ٹھیک ہے. >> ہائی کم جاؤ.
اور ان کے آنسو نہیں ہے. ہم صرف انہیں اٹھا تو ہم ان کے دوبارہ استعمال کر سکتے ہیں.
ٹھیک ہے، تو 1. انتظار کریں. اس سے پہلے کہ آپ جا رہو، کہ 1، واضح طور پر غلط تھا.
تو آپ کے دماغ میں کیا اگلے جا رہا ہے؟ آپ کی اگلی چال کیا ہے؟
اگلے ایک ہے. ٹھیک ہے. >> اگلے ایک ہے. اچھی بات ہے. 3، بہت غلط. آپ کی اگلی چال کیا ہے؟
جانے پر رہو. >> ٹھیک ہے. جانے پر رہو. 5.
تو جا رہیں، اور مجھے تم سے اولاد کے لئے اس ہاتھ.
7. >> بہترین. بہت اچھا ہے. نمبر 7 ملا. [تعریف]
تو یہ اچھا تھا، لیکن شان بھی نمبر 7 مل گیا ہے.
اور میں لوگوں کا کہنا ہے کہ آپ کو معلومات کے اس اضافی ٹکڑا نہیں استحصال،
جس میں یہ ہے کہ یہ اعداد و شمار کے مطابق کر رہے ہیں.
تو ہم بہتر کر سکتا ہوں؟ یہاں کوئی تجاویز نہیں؟ جی ہاں، پیچھے.
[طالب علم] بائنری تلاش. >> مجھے کوئی اندازہ نہیں ہے بائنری تلاش کیا ہے ہے.
>> [طالب علم] وسط میں شروع کریں. >> وسط میں شروع کریں. ٹھیک ہے. تو چلو دیکھتے ہیں، اگر ہم وہاں حاصل کر سکتے ہیں.
تو بجائے اگر تم درمیان سے شروع کہا رہے ہیں، آگے بڑھو اور درمیانی دروازہ کھولو.
ان میں سے 8 ہے، تو آپ کو منمانے ایک کا انتخاب کرنے جا رہے ہیں
تھوڑا سا بائیں یا دائیں. ٹھیک ہے. 7! [تعریف] بہت اچھا.
ٹھیک ہے، لیکن جہاں ہم اس کے ساتھ جا رہے تھے؟
چلو صرف ٹائی تم یہاں شروع کیا تھا توڑ خیال سے
اس لیے کہ وہ یکساں طور پر اچھی طرح سے کے طور پر ہو سکتا تھا.
ہم تو صرف یہ جانتے ہیں کہ 7 وہاں تھا ہوا. تو یہ 13 ہے.
لہذا اگر وہ حل کر رہے ہیں اور ہم صرف درمیان میں شروع کیا،
زیادہ سے زیادہ اگلی چال کیا ہوتا ہے؟
بائیں جاؤ. اور اس طرح یہاں فون بک مثال کے طور پر پھر سے آتا ہے.
اگر یہاں 13 ہے اور ہمیں معلوم ہے کہ فہرست کے مطابق ہے،
تو کاغذ کے ان ٹکڑوں کے ہم سب اب uninteresting رہے ہیں
کیونکہ ہم نے پہلے سے ہی جانتے ہیں کہ 7 بائیں طرف ہونا چاہیے
اگر ان کی تعداد کے مطابق ہے اور ہم 13 پائے جاتے ہیں.
>> تو کیا آپ کی اگلی یہاں اقدام ہے؟ >> بائیں طرف دیکھیں. >> ٹھیک ہے، اچھا ہے.
تو بائیں، اور - رکو، ہے، ہے، ہے. یہ دھوکہ دے رہی ہے.
تو تم نے 7 پایا جاتا ہے، لیکن الگورتھم ہم صرف درخواست کیا تھا؟
درمیان میں شروع کریں. >> اچھا لگا. تو کیا ہے جو ایک ہی خیال کے منطقی توسیع ہے؟
اوہ، صرف ان کے لئے ہے. بالکل ٹھیک ہے. >> >> تو میں یہاں شروع ہو جاتے ہیں. >> اچھا لگا.
تو اب ہم بائیں طرف تھوڑا سا پھر سے چلے گئے. 3 ہے.
لیکن دلچسپ takeaway ہے جو کسی کو آپ کی پرواہ نہیں ہے؟
2 یہ. >> 2 یہ. تو اب اس سے دور جا سکتے ہیں، اس کے لئے اس سے دور کی جا سکتی ہے.
اب مسئلہ یہ ہے کہ 8 تھا تو تھا حجم 4 2 سائز ہے.
ہم کافی قریب ہو رہے ہیں. پھر ان 2 عناصر کے درمیان.
>> ٹھیک ہے. تو اس طرح بدقسمتی ہے کہ اب ہم ہمیشہ چھوڑ جا رہے ہیں کیونکہ ہم نے پکڑ دھکڑ نیچے ہیں.
لیکن یہ ٹھیک ہے کیونکہ اب ہم اس دور اور سب کچھ پھینک، صرف 7 کے ساتھ ہم چھوڑ کر.
کی تعریف کی ایک گول دے دو. ہم 7 پھر سے مل گئی. [تعریف] ٹھیک ہے. اس بات کا یقین.
صرف 1 دوسری کے لئے رکو.
اگرچہ کہ آئندہ کے عمل کی طرح اب تھوڑا لیا سے ہم نے محسوس کیا یہ چاہتے ہیں،
سچ کہوں تو، آپ یہاں پہلے مرتبہ instincts سب سے بہتر تھے، ٹھیک ہے؟ ہم فوری طور پر 7 پایا.
لیکن ہم 7 ہے تیز کریں گے مل گیا ہے، اس کے مقابلے میں کوئی بھی معاملہ اس مثال میں کیا،
اگر اعداد و شمار کے مطابق کر رہے ہیں، کیونکہ ایک فون کی کتاب میں صفحات کی طرح
آپ کو مسئلے کا نصف واقعی بار بار بار کاٹ کر سکتے ہیں.
اور یہ بہت ہی آسان ہے 8 صرف تعداد کے ساتھ اس کو دیکھنے کے لئے نہیں
1،000 صفحے فون بک ہے جہاں آپ واقعی اسے نابینا دیکھ کے خلاف
لیکن یہاں اس صورت میں جب شان 7 کے لئے تلاش کر رہا تھا،
کتنے بدترین صورت میں اقدامات اسے لیا ہوتا؟ >> [طالب علم] 7.
بدترین صورت میں 7. ، بدترین 7 اگر 8 دروازے یہاں نہیں ہے.
یہ اسے 8 اقدامات لیا.
>> تو اگر (ن) کے دروازے، یہ شان ایک جوڑے سال پہلے ہو سکتا ہے نے ن اقدامات.
اب تمہارے معاملے میں، یلیکس، دیا ہے کہ ان کی تعداد کے مطابق کر رہے ہیں -
اور ہم جہاں ہم اس کہانی میں اس طرح اب تک کیا گیا ہے سے اندازہ کرنا اس کی طرح کر سکتے ہیں -
یلیکس زیادہ ذہین الگورتھم چلانے کا وقت ہو گیا ہے
وسط سے شروع اور پھر دہرانے کا؟
[3 طالب علم]. >> تو وہ 3، موٹے طور پر، اگر آپ کو 8 سے 4 سے 2 سے 1 جا رہا ہے.
3 اقدامات تو یا، عام طور پر، لاگ ان ن دوبارہ ہے.
کسی بھی وقت آپ کو halving اور halving اور halving اور halving رہے ہیں،
لاگ ان ن کے اس خیال کا اظہار ہے.
اور اس لئے کہ تم صرف 3 اقدامات کریں گے لیا، اور بیشک اس نے
ایک بار ہم نے کھولا دروازے halving اور halving،
جبکہ اس شان 7 کچھ یا 8 اقدامات لیا.
تو آپ کو ہمارے ساتھ اس سال ہونے کی وجہ سے کے لئے شکریہ. >> آپ کا شکریہ. آپ ملاقات کر اچھا لگا.
یلیکس کرنے کے لئے آپ کو شکریہ ادا کیا. اسی طرح. >> [تعریف]
>> تو اس کا حقیقی مطلب کیا ہے؟
اب یہ تصور کریں کہ یہ 8 دروازے، جو واضح طور سے، ہم میں سے سب کچھ مل سکتا ہے نہیں ہے
پیچھے صرف کاغذ کے ٹکڑے ٹکڑے کرنا اورکپڑے پھاڑنا اور ہمارے instincts کے ساتھ جا کر 8 کافی تیزی سے دروازے.
لیکن کیا اگر یہ ایک ملین دروازے ہے؟ کیا ہوگا اگر یہ 4 ارب دروازے ہے؟
4 ارب دروازے کے معاملے میں، آپ واقعی میں یلیکس الگورتھم کے ساتھ جانے کے لئے کرنا چاہتے ہیں جا رہے ہیں،
بائنری تلاش کے طور پر ہم اسے بلا شروع یا تقسیم اور فتح، زیادہ عام طور پر کریں گے،
آپ halving اور halving مسئلہ کہاں رکھنا،
کیونکہ اگر آپ کے پاس 4 ارب دروازے ہیں، کتنی بار تم نصف میں 4 ارب کاٹ کر سکتا ہوں؟
32 [طالب علم. >> یہ اصل میں 32 ہے. آپ اس کو ایک کاغذ کا ٹکڑا یا تمہارے دماغ میں کام کر سکتے ہیں.
آپ کو 4 ارب 2 ارب 1 ارب نصف بلین 250 ملین، ڈوٹ، ڈوٹ، ڈوٹ، جاؤ.
اور اگر آپ کو ریاضی کرتے ہیں، آپ یقینا 32 حاصل کرنے جا رہے ہیں،
اور یہ کہ اصل میں کمپیوٹر سائنس سے متعلق ہے کیونکہ ہم نے 2 کے اختیارات میں عام طور پر شمار.
32 2 4 ارب ہوتا ہے.
تو 2 کمپیوٹر سائنس میں اختیارات کی اس قسم کی مطابقت کی ایک بہت ہے.
>> لیکن جو 8 ارب؟ کس طرح بہت سے اقدامات ہیں جو آنے والا ہے اگر 8 ارب دروازے ہیں؟
33 [طالب علم. تو 33 >>. اگر ارب 16 دروازے ہے؟ کس طرح بہت سے اقدامات ہیں جو آنے والا ہے؟
34 [طالب علم. 34. >> کی قسم ہم اس اشتھاراتی nauseam جاری کر سکتا ہے. لیکن یہ ایک طاقتور چیز ہے.
آپ کو آپ کا مسئلہ زیادہ آدانوں کی اربوں متعارف کرانے لیکن کوئی بڑی بات نہیں، کر سکتے ہیں،
تم صرف 1 اس کا اضافی کاٹنے باہر لے جاؤ اور اس طرح ہمیں بائنری تلاش کی طرح کچھ دیتا ہے
اور فتح تقسیم، زیادہ عام طور پر ہے.
لیکن میں یہاں دھوکہ دہی کا مہربان ہوں، ہے نا؟
یلیکس الگورتھم کے معاملے میں، وہ شان سے زائد ایک فائدہ تھا.
وہ جانتا تھا کہ یہ اعداد و شمار کے مطابق کیا گیا ہے، لیکن یلیکس انہیں خود سے حل کرنے کی ضرورت نہیں تھی.
پہلے میں بنایا اس بات کا یقین بلیکبورڈ اور قسم آیا
کہ میں ان سب کے مطابق ترتیب میں متوجہ کیا، تو میں نے ان سے کاغذ کے ساتھ احاطہ کرتا ہے.
لیکن کتنا کام ہے کہ مجھے کیا؟
اگر ہم کچھ بظاہر بے ترتیب ترتیب میں ان کی تعداد کے ساتھ شروع کیا تھا -
اس معاملے میں ان آسان تعداد، یہاں 1 کے ذریعے 8 -
ہم نے ان اقدار کو حل کرنے کے بارے میں کیسے جا سکتا ہوں؟
اگر آپ کو اس کام انسان تھے، آپ کا حوالہ کے نقطہ نظر کی کس طرح لیں گے
نمبروں کی ایک مکمل جھوبڈ کو حل کرنے کے لئے ہے؟
یہ چیزیں پہیلی ٹکڑے ٹکڑے کے طور پر رکھی رہے تھے. جی ہاں.
>> [طالب علم] میں ہر ایک نمبر لے لو اور ہر ایک اس کا موازنہ کریں گے
اور بائیں طرف جانے رکھیں. >> ٹھیک ہے، اچھا ہے.
تو ہر نمبر لے، اس کے ساتھ دیئے گئے ایک کرنے کے لئے اس کا موازنہ،
اور پھر صرف چیزوں rejiggering آپ کے طور پر جانا کی فہرست قسم، کے ساتھ ساتھ چلتے رہو.
تو ہم یہاں ملوث حاصل کرنے کے لئے شاید ایک سے زیادہ کچھ لوگوں کے لئے ایک موقع ہے.
کیا ہم 8 مزید رضاکاروں جو آنے سے محبت کریں گے؟
آپ سے ایک چھوٹی سی کم دباؤ صرف ایک نہیں ہو. 1، 2، 3، 4، 5، 6، 7، 8.
ذیل آو. تم لوگوں کو 8 کے ذریعے 1 نمبرز بننے جا رہے ہیں.
چلو دیکھتے ہیں اگر ہم یلیکس کے لئے اسی طرح میں نے اسے پہلے سے کیا میں اس چھنٹائی نہیں بہت کچھ کر سکتے ہیں.
1، 2، 3، 4.
آگے اگر تم ایسا کروگے جاؤ اور سٹیج پر موسیقی کھڑے ہو جاؤ اور مجھے یہاں کے درمیان لائن
سکرین پر سلائیڈ کے طور پر اسی ترتیب میں.
اہ اوہ.
ہم آپ کو اگلے مثال کے طور پر میں کام کریں گے. اوہ، رکو، رکو. یہاں ہم چلے. انتظار کریں.
اگلی مثال کے طور پر اب ہے. تم جاؤ. 8 نمبر. پر چلو.
ٹھیک ہے. ترتیب دیں اس کے مطابق خود.
موسیقی کی طرف سے صرف تھوڑا سا سلائیڈ یہاں کھڑے رہو.
تو ہم نے 4، 2، 6، ہے - وہاں میں یہاں ختم ہو جائے، وہاں - 3.
جی ہاں. ٹھیک ہے. تم یہاں جاتے ہیں. نہیں، تم وہاں رہنا.
جی ہاں، ٹھیک ہے وہاں. نہیں. میں غلط ہوں. وہاں. ٹھیک ہے، بہت اچھا ہے. ٹھیک ہے.
تو اب ہم انہیں ایک بڑھتی ہوئی ترتیب میں الگ الگ ہے.
>> میں ایسا کرنے کے بارے میں کیسے جا سکتے ہیں؟
الگورتھم ہے کہ پہلے ایک لمحے کی تجویز پیش کی گئی تھی کیوں نہ ہم آپس میں موازنہ
لوگ جو اس قسم کی ایک دوسرے کے ساتھ ہیں اور اس کے بعد کوئی غلطی کو درست کریں،
بائیں سے دائیں جانب بڑھ رہا ہے.
تو یہاں ہم نے 4 اور 2 واضح طور پر باہر کے حکم کی ہے. چلو تم تبادلہ. ٹھیک ہے.
تو اب میں نیچے لائن میں منتقل کی جا رہی ہوں. 4 اور 6، نہیں. [ہنسی]
6 اور 8، بہت اچھا ہے. 8 اور 1، مجھے تم لوگوں کو تبادلہ کریں. ٹھیک ہے.
تو 8 اور 3، تم لوگ تبادلہ.
8 اور 7، مجھے تم لوگوں کو تبادلہ کریں. 5 اور 8، بہترین.
میں آپ کو ایک کے مطابق کی فہرست دیتے ہیں.
ٹھیک ہے. تو کافی نہیں.
- 8 پوائنٹ میں کیس - لیکن اس کی وجہ بڑی تعداد بہتر ہے
کی طرح بائیں سے bubbled کو درست کرنے کے.
تو میں نے ان میں سے 1 صحیح ہے، لیکن یہ اس طرح کا خیال ہے کہ کیا مسئلہ کافی حل نہیں ہے.
>> تو کیا تم تجویز ہم اگلے کیا کریں گے؟ >> [طالب علم] یہ کر رکھیں. >> ہم یہ کام کر رہے رہیں.
اور پھر احساس، ہم باتیں صرف تمام انسانوں کی طرف سے مقرر
طرح کی ہوشیاری خود کو اس تصویر پر کی بنیاد پر بندوبست،
لیکن اب ہم زیادہ ودوت ہے.
ہم جیسے ہم کوڈ لکھ رہے ہیں اس کے بارے میں algorithmic رہنا پڑے گا -
زبانی pseudocode اس معاملے میں.
تو مجھے پھر سے کوشش کریں. یہ بہت اچھی طرح کام کیا ہے. یہ حل نہیں تھا.
لیکن جب اس پر شک ہے، اور دوبارہ کوشش کریں کرنے کی کوشش کریں. تو 2 اور 4، اور مدد نہیں تھا.
4 اور 6. آہ! 6 اور 1، اب بہتر تھوڑا.
6 اور 3، اچھا. 6 اور 7، 7 اور 5، 7 اور 8، اچھا ہے.
اور تم جانتے ہو، میں 8 شاید اب نظر انداز کر سکتے ہیں کیونکہ انہوں نے فہرست کے آخر میں ہے.
شاید ہم کسی کو اس کے ماضی میں جا کے بارے میں فکر کرنے کی ضرورت نہیں ہے.
لیکن دیکھتے ہیں اگر وہ ایک محفوظ مفروضہ ہے.
اب فہرست ہے - لات - نہیں کے مطابق. چلو، پھر سے کوشش کریں.
2 تو اور 4، 4، اور 1، 4، اور 3.
4 اور 6، اچھا. 6 اور 5، اچھا ہے.
6، 7، اور 8، اچھا ہے. لیکن نوٹس، صرف میں یہاں اب بند کر سکتے ہیں اور اب یہاں روکنے؟
[طالب علم] جی ہاں. >> جی ہاں؟
اگر تم میں سے کسی ایک کے 9 تعداد وہاں گیا تھا سارا راستہ کیا ہے؟
یہ کیا گیا ہے کے مطابق کریں گے. >> اچھا لگا. یہ کیا گیا ہے پہلی بار کے مطابق کریں گے.
اچھی بات ہے. تو دوبارہ واپس جانے. ہم وہاں تقریبا رہے ہیں.
1 اور 2، 2، اور 3، 3 اور 4، 4 اور 5، 5 اور 6، 6 اور 7، 7 اور 8.
>> اب میں کیا کر رہا ہوں، لیکن پھر میں نے ایک کمپیوٹر ہے جو کہ صرف کر سکتے ہیں جو میں نے کرنے کو کہا ہے ہوں،
اور میرے صرف یاد اب یہ ہے کہ میں نے اصل میں صرف تھوڑا سا کام کیا ہے.
یہاں کچھ تبدیل کر دیا گیا.
تو میں نابینا یا algorithmically ہے کہ اس فہرست میں واقعی کے مطابق ہے تکنیکی طور پر اس بات کی تصدیق نہیں کی ہے.
تو صرف اچھے کی پیمائش کے لئے، صرف اس کے بارے میں مقعد، 1 مزید وقت دینا.
1 تو 2، 2، اور 3، 3 اور 4. اور تم کیا جانتے ہو؟
بس اچھا اقدام کے لئے، میں نے میرے ہاتھ پر ٹریک پر اس وقت رکھنے کے لئے جا رہا ہوں
کتنے سویپ میں صرف اس لئے ہے کہ میں جانتا ہوں کہ کتنا کام میں اصل میں کیا ہے.
3 اور 4، 4 اور 5، 5، اور 6، 6، اور 7، 7 اور 8. کوئی سویپ.
تو اب میں یہ دوبارہ کرنا مورھ قانونی طور پر ہو گی
کیونکہ اگر میں نے انسانوں کے اس پاس کے ذریعے کوئی کام نہیں کیا
تو واضح طور پر کہ پھر کیا ہونے جا رہا ہے اگر ان میں سے کوئی بھی طرح تصادفی ہے
adversarially خود کے ارد گرد منتقل. تو اب مجھے روک نہیں سکتا.
اب سوال پوچھنا کتنا کام یہ اصل میں آپ کے وزٹرز کا ریکارڈ رکھا لے گئے تھے؟
کہ کتنے قدم تھا؟ >> N مربع.
جی ہاں، تو ن مربع. آپ ن کہاں مربع کو حاصل کرنے سے؟
آپ کو ہر NUM چیک کرنے کے لیے ہے -
ن کی تعداد ہے، اور آپ (ن) کی تعداد میں سے ہر ایک تعداد کو چیک کرنے کے لیے ہے.
اچھی بات ہے. تو >> مربع ن ہے. >> اچھا لگا.
>> تو یہ لگتا ہے طرح (ن) بہت اچھی طرح مربع ہو، ٹھیک ہے کر سکتے ہیں؟
ان لڑکوں کو (ن)، 8 خاص طور پر اس صورت میں،
لیکن ہر بار میں نے اس فہرست کے ذریعے چلا گیا، میں دوسرے کے خلاف پہلے شخص کا موازنہ کر رہا تھا،
تیسرے کے خلاف دوبارہ دوسری اور بار بار،
اور جب میں نے آخر تک ہے، میں نے کیا کیا ہے؟ میں نے یہ redid.
لہذا اگر ہم اس وضاحت کو عام کرتے ہیں، ہم لوگوں کو ن ہے
اور میں کر ظاہر کر رہا ہوں، 8 اقدامات، ن اقدامات، ہر وقت میں اس الگورتھم کے ذریعے جاؤ.
لیکن کتنے بدترین صورت میں اوقات میں لوگوں کی اس فہرست کے ذریعے جانے کے لئے کی ضرورت ہے؟
[طالب علم] N اوقات. >> شاید (ن)، ٹھیک ہے، کیونکہ بدترین صورت میں،
شاید جو ان لڑکوں میں سے سب سے زیادہ جانے حاصل سے کیس انتظام ہے؟
اگر وہ مکمل طور پر آرڈر الٹ رہے ہیں
کیونکہ صرف ذہنی طور پر، مان لیں let's - آپ کا نام کیا ہے؟ >> Bowen.
Bowen. ٹھیک ہے. تو Bowen، صرف ایک لمحے کے لئے یہاں آیا ہوں.
>> لگتا ہے کہ Bowen الگورتھم کے آغاز میں یہاں آیا تھا،
ہم جانتے ہیں اور نہیں باقی سب کیا ہے، لیکن Bowen یہاں اس الگورتھم کے مطابق، -
اپ بلبلا جا ہے، کے طور پر انہوں نے پہلی بار کیا - اور اگر تم صرف میرے ساتھ چہلقدمی کرنا چاہتے ہیں،
آخر تک کا راستہ ہے.
لیکن لگتا ہے کہ کہ Bowen اگلے شخص نمبر 7.
میں واپس جانا اور نمبر 7، جس کا مطلب ہے کہ میں تمام طرح یہاں واپس جانا ہوگا حاصل ہے.
اب میں شخص جو نمبر 7 ہے کے ساتھ ہے جو ایک ہی گھومنے ہیں.
لیکن کیا پھر اگر 6 نمبر اس کے ساتھ کے ساتھ ساتھ تھا؟
اس کے بعد میں واپس جانا اور 6 حاصل ہے.
تو پھر، میں ن لوگوں میں سے ہر ایک کو اس لوپ کے ہر iteration پر بات کر رہا ہوں،
اور میں ان strolls ن کرنے کا یقین ہے کہ میں ھیںچ رہا ہوں ہو سکتا ہے
سب سے بڑا اور پیچھے کی اور واپس فہرست کے آخر عناصر کے سب.
تو ن چیزیں (ن) اوقات ن کے اوقات ن یا ن مربع ہے.
>> تو یہاں پہلے ہی ہم ایک الگورتھم ہے جو اب نہیں ہے (ن)، جو اب نہیں لاگ ان ن ہے،
یہ اصل میں کچھ ہم پہلے کیا ہے سے بھی بدتر ہے.
تو یلیکس کی طرح خوش قسمت ہے کہ میں بظاہر اس کے لیے سامنے کا کام تمام کیا،
مہنگی کام کے تمام، تا کہ وہ اس بائنری تلاش الگورتھم میں لطف اندوز سکتا ہے
جو کہ (ن) کے لاگ ان ہے.
لیکن یہ پیر مرکزی خیال، موضوع کے مطابق ہے.
ہم نے تھوڑا سا زیادہ جگہ دی، ہم نے زیادہ بٹس کا استعمال کیا، ہماری رننگ ٹائم کی رفتار تیز کرنے کے لئے.
اتنا وقت اور جگہ کے درمیان اس کاروبار بند ہے،
وہاں بھی تجارتی آف کے درمیان وقت چیزوں کو جانے کے لئے تیار ہو رہی ہے کے سامنے طرح خرچ ہو سکتا ہے
اور اصل میں تلاش کی طرح ایک الگورتھم قتل. کی ایک اور کرنے کی کوشش کریں.
اگر تم لوگ صرف تیزی سے rearranging میں کوئی اعتراض نہیں کریں گے اپنے آپ کو ہے کہ پھر سے ملنے کے لئے،
تھوڑا سا مختلف ہے جہاں یہ ہے بہت آسان نہیں کچھ کرنے کی کوشش کریں تو
کے طور پر صرف تمام pairwise غلطیوں، جو سپر بدیہی ہے طے کر لو.
کی بجائے تھوڑا اور جان بوجھ کر اور ایسا کرنے دو.
شاید اس میں بھی تجویز ہے بہت بدیہی ہے.
>> کی فہرست میں سے سب سے چھوٹی شخص بار بار منتخب کرتے ہیں. تو ہم یہاں جانا.
4، آپ کو سب سے چھوٹے شخص میں اس طرح اب تک دیکھا ہے،
تو میں ذہنی طور پر صرف اب کے لئے آپ کی طرف اشارہ کرتے ہوئے کی طرف سے کہ یاد کرنے جا رہا ہوں.
2. ؤہ! 4 تعداد کے بارے میں بھول جاؤ. میں نے صرف اس فہرست میں نیا سب سے چھوٹی عنصر مل گیا.
میں قسم کی ہے کہ یاد کرنے جا رہا ہوں. 6، 8.
ؤہ! 1. الوداع. تو اب میں 1 نمبر یاد کرنے جا رہا ہوں.
ہم جانتے ہیں کہ 1 سب سے چھوٹی ہے، لیکن میں کمپیوٹر ہوں. کیا ہوگا اگر کوئی 0 ہے؟
کیا اگر وہاں ایک -1 ہے؟ میں جا رہا ہوں رکھنے کے لئے ہے.
تو 3، 7، 5، نہیں. ٹھیک ہے. تو نمبر 1 سب سے چھوٹی تھی.
مجھے آپ کی فہرست سے منتخب کریں - we'll اس طرح -
اور آپ کی فہرست کے شروع میں منمانے ڈالو.
اب، ایک منٹ رکو. دھوکہ دیا میں ہے.
اگر یہ لوگ 8 لوگوں کی فہرست نہیں بلکہ ایک صف کی نمائندگی کرتے ہیں،
ملحق میموری 8 حصوں - آپ کو صرف ایک لمحے کے لیے واپس نکلنے میں کوئی اعتراض ہے؟
اصل میں یہیں پر آپ کے لئے کوئی جگہ نہیں ہے.
تو ہم کس طرح کی جگہ کرتے - تمہارا نام کیا ہے؟ >> سیمی. >> سیمی.
ہم نے سیمی کے لئے کس طرح کی جگہ ہے؟
>> ہم N جو مجھ سے پہلے ہیں منتقل. ٹھیک ہے. >>
تو ہم ن لوگ ہیں جو اس سے پہلے ہیں میں منتقل کر سکتا ہے،
اگر ایسا ہے تو آپ لوگ 1 جان بوجھ کر، ڈرامائی بائیں طرف قدم اٹھانے کے لئے چاہتے ہیں.
وہ سب مل کر کیا، لیکن آخری وقت میں کچھ کوڈ لکھا،
آپ کو ترتیب نہیں کی بہت سی چیزیں ایک بار میں منتقل کر سکتے ہیں.
ہم نے اسے ایک لوپ میں کیا، ہر کسی کو ایک وقت میں منتقل ایک بار کر سکتے ہیں.
تو اگر تم لوگ حق واپس نکلنے میں کوئی اعتراض نہیں ہوگا،
اور سیمی، اگر تم واپس قدم ہے کیونکہ وہاں اب بھی آپ کے لئے کوئی گنجائش نہیں ہے کر سکتے ہیں،
اب ایسا دو. سیمی ایک لمحے پہلے کہاں تھا؟ وہاں.
تو وہاں ایک فرق ہے. تو آپ کو سیمی جگہ میں منتقل کر سکتے ہیں.
اب اگلے اب انسان اور اگلے شخص، اب اگلے شخص ہے. اب ہم سیمی کے لئے کمرہ ہے.
سامعین سے اب کوئی - وہ اچھا تھا وہ درست تھا،
یہ محسوس کیا تھوڑا وقت لگتا - کیا تیز ہے؟ جی ہاں.
[طالب علم کو] ایک نئی صف؟ >> وہ کیا ہے؟ >> [طالب علم کو] ایک نئی صف؟ >> ٹھیک ہے، اچھا ہے.
>> صرف تجارت آف کے اس مرکزی خیال، موضوع کے ساتھ تو مسلسل، کیوں بس میں نہیں ہے ایک نئی صف
اور اس کے بعد سیمی ان لوگوں کے سامنے میں خلا میں مثال کے طور پر، تیرنا،
اور ہم ایک نئی صف کو مکمل طور پر بھرنے شروع کر سکتے ہیں. یہ بھی کام کریں گے.
لیکن میں آج زیادہ جگہ خرچ کرنے میں کوئی دلچسپی نہیں ہے. کیا ایک اور نقطہ نظر ہے؟
[طالب علم] سویپ. ٹھیک ہے. >> ہم ان 2 لوگ صرف تبادلہ کر سکتے ہیں. آپ کا نام کیا ہے؟
ماریو. >> ماریو. ماریو تو، آپ اس وقت یہاں تھے.
سیمی، آپ کو صرف ایک لمحے کے لئے واپس کر سکتے ہیں؟ ماریو یہاں تھا.
ہم آپ کے لئے کمرے نہیں ہے اب، اگر ایسا ہے تو آپ جہاں سیمی ہے جانے میں کوئی اعتراض نہیں ہوگا،
ہم سیمی یہاں ڈال، اور اب میں کا کہنا ہے کہ سیمی گماگمن آپریشن بہت تیز تھی گے.
ہم 1 آپریشن کیا ان لوگوں کے تبادلہ، 2 ہو سکتا ہے یا ان لوگوں کو تبادلہ،
لیکن ہم 1، 2، 3، 4 نہیں کیا، تو یہ بہتر محسوس ہوتا ہے. اب، ایک منٹ رکو.
میں قسم کا مسئلہ بھی بدتر بنا دیا ہے کیونکہ 4 نمبر طرح کے آغاز کے قریب تھی.
اب 4 نمبر تھوڑا اس مقصد کے قریب ہے، لیکن میں واقعی نہیں تھا اس کے بارے میں خیال معلوم.
تو یہ صرف بدقسمتی یہ ہے کہ 4 نمبر تھوڑی دور اس کی قسمت جگہ سے دور ہے.
تو اب ہم اس الگورتھم دوبارہ.
>> ، جب تک اس کہانی تھی recap، ہم سب کی فہرست کے ذریعے کیا گیا تھا چل
سب سے چھوٹا نمبر شخص کی تلاش میں ہے.
تو اب اسے دوبارہ نہ ہونے دو. ہم سیمی کے بارے میں اور زیادہ فکر کرنے کی ضرورت نہیں ہے.
ہم صرف یہاں سے جا سکتے ہیں. ؤہ! 2 نمبر. یہ ایک بہت چھوٹی سی تعداد ہے.
6، 8، 4، 3، 7، 5. ٹھیک ہے، اچھا ہے.
اور اتفاق کے ذریعے شکر، میں منتقل کرنے کی ضرورت نہیں ہے - >> ولی.
ولی کیونکہ اب وہ اس کی صحیح جگہ میں ہے.
چلو، یہ پھر سے کرتے ہیں اور ان 2 لوگ نظر انداز کریں.
6. یہ ایک بہت چھوٹی سی تعداد ہے. ؤہ! 8 ضرور ہے بڑی ہے.
4. 4 توجہ مرکوز ہے. ؤہ! 3 بھی بہتر ہے.
7 اور 5. لہذا جو ہم سے اب کرتے - >> راجر. >> راجر؟
چلو اسے 6 نمبر کے ساتھ تبادلہ کریں.
لہذا اگر 6 اور 3 تبادلہ کرنا چاہتے ہیں،
اب ہم 6 کہ میں اس قسم کی ہے خوش ہو گیا وہ کہاں ہونا چاہئے کے قریب ہے،
لیکن یہ صرف ایک اتفاق ہے یہاں. تو اب یہاں سے جانا ہے.
8 ایک بہت چھوٹی سی تعداد ہے. ؤہ! 4 چھوٹا ہے.
6، 7، 5. اب ہمیں کیا کرنا ہے؟ >> سویپ. بالکل ٹھیک ہے. >>
تو اب تیزی سے اس طرح کرتے ہیں ہم.
8، 6، 7، 5. 5 کہاں جاتا ہے؟ اچھی بات ہے. ٹھیک ہے.
6، 7، 8. 6 وہ کہاں ہے رہنے کے لئے ہو جاتا ہے. آپ کا نام کیا ہے؟ >> Rosalie.
Rosalie وہ کہاں ہے رہنے کے لئے ہو جاتا ہے. 7 ہو جاتا ہے - چلو دیکھتے ہیں. 7، 8. ٹھیک ہے.
تو 7 وہ کہاں ہے رہنے کے لئے ہو جاتا ہے. آپ کا نام کیا ہے؟ >> آمنہ ہے. >> آمنہ ہے.
>> تو آمنہ وہ کہاں ہے رہنے کے لئے ہو جاتا ہے، اور 8 تعداد پہلے ہی ہے اب وہ کہاں ہونا چاہئے.
ٹھیک ہے، اچھا ہے. جیسا کہ ہم صرف خود کے لئے کام کی تشکیل کر رہے ہیں یہاں، اگرچہ لگتا ہے.
بالآخر اس الگورتھم کی رننگ ٹائم کیا ہے؟
اگر ہم نہیں 8 لیکن (ن) کے طور پر ان لوگوں کے بارے میں میں کیا سوچتے ہیں؟ >> یہ ن ہے.
یہ اقدامات کو ن ہے، لیکن ہم نے ہر ایک وقت کی جانچ پڑتال کر رہے ہیں.
ٹھیک ہے. N لیکن آپ کو ہر ایک وقت کی جانچ پڑتال کر رہے ہیں؟
ٹھیک ہے، لیکن اگر یہ اقدامات کو ن ہے، میں نے نہ آپ کو صرف 1، 2، 3، 4 جا کر کو حل کرنے کے قابل ہو گیا ہے؟
اوہ! ٹھیک ہے، یہ ایک بڑا فرق ہے.
تو (ن) کیوں مربع؟ کہ اصل میں کیا ہو رہا ہے؟
اس فہرست میں (ن) کے لوگوں کی ہے، لیکن فہرست میں سب سے چھوٹی شخص کو تلاش کرنے کے لئے
بدترین صورت میں، میں نے کتنے قدم لینے کی کیا ضرورت ہے؟ >> N.
>> (ن)، ٹھیک ہے، کیونکہ بدترین صورت میں، نمبر 1 وہاں راہ ہے،
تو میں اسے ملے گا یا اس سے ہے.
اور پھر جب میں نے کا احساس 1 سب سے چھوٹا تھا، تو یہ بہت جلد ان کے تبادلہ پر ہے.
لیکن اب مجھے شروع سے شروع کرنے کے لئے اور جو دیکھو ہے؟
اگلے سب سے چھوٹا شخص، جو 2 ہے. بدترین صورت میں 2 کہاں ہے؟
اوہ، میرے خدا. یہ یہاں آخر میں تمام طریقہ ہے.
تو اب میں صرف ایک ن اقدامات، ایک دوسرے ن اقدامات کیا ہے.
اور اگر ہم (ن) کے لوگوں کی ہے اور بدترین صورت میں سب سے چھوٹی شخص ن دور اقدامات،
پھر (ن) اوقات (ن) ہے، اور ہم ایک بار پھر مربع ن ہے.
یہ اتنا اچھا محسوس نہیں ہے.
اور سب سے بہتر صورت میں بھی - اور اصل میں، لگتا ہے کہ وہ شروع سے دور کے مطابق -
کتنے قدم کے لئے اسے لے لو آپ کے وزٹرز کا ریکارڈ رکھا اس الگورتھم کو استعمال کرتے ہوئے ان ن لوگوں کو سلجھا ہے؟
N مربع. >> میں نے سنا ن مربع. ن مربع کیوں؟
کیونکہ آپ کو اب بھی ہر ایک وقت چیک کرنے کے لیے ہے. >> جی ہاں.
اور تم ان کا تبادلہ ہے. >> اگرچہ ہم انسان سروشتھ کی طرح ہیں
احساس میں ضعف ہے کہ ہم دیکھتے ہیں کہ اس کے مطابق ہے قسم کر سکتے ہیں
کمپیوٹر ہوشیار نہیں ہے.
یہ یہاں اور یہاں اور یہاں تلاش کرنے جا رہا ہے،
لیکن، جو اس کے لئے لگ رہا ہے سب سے چھوٹا عنصر ہے اگر
آپ کو صرف اتنا معلوم ہے کہ آپ کس نقطہ کی طرف سے سب سے چھوٹی عنصر مل گیا؟ ایک بار جب آپ نے آخر میں ہیں.
لیکن آپ صرف اس وقت اس وقت سب سے چھوٹی عنصر تلاش کر لیا ہے.
آپ کو دنیا کی حالت کے بارے میں کچھ اور ضروری نہیں جانتا.
تو آپ بار بار بار جانے کے لئے ہے.
>> تو اس وقت مجھے سچ میں پتہ گونگا نظر آتے ہیں کیونکہ میں جانچ پڑتال، ٹھیک ہے، 2 رہا ہوں، آپ سب سے چھوٹی ہیں،
لیکن میں ہے کہ میں کل معلوم نہیں ابھی تک.
3، 4، 5، 6، 7، 8. ٹھیک ہے، اچھا ہے. 2 بلاشبہ سب سے چھوٹی تھی.
اب ہم اگلے سب سے چھوٹی تلاش. ٹھیک ہے.
3، آپ فی الحال سب سے چھوٹی ہیں. چلو دیکھتے ہیں. 4، 5، 6، 7، 8. ٹھیک ہے، ایک بار پھر خوش ہے.
3 صحیح جگہ واقعی میں تھا. لیکن میں یہ کر بار بار بار رکھنے کے لئے جا رہا ہوں.
ہم نے کبھی ایسا تھوڑا بہتر کس طرح کر سکتا ہوں؟
لوگوں کو بلبلا ہونے تک pairwise سے سب سے چھوٹی سب سے بڑا کرنے کے بجائے
اور تو سب سے چھوٹا شخص کو منتخب کرنے کی فہرست کے ذریعے آگے اور پیچھے جانے کی بجائے،
اس کے بجائے ہم کیوں ایک نئی فہرست قدم میں نہیں ان لوگوں قدم کی طرف سے داخل ہے؟
چلو، اس کی کوشش ہے. اب مجھے اس بات اندراج کی طرح فون.
تو یہاں ہم یہاں ہیں. نمبر 1. میں نے اس فہرست میں کسی اور کے بارے میں پرواہ نہیں کرتے.
میرا مقصد ابھی ایک کے مطابق کی فہرست کے شروع میں نمبر 1 کے لئے ہے.
اور میں تجویز کی جا میں صرف میموری کے 8 حصوں ہیں تو رہا ہوں،
منمانے اب میں میرے قیاس ناچھانٹا ہوا کی فہرست کے درمیان دیوار ہوں،
اور جو کوئی بھی میرے پیچھے ہے میں دعوی کرنے جا رہا ہوں کے مطابق ہے.
تو اب ہم نمبر 1 ہے.
تو میں اسے میرے مطابق کی فہرست میں داخل کرنا چاہتے ہیں، میں صرف یہاں دیوار میں منتقل کی جا رہی ہوں،
اور اب میں یہ دعوی کرتے ہیں اس فہرست کے مطابق ہے، اس فہرست ناچھانٹا ہوا ہے - کم از کم اتنا جہاں تک میں جانتا ہوں.
میں نے ایک بار میں تمام نمبر نہیں دیکھ سکتے ہیں.
>> اب میں نمبر 2 کا سامنا ہو. میں نے اس کے ساتھ کیا کروں؟
میں اب آپ کے مطابق فہرست میں ڈالیں. نوٹس لیکن کتنا آسان تھا.
مجھے صرف دیکھنا ہے. نمبر 1 ہے. اوہ، ظاہر 2 نمبر 1 کی طرف جاتا ہے ہے.
اب کیا میں 3 کے ساتھ کیا کرتے ہیں؟ میں آپ کے مطابق فہرست میں داخل ہیں. لیکن وہ سپر آسان تھا.
یہ سپر آسان ہے، سپر آسان ہے، سپر آسان، سپر آسان، سپر آسان ہے.
اور اب سب کچھ میرے پیچھے کے مطابق ہے، اور یہ کہ کتنے قدم لے گئے؟
[طالب علموں] N. >> تو یہ صرف ن ہے. ہم خوش قسمت ہے.
یہ صرف (ن) کیوں تھا؟ >> [طالب علم] کیونکہ فہرست کے مطابق کیا گیا تھا.
فہرست میں پہلے ہی کے مطابق ہے. تو ہم خوش قسمت ہے.
لیکن ہم ایک الگورتھم اس وقت ہے کہ اس طرح کی قسمت harnesses ڈیزائن
کہ غیر ضروری وقت نہیں ضائع کر بہترین حالات ہیں.
تو اب ہم کیا ہم بلبلا قسم کو فون کرتا ہوں
جہاں pairwise اپ بلبلا کے لوگوں قسم.
اب ہم انتخاب طرح ہے جہاں ہم سب سے چھوٹے شخص توڑو بار بار.
اور اب ہم اندراج کی طرح ہے جہاں ہم طرح کی مسلسل لوگ ہیں جہاں وہ تعلق رکھتے ڈال
ایک تیزی کے مطابق فہرست میں.
اگر ہم کر سکتے، ان لوگوں کے لئے یہاں تعریف کی ایک گول. [تعریف]
چلو ہماری یہاں 5 منٹ کے وقفے لے.
اور جب ہم واپس آئے، ہم نے پانی سے باہر ان یلگوردمز کی سب اڑا گا
بہتر چيز کے ساتھ. ٹھیک ہے. کا بہت بہت شکریہ. آپ souvenirs کے طور پر لوگوں پر رکھ سکتے ہیں.
ٹھیک ہے. ہم واپس آ گئے ہیں.
>> اور حقیقی روزہ recap، ہم چھنٹائی ان مختلف 3 نقطہ نظر تھا،
پوائنٹ حاصل کرنے کے لئے جس کے پورے نقطہ تھا جہاں یلیکس طرح کسی
شان کر سکتا ہے کسی سے تیز کی تعداد کی ایک فہرست کو تلاش کر سکتے ہیں.
اور اگرچہ ہم 8 تعداد کے ساتھ اس طرح سادہ مثالیں ہیں،
آپ آسانی سے 8 ویب صفحات، 8 ارب ویب صفحات extrapolate سکتا ہے،
یا فیس بک پر 800 ملین.
تو یہ الگورتھم اس طرح کی اقدار کی ان ضرور کرنا کر سکتے ہیں،
اور خیالات بالآخر ایک جیسے ہیں.
تو بلبلا طرح کا سب سے پہلا ہے جہاں ہم نے اس قسم کی سب سے بڑی شخص bubbled تھا
لوگوں کو pairwise گماگمن کی طرف سے ٹھیک طریقہ ہے.
پھر ہم نے وہی کیا جو ہم نے انتخاب طرح فون جہاں میں تھوڑا اور جان بوجھ کر کریں گے
رکھا فہرست کے ذریعے تلاش، بار بار سب سے چھوٹی تعداد کو منتخب کریں اور دوبارہ
جس کا منطقی نتیجہ یہ ہے کہ فہرست بالآخر کے مطابق ہے.
پھر تیسرے میں سے ایک میں، میں لوگوں کو ان کی مناسب جگہ میں ڈالا،
اور ہم نے اس فہرست میں پہلے ہی کے مطابق کیا گیا تھا میں ایک بہت contrived مثال کے طور پر کیا،
لیکن اس پیغام کو بھیجنے کے لئے یہ تھا کہ اندراج کی طرح کے کیس میں،
تم خوش قسمت حاصل کر سکتے ہیں.
اگر اعداد و شمار کے مطابق پہلے ہی کر رہے ہیں، یہ صرف آپ (ن) کے اقدامات پر زیادہ کے طور پر کی تصدیق ہو رہا ہے،
جبکہ انتخاب طرح آپ کو تھوڑا اور سرنگ وژن ہو
اور تم نے کبھی یہ نہیں ہے کہ فہرست پہلے ہی کے مطابق ہے احساس ہے.
تو کارروائی میں بلبلا طرح یہاں دیکھ.
مندرجہ ذیل مثال میں، ہم عمودی سلاخوں کو دیکھنے کے لئے کے بارے میں
جن بلندیوں کی تعداد کی نمائندگی کرتے ہیں تاکہ ہم مرئی ہو چھںٹائی کی ترتیب کر سکتے ہیں.
چھوٹے بار، چھوٹے تعداد، بڑی بار، بڑی تعداد ہے.
>> اور ہم نے اسے اس ڈیفالٹ کی رفتار میں ادا کریں گے.
یہ اب کے لئے ایک چھوٹا سا اور روزہ بھی منتقل کی جا رہی ہے، لیکن لال ہے جو 2 سلاخوں کے دکھا رہا ہے
کیا جا رہا ہے کی طرف سے کی طرف سے کے مقابلے میں.
اور اگر آپ ان کے ساتھ مل کر دیکھتے ہیں، کیا ہوتا ہے یہ ہے کہ اگر سلاخوں کے حکم سے باہر ہیں،
ایک چھوٹی بائیں میں منتقل کردیا گیا ہے، بڑا حق پر ہو جاتا ہے،
اور پھر آپ کو آگے بڑھانے رکھیں.
تو اگر ہم ایسا بار بار محسوس ہے کہ سب سے چھوٹی سلاخوں
رہے ہیں اور بائیں جانب اپنے راستے inching رکھنے کے لئے جا
اور سب سے بڑا سلاخوں کے حق پر اپنے راستے inching رکھنے کے لئے جا رہے ہیں.
اور یقینا ہم ایک طرز دائیں ہاتھ پر دیکھنا شروع کر رہے ہیں
جیسا کہ ہم نے 8 تو نے دیکھا اور 7 آخر میں ہمارے انسانی فہرست کے دور آخر تک bubbling.
تو یہ بہت جلد تھوڑی تکاؤ حاصل کرنے کے لئے کی جا رہی ہے، تو کے وزٹرز کا ریکارڈ رکھا جائے گا. میرے ایک لمحے کے لئے اس کو روک دے.
مجھے رفتار بہت تیز ہو تبدیل.
میں الگورتھم کو تبدیل نہیں کر رہا ہوں، میں تو بس بنانے حرکت پذیری تیزی سے ہو رہا ہے.
پھر بھی بلبلا طرح، اسی الگورتھم
لیکن اب تم ہماری زبانی مظاہرے سے زیادہ تیزی سے دیکھ سکتے ہیں
ہے کہ سب سے بڑا عناصر یقینا سب سے اوپر تک bubbling ہیں.
>> ایک طرف ایک کے طور پر، نیچے بائیں میں ان چھوٹی چوکوں اور نیچے دائیں
آپ کتنے موازنہ کر رہے ہیں کے طور پر بہت کم یاددہانی ہیں.
لیکن پرامڈ کہ شکل لے رہا ہے اب ہم اپنی توجہ مرکوز، اور اس جا رہا ہے کر سکتے ہیں.
سب سے چھوٹی عنصر بائیں، دائیں طرف سب سے بڑا، اور کسی کے درمیان میں سب کچھ ہے.
اب بجائے انتخاب کی طرح پر ایک نظر لے.
مجھے آگے جانا ہے اور سٹاپ مارا جا رہا ہوں. ہم سلاخوں کے کی ایک نئی بے ترتیب سیٹ حاصل کرنے کے لئے جا رہے ہیں.
سلیکشن طرح، یاد، کی فہرست کے ذریعے بار بار بار جاتا ہے،
سب سے چھوٹی عنصر plucking. تو یہاں انتخاب طرح ہے.
یہ وہاں کم ہو رہا کام کی طرح لگتا ہے کیونکہ ہم pairwise موازنہ نہیں کر رہے ہیں
لیکن ہم چیری بائیں سے دائیں سے سب سے چھوٹی عناصر کو اٹھا کے الگ الگ رہے ہیں.
یہ بہت کم وقت لگا، وہاں پہلے سے ہی وجود میں ائی ہے.
صرف اس لئے کہ ایک الگورتھم ن مربع بلبلا طرح کی طرح وقت لینے کے لئے کہا جاتا ہے
اور انتخاب طرح کی طرح، ان لوگوں کو واقعی بدترین چل رہا اوقات.
مثال کے طور پر، کی صورت میں دو، کا کہنا ہے کہ، انتخاب کی طرح،
دراصل میں سب سے چھوٹے شخص کا انتخاب اور اس کے یا اس کے یہاں ڈال رہا ہوں،
تو میں نے اسے پھر کر رہا ہوں، تو میں اسے دوبارہ کر رہا ہوں،
لیکن تھوڑا سا اصلاحی میں بنا سکتے ہیں.
>> اس صورت میں سیمی - جیسے ہی میں یہاں نمبر 1 میں منتقل کردیا گیا -
کیا میں اس کے ساتھ اس کے بعد کرنے کی ضرورت ہے کیا؟ >> [طالب علم] اسے چھوڑ دو.
اسے چھوڑ دو، ٹھیک ہے؟ کچھ بھی نہیں.
میں نے کبھی سیمی پر سے بات کرنے کی ضرورت نہیں تھی پھر کیونکہ اگر میں سب سے چھوٹی عنصر منتخب کیا تھا
اور اسے یہاں رکھ، وقت برباد کیوں میرا مکمل فہرست کے آخر میں جا رہے ہیں؟
اگلے iteration پر مجھے اصل میں نمبر 2 صرف نمبر 3 پر منتقل کرنے کے لئے،.
تو حقیقت میں، میں ن چیزوں ن اوقات نہیں کر کیا گیا تھا.
1 چیزوں، تو N - 2 - چیزیں، تو N - 3 چیزیں، میں ن چیزیں، تو ن کر رہے تھے
تو N - 4، ڈاٹ، ڈوٹ، ڈوٹ.
ہم ایک ستادوستیی سیریز کا تھوڑا سا ہے، جس کا مطلب صرف اتنا ہے
آپ کو شامل کر کے آہستہ آہستہ چھوٹی تعداد رہے ہیں.
+ ن + ن ن نہیں + ن لیکن ن 7 + 6 + 5 + 4 + 3 + 2 + 1 +.
اور کیا ہے جو عام طور پر کام کرتا ہے -
میں اپنے بورڈ گندگی جا رہا ہوں، صرف ایک لمحے کے لئے یہاں -
/ 2 - جو ن (1 ن) کی طرح کچھ کام کرنے جا رہا ہے
اگر ہم ایک ریاضی کی کتاب ہے جہاں آپ سب دھوکے باز شیٹ ہے کے پیچھے نظر آتے ہیں صرف قسم
فارمولوں کے لئے.
اگر آپ نے ابھی کچھ انہوں نے مزید کہا رہے ہیں ن + N - 1 + N - 2، اسے باہر کام کرتا ہے کچھ اس طرح ہے.
اور اگر ہم صرف کی قسم یہ ضرب، جو مربع مائنس ن / 2 ن ہے.
میں نے یہ کہہ (ن) مربع، اگرچہ، اور یہ کہ کیونکہ میں ایک ذہنی شارٹ کٹ کو لینے کے طرح تھا
کیونکہ حقیقت میں (ن) واقعی مربع مائنس ن 2 سے تقسیم اقدامات کی حقیقی تعداد ہے
کہ انتخاب کی طرح کی طرح ایک الگورتھم لے اگر ہم سچ میں شمار ہوتا
ان موازنہ کے تمام اور تھوڑا مصروف کام ہم کر رہے تھے سب.
لیکن سچ کہوں تو، ایک بار N دس لاکھ یا ایک ارب، جو heck پرواہ ہے ہو جاتا ہے
اگر آپ کو ایک ارب مربع مائنس ارب 2 سے تقسیم کر رہے ہیں؟
بلین مربع ایک بڑی تعداد ہے.
آپ کے ساتھ اس کا ارب ایک دوسرے سے دور لے جا سکتے ہیں - ن. یہ اتنا بڑا سودا نہیں ہے.
بڑی تعداد میں تو ملے، کم اہم یہ کم منظم کی شرائط ہیں.
اگر آپ کو 2 کی طرف سے تقسیم اگر آپ اقدامات کی تعداد کے quadrillions کے بارے میں میں بات کر رہے ہیں کون پرواہ کرتا ہے؟
>> تو عام طور پر، کمپیوٹر کے سائنسدانوں سب کچھ لیکن سب سے بڑا اصطلاح پر پھینک دیتے ہیں،
اور ہم صرف کی قسم دنیا کو آسان بنانے اور کہتے ہیں کہ اس کے الگورتھم
تقریبا ن مربع اقدامات لیا. یہ ایک الگورتھم چلانے کا وقت ہو گیا ہے.
تو ہم صرف ایک لمحے میں اس میں کچھ ٹھوس مثالوں کے ساتھ واپس آ جائیں گے،
لیکن اب کے لئے، جو صرف ہماری دنیا کو آسان بنانے کے پیچھے بدیہی حوصلہ افزائی کی طرح ہے
اور ان تمام پسند ہیں فارمولوں میں ہو رہی کی بجائے سب سے زیادہ اہم شرائط کے بارے میں بات کر رہی ہے.
تو اس انتخاب طرح تھا، اور ہم وہاں تھوڑا خوش ہے.
چلو اندراج طرح نظر. آپ کے وزٹرز کا ریکارڈ رکھا آگے بڑھیں اور یہ ایک اچھی طرح سے شروع کریں.
اب پیٹرن ہو رہا ہے محسوس تھوڑا مختلف ہے،
اور ہم بے ترتیب تعداد کے ساتھ شروع کر دیا،
لیکن اگر ہم بدترین صورت میں اصل میں اقدامات کی تعداد شمار،
اگر فہرست صحیح ترتیب میں مکمل طور پر شروع کر دیا،
ہم ن اقدامات صرف زیادہ سے زیادہ احساس کرے گی.
>> لیکن اگر فہرست اصل میں پیچھے تھے - مثال کے طور پر، اس صورت میں یہاں -
تو محسوس ہم اصل میں اس معاملے میں بہت زیادہ کام کرنا ہے.
اور اس قسم کی آپ کو ایسا لگتا ہے کہ یہ ایک مشکل کام کرنے کا قسم ہے
بائیں ان چھوٹے عناصر کو حاصل ہے، اور وہ اس لئے ہے کیونکہ ہم اباگی ہے.
فہرست ریورس میں اتفاقی طور پر حل کیا گیا تھا.
کے برعکس، اندراج طرح سے اگر ہم یہاں نقل کرنا کیا ہم اپنے انسانوں کے ساتھ کیا کیا
کے مطابق سب کے ساتھ شروع ہونے والی اور اس کے بعد شروع کرنے کے کی طرف سے، یہ ایک بہت اچھا طریقہ ہے، ہے نا؟
یہ پہلے ہی، حقیقت میں ہے کے مطابق،.
تو مختصر بالکل کتنا وقت ان چیزوں ہمیں لے رہے ہیں کرنے کی کوشش کریں
شبدجال کی تھوڑا سا یا سنکیتن ہے کہ اصل میں ہے بہت آسان شروع کی طرف سے
سے fanciness طرح کی تجویز.
یہ بات، یہ بڑا اے کی سکرین پر ہے، جو عام طور پر ایک کمپیوٹر سائنسدان استعمال کریں گے
ایک الگورتھم کے بدترین رننگ ٹائم کی وضاحت.
>> ایک بار پھر بدترین کی طرف سے، یہ مکمل طور پر سیاق و سباق پر منحصر ہے.
ہم بدترین کی طرف سے کیا مطلب مکمل طور پر مسئلہ کے بارے میں ہم بات کر رہے ہیں کی بنیاد پر مختلف ہوتی ہے.
لیکن چھنٹائی کی صورت میں، ممکن بدترین منظر نامے کیا ہے؟
سب کچھ پیچھے ہے کیونکہ یہ صرف محسوس ہوتا ہے کہ جیسے ہمارے لئے بہت کام کا مطلب ہے کہ.
میں نیچے jotted الگورتھم ہے کہ ہم ابھی تک دیکھا ہے میں سے چند ایک ہے:
لکیری، تلاش کریں، فون بک یا کاغذ کے ٹکڑے کے ساتھ جیسے بائنری تلاش
جیسے تو بلبلا طرح، انتخاب کی طرح، اور اندراج کی طرح ہم اپنے انسانوں کے ساتھ دیکھا،
اور اس کے بعد 1 دوسرے کہ آخر طرح ضم بلایا جا رہا ہے.
تو بدترین صورت میں لکیری تلاش میں، کتنے قدم یہ نمبر 7 کو تلاش کرنے کے لئے لگتا ہے
اگر شان چہرے کی طرح ن دروازے ہیں؟ >> [طالب علم] N.
N. تو ہم بڑا این اے کو لکھنے کے لئے جا رہے ہیں.
میں صرف کچھ خالی میں بھرنے کے لئے جا رہا ہوں. یہ صرف خالی کا ایک گرڈ ہے.
لیکن لکیری تلاش کے ساتھ سب سے بہترین صورت میں، 7 کی فہرست کے آغاز میں ہو سکتا ہے،
اور شان فہرست کے آغاز کو دیکھ شروع ہو سکتا ہے.
تو اگر آپ لکیری تلاش کا استعمال کرتے ہوئے کر رہے ہیں اور صرف چیک کر بائیں سے دائیں یا شاید دائیں سے بائیں -
وہ برابر ہو - بہترین صورت میں، کتنے قدم لکیری تلاش کر سکتے ہیں
شان الگورتھم کی طرح لے؟ بس مرحلہ نمبر 1.
>> لہذا میں نے کا کہنا ہے کہ ومیگا سنکیتن کے لئے جا رہا ہوں.
یہ صرف سرمایہ ومیگا ہے.
ومیگا کہ بہترین وقت چل رہا کرنے کے کی تلاش میں راستہ ہے.
تو بہترین صورت میں چل رہا وقت ایک قدم یا مسلسل کی تعداد میں قدم ہے -
اس صورت میں 1 - لیکن بدترین صورت میں، بگ O، یہ اصل میں ن اقدامات ہے.
اور یہ یہاں ایک، تھیٹا، ہم اصل میں ابھی نظر نہیں ہو.
یہ اس خاص مثال سے متعلق نہیں ہے.
لیکن اب بائنری تلاش کرنے کی کوشش کریں.
بائنری تلاش کے ساتھ بدترین صورت میں، کتنے قدم یہ نمبر 7 تلاش کرنے کے لئے لے جا رہا ہے
یا جو کچھ بھی ہم کے لئے تلاش کر رہے ہیں؟ >> [طالب علم] لاگ ان ن.
اب بھی لاگ ان N کیونکہ جیسا کہ یلیکس اشوب ہے لے جا
ہم واقعی جب مسئلہ کے ذریعے طریقے پر کام کیا
اور وہ آخری دروازہ وہ کو دیکھا تک 7 نمبر نہیں ملا،
اگرچہ، جانبداری میں، وہ راستے میں کچھ دروازے پر پھینک ہے،
بدترین صورت میں بائنری تلاش لاگ ان کریں (ن) کے ایک وقت چل رہا ہے.
اور پھر یہ تقسیم اور اس فتح کے لئے بات کرتا ہے.
لیکن کے بارے میں بہترین صورت میں کیا ہوگا؟
اور یلیکس اصل میں جو بہترین کیس کا سامنا کرنا پڑا جب وہ اسٹیج پر آئے.
کس طرح بہت سے اقدامات ہیں جو بائنری تلاش میں تھا؟ >> 1 [طالب علم.
1، صرف اس لئے کہ وہ خوش قسمت ہے.
لیکن یہ ٹھیک ہے کیونکہ ومیگا بہترین کیس منظرنامے سے مراد،
بہترین کیس آدانوں، یہاں تک کہ اگر یہ صرف بے ترتیب گونگا قسمت ہے.
>> اب، یہ بھی اب ہم چھٹی خالی صرف قسم جا رہے ہیں.
کے بارے میں اب کس طرح بلبلا طرح ہے؟
بلبلا طرح سے بدترین صورت میں، ہر کوئی معکوس ترتیب میں ہے،
تو ہم bubbling کے بہت کچھ ہے.
لیکن کس طرح بہت سے اقدامات ہیں جو بدترین صورت میں لے جا رہا ہے؟ >> [طالب علم] مربع N.
یہ ن مربع تھا، کیونکہ اگر آپ اس کے بارے میں کیا سوچتے ہیں،
اگر فہرست مکمل طور پر پیچھے کی طرف ہے - 8 یہاں ہے، 1 یہاں ہے -
کے طور پر بات بلبلا شروع، 8 نمبر اس طرح، اس طرح منتقل کرنے کے لئے کی جا رہی ہے،
اس طرح، اس طرح، لیکن جہاں بدترین صورت میں نمبر 7 ہے؟
وہ اب بھی وہاں ہے. تو ہم نے اسے بار بار کیا ہے.
اور یہ ہے جہاں ہم ن اقدامات، تو N - 1 اقدامات، تو N - 2 قدم ہے.
اور اگر تم اس کے لئے میری بات - کہ اگر آپ اس قسم کی ضرب،
یہ تقریبا آخر میں (ن) کچھ دوسرے الفاظ کے ساتھ کہ اب ہم صرف نظر انداز کریں گے مربع -
تو بدترین بلبلا طرح میں مربع (ن) ہے، یا لے دے.
لیکن بلبلا طرح کے ساتھ سب سے بہترین کیس کے بارے میں کیا؟
بہترین دوسری صورت کیا ہے؟ کی تعداد کے سب پہلے ہی کے مطابق کر رہے ہیں.
اور کیا heuristic میں استعمال کیا جاتا ہے، چال میں استعمال کیا تھا،
احساس ہے کہ میں نے کوئی کام نہیں کیا تھا اور جلد اس لئے روک سکتا ہے؟
[طالب علم] ایک بار چیک کریں. >> ایک بار چیک کریں. لیکن میں راستے میں کیا کر رہا تھا؟
میں کتنے سویپ میں نے ٹریک رکھ رہی تھی.
اور مجھے احساس ہوا کہ اگر میں نے اپنی انگلیاں پر کوئی سویپ شمار نہیں کیا ہے، تو میں نے کوئی کام نہیں کیا ہے.
میں بات کو یقینی طور سے کوئی کام نہیں دوبارہ کوشش نہیں ہے، تو میں روک سکتے ہیں.
>> تو بلبلا طرح سب سے بہتر صورت میں جب فہرست پہلے ہی کے مطابق ہے،
ومیگا سنکیتن ہے تم بہترین کیس وقت چلنا کہیں گے؟
یہ صرف ن ہے. ہم کچھ کام کرنا ہے، لیکن ہم صرف کام کے 1 ٹہلنے مالیت کرنا پڑے گا.
اور یہاں بھی میں اس حصے کو خالی چھوڑ جا رہا ہوں.
اور اب انتخاب کی طرح ہے.
سلیکشن طرح مجھے سب سے چھوٹا شخص plucking بار بار کیا تھا.
اور جو ہم تھا رننگ ٹائم کا کہنا ہے کہ کیا؟
یہ تھا ن بدترین صورت میں مربع.
اور بدقسمتی سے، یہ بہترین صورت میں بھی مربع ن ہے
کیونکہ میں پوری دنیا کے سروشتھ طرح کی نہیں ہے؛
میں صرف ایک مکمل iteration جانتے ہیں کہ میں نے واقعی سب سے چھوٹا شخص مل گیا ہے.
تو انتخاب کی طرح کی طرح بیکار ہے، اس معنی میں
لیکن الٹا بدیہی کی قسم ہے.
یہ بہت آسان ہے کوڈ کیونکہ تمام ہے تمہیں کیا کرنا ہے ہے loops کے لئے اندر در اندر کے ایک جوڑے لکھیں
عام طور پر، یہ سب سے چھوٹی عنصر کی تلاش کے ذریعے جاتا ہے
اور پھر سب سے چھوٹی عنصر ہے جہاں اس کی فہرست کے آخر میں تعلق رکھتا ہے رکھتا ہے.
تو یہاں بھی ایک تجارتی آف ہونے جا رہا ہے.
وقت کی رقم آپ اور اصل میں کوڈ لکھنے کی طرف سے کچھ ترقی کے بارے میں سوچنا لیتا ہے
زیادہ وقت کو بہت اچھی طرح سے لیتے ہیں اگر آپ کو ایک بہتر الگورتھم اور تیز کارکردگی چاہتے ہیں کر سکتے ہیں.
>> لیکن اگر آپ واقعی کوڈ اپ کچھ قسم فوری اور گندی
اور قسم کی ممکن بیوکوفی خیال ہے جو آپ کے بارے میں سوچ کر سکتے ہیں،
کہ آپ نے کوڈ میں چند منٹ لگ سکتے ہیں، لیکن بڑے ڈیٹا سیٹ کے ساتھ
آپ کا الگورتھم گھنٹے لگ چلانے کے لئے کر سکتے ہیں.
اور گریجویٹ اسکول میں بھی کبھی کبھی میں یہ تجارت آف گے.
یہ 3am ہو گا، میں کچھ بہت بڑی ڈیٹا سیٹ کا تجزیہ کرنے کی کوشش کر رہا تھا
سیکورٹی تحقیق میں کیا کر رہی تھی سے متعلق ہے، اور یہ یا تو 5 منٹ خرچ کیا گیا
میرے اعداد و شمار کا تجزیہ کرنے اور سو جاؤ پروگرام tweaking
یا 8 گھنٹے ہو رہی صرف حق خرچ کرتے ہیں تو اسے فوری طور پر چلتا ہے اور سو نہیں جاتے.
اور تو وہاں بھی ہوش کے فیصلے کی قسم ہے.
کم ترقی وقت، نیند.
ماضی میں، میں نے شاید نہیں حوصلہ افزائی کرنا چاہیئے کہ
جب یہاں کا مقصد کوڈ کے معیار کو بہتر بنانے کے ہے،
لیکن یہ بھی حقیقی دنیا میں ایک بہت ہی مناسب تجارتی آف ہے.
کم وقت، کم کارکردگی یا اس کے برعکس ہے.
تو ہم یہاں آخر میں تھیٹا کے بارے میں بات کرنے کا موقع ملے.
تھیٹا سنکیتن کچھ کمپیوٹر کے سائنسدانوں کو بات چیت میں لا سکتے ہیں ہے
جب بڑی O اور ومیگا پہلے جیسا نہیں ہو.
آپ تھیٹا واقعی پیغام کو بھیجنے کے لئے ہے کہ اس طرح کی سخت پابند ہے کا کہنا ہے کہ.
کوئی فرق نہیں پڑتا کہ منظر نامے اچھا ہے یا برا ہے، یہ مربع ن ہے.
تو یہ ان کہانیوں میں صرف متعلقہ نہیں ہے.
اضافے کی طرح گزشتہ ایک ہم کو دیکھا ہے،
میں صرف جہاں سب کو صحیح جگہ میں داخل کیا گیا تھا.
بہترین صورت میں اندراج کی قسم کی رننگ ٹائم کیا تھا جیسا کہ ہم نے اسے یہاں دیکھا؟
[طالب علم] سب سے اچھا مقدمہ؟ >> سب سے اچھا معاملہ.
>> یہ (ن) کی وجہ سے سب کو بہترین صورت میں حل کیا گیا،
اور سیمی اور کوئی نہیں واقعی میں منتقل کرنے کے لئے تھا.
وہ پہلے ہی اپنی صحیح جگہ میں تھے.
بہترین صورت میں تو اندراج کی طرح اس معاملے میں ہے،، ن.
لیکن یہ سب سے زیادہ کیس میں مربع ن کی طرح ہے. کیوں؟
اگر انسانوں کی فہرست معکوس ترتیب میں ہے،
میں نے سب سے پہلے 8 تعداد کے ساتھ شروع کرتے ہیں اور میں نے صحیح پوزیشن، جو یہیں ہے میں اسے داخل یا اس.
طرف کے اقدام کا مجھے کس طرح کی ہے. یہ لوگ ناچھانٹا ہوا، وہ کر رہے ہیں یا وہ کے مطابق ہے.
لیکن اب میں جو اگلے تلاش کرنے کے لئے ہوا ہے؟ >> [طالب علم] 7.
بدترین صورت میں 7 معکوس ترتیب میں ہے کیونکہ.
>> تو یہاں 7 ہے. 7 کہاں ہے؟ یقینی طور پر میرے پیچھے.
لیکن اب 7 اصل میں فوری طور پر میرے پیچھے لیکن 8 نمبر کے پیچھے نہیں ہے،
تو میں، کا کہنا ہے کہ "مجھے معاف کیجئے گا، 8 نمبر ہے، آپ براہ مہربانی اس طرح سے منتقل کریں کر سکتے ہیں
"7 کے لیے جگہ بنانے کے لئے؟" اب میں 6 سامنا.
"اوہ، معاف کرنا، 8 نمبر اور نمبر 7، 6 کے لئے کمرے میں منتقل کر سکتے ہیں؟"
تو دوسرے الفاظ میں، اندراج طرح سے، اگرچہ میں زیادہ تحریک نہیں کر رہا ہوں،
میرے پیچھے لوگوں کو بہت زیادہ کام کر رہے ہیں، اور یہ کہ کسی وقت کی لاگت ہے.
یہ کمپیوٹر وقت کی لاگت جا رہا ہے.
تو ہم اندراج قسم کے کیس میں اب بھی شکار ہیں.
اگر آپ کے اقدامات کی کل تعداد شامل شروع، ہم نے ختم تقریبا ن مربع مار
کیونکہ یہ لوگ انسانی کے لئے کمرے میں کرنے کی ضرورت ہے اس فہرست میں واپس داخل.
اور تو اس صورت میں تھیٹا صرف ہاتھ میں خاص طور پر کہانی پر لاگو نہیں ہے.
وہ تمام اچھے اور اچھی بات ہے. ہم رننگ ٹائم کے بارے میں بات کرنے کا ان مختلف 3 طریقے ہیں.
لیکن کیا یہ حقیقی معنوں میں اصل میں اگر ہم واقعی ایک الگورتھم کوڈ کرنے کی کوشش کا مطلب یہ ہے؟
>> مجھے تجویز ہے کہ وہاں اس سے بھی بہتر طریقہ ہے
کہ خود کو کچھ ٹریڈ آف ہے.
ہم نے اس وقت اس طرح ضم جا رہے ہیں، اور اس طرح کی اس جادو الگورتھم کی ہے
کہ صرف تیزی سے کسی نہ کسی طرح کام کرتا ہے، اور یہ بہت آسان ہے کم از کم pseudocode میں اظہار کرنے کے لئے،.
اس الگورتھم کو ضم طرح کے عمل کے مندرجہ ذیل کی جا رہی ہے.
(ن) کی تعداد، (ن) لوگ، - جو بھی ہو - پہلے وویک چیک عناصر ن کب دیا رہے ہیں.
اگر N 2 سے کم ہے ضم، طرح صرف روکتا ہے. اس کے فوائد، تو بات کرنے کی.
اگر آپ ن 2 سے بھی کم ہے کیوں بند ہو جائیں گے؟ >> [اشراوی طالب علم کے جواب]
ٹھیک ہے. (ن) اور پھر (ن) کی فہرست میں نمبر نہیں ہے، فہرست کا سائز ہے.
اگر (ن) 2 سے بھی کم ہے، اس کا مطلب ہے کہ یا تو آپ کی فہرست 1،
تم ظاہر ہے جہاں کے مطابق اگر یہ نمبر 1 ہے رہے ہیں،
یا، 0، جس صورت میں وہاں کی چھانٹی کرنے کی کوئی بات نہیں ہے
تو ہم بیس کیس کی اس طرح کی ضرورت ہے.
اگر فہرست اتنی مختصر ہے کہ بس کرنا کچھ بھی نہیں ہے، لفظی کچھ بھی نہیں ہے. واپس جائیں.
ورنہ عناصر کے بائیں نصف ترتیب، تو عناصر کے دائیں نصف ترتیب،
پھر 2 کے مطابق حصوں کو ضم.
>> اس طرح کا ایک چھوٹا سا دھوکے باز کی طرح لگتا ہے جس میں تم سے پوچھ رہا ہے کہ کس طرح عناصر ترتیب رہا ہوں
اور تم مجھ سے کہہ رہے ہیں "بائیں نصف ترتیب، صحیح نصف ترتیب."
میں کی طرح ہوں "ٹھیک ہے آپ کو بائیں نصف ترتیب کیسے ہو؟"
"بائیں نصف کے بائیں نصف ترتیب، بائیں نصف کے دائیں نصف ترتیب، اور پھر کیا ہے."
آپ کو cyclically وضاحت جو اس ترتیب کا مطلب کی طرح ہیں،
لیکن یہ پتہ چلا ہے کہ اس معاملے میں واقعی شاندار ہے.
یہ سچ نہیں ہے اس شیطانی سائیکل ہے جو کبھی ختم نہیں ہوتا
کیونکہ یہ ختم کب ہوتی ہے؟ >> [طالب علم] جب تم 1 بات تک پہنچنے.
جب آپ 1 بات تک پہنچتے ہیں.
تو اگرچہ آپ کو 8 لوگوں کے ساتھ شروع کریں گے اور میں کہتا ہوں کہ ہو سکتا ہے، انہوں نے کہا کہ ان لوگوں کے بائیں نصف قسم
ان 4 افراد، "تو میں کہتا ہوں،" آپ کو بائیں نصف کس طرح ترتیب ہے؟ "
"، 2 افراد یہاں ترتیب." اور پھر آپ کی طرح ہیں "ٹھیک ہے، ٹھیک ہے،".
"آپ کو ان لوگوں کے بائیں نصف کو کس طرح ترتیب ہے؟"
"صرف اس 1 شخص یہاں ترتیب." شاندار اب وحی کیا ہے؟
میں 1 شخص کو ترتیب ہے. ہو گیا. میں کوئی بھی کام کرنے کی ضرورت نہیں ہے.
لیکن اب میں اس شخص کو ترتیب ہے، لیکن وہ ایک شخص ہے، کرنا کچھ نہیں ہو.
>> تو جادو بظاہر اس تیسرے مرحلے میں ہے: کے مطابق حصوں کو ضم.
تو ضم طرح اس شاندار بصیرت لیتا ہے کہ اگر آپ کو ایک بڑا مسئلہ ٹوٹ
2 چھوٹے مسائل، identically سائز میں
اور پھر گلو کے آخر میں صرف قسم کے چھوٹے حل مل کر
میری تجویز ہے کہ ہم بہت کرتے ہیں، زیادہ بہتر [ٹیپ کی آواز] کر سکتے ہیں
انتخاب طرح یا اندراج طرح کے کسی سے.
میں واقعی میں کیا گیا ہے آدھے گھنٹے کے لئے نظر انداز کرتے ہوئے، لیکن مجھے سچ میں پتہ نہیں کیا ہو رہا ہے
آج باہر. [whirring آواز] [ہنسی]
تو چلو دیکھتے ہیں، اگر ہم نے ہمارے دوست روب Bowden کی طرف سے ایک چھوٹی سی مدد کے ساتھ یہ دیکھ سکتے ہیں.
ضم طرح کے عمل میں 2 بڑے اقدامات ہیں.
سب سے پہلے، مسلسل حصوں میں کپ کی فہرست تقسیم
جب تک ہم ان میں صرف 1 کپ کے ساتھ کی فہرست کا ایک گروپ ہے.
اگر ایک فہرست طاق پر مشتمل ہے فکر نہ کرو
اور آپ ان کے درمیان ایک بالکل صاف کٹ نہیں بنا سکتے.
بس منمانے لینے جو فہرست اضافی کپ اندر شامل کرنے کے لئے
تو ہم ان فہرستوں کو تقسیم.
اب ہم نے 2 فہرستوں ہے.
اب ہم نے 4 کی فہرست ہے.
اب ہم ہر ایک کی فہرست میں ایک کپ کے ساتھ 8 کی فہرست ہے.
تو اس 1 مرحلے کے لئے ہے.
مرحلے کے لئے 2 ہم ضم الگورتھم ہم پہلے سیکھا کا استعمال کرتے ہوئے کی فہرست کے بار بار جوڑوں کو ضم کریں.
108 اور 15 ضم ہم 15 کی فہرست، 108 کے ساتھ ختم.
50 اور 4 ضم ہم 4 50، کے ساتھ ختم.
8 اور 42 ضم ہم 8، 42 کے ساتھ ختم.
اور 23 اور 16 ولی ہم نے 16 سے آخر، 23.
اب ہمارے تمام فہرستوں 2 سائز کے ہیں.
یاد رکھیں کہ 4 فہرستوں میں سے ہر ایک کے مطابق ہے،
تو ہم کی فہرست کے جوڑوں کو دوبارہ ضم کرنا شروع کر سکتے ہیں.
15 اور 108 اور 4 اور 50 ضم کرنا ہم سب سے پہلے 4 لے، اس کے بعد 15،
تو، 50 پھر 108.
8، 42 اور 16، 23 ضم ہم پہلے 8، تو 16 لے،
پھر 23، پھر 42.
تو اب ہم 4 سائز کے صرف 2 کی فہرست ہے، جن میں سے ہر ایک کے مطابق ہے.
تو اب ہم ان 2 کی فہرستوں ضم.
سب سے پہلے ہم 4 لے، پھر ہم 8 لے، اس کے بعد ہم 15 لے
16 اور 23 اور 42 اور 50 اور 108.
اور ہم کیا کر رہے ہیں. اب ہم ایک کے مطابق کی فہرست ہے.
>> روب کچھ ہے کہ ہم نے ابھی تک نہیں کیا ہے کا فائدہ لینے کے طرح تھا.
یہ مشورہ دیا ہے، کیا گیا تھا لیکن ہم یہ اصل میں نہیں کیا.
کپ کہ تجویز کے ساتھ وہ کچھ کر رہا تھا جسمانی
وہ وقت کے علاوہ کچھ وسائل خرچ کر رہی تھی. >> [طالب علم] خلائی. >> یہ خلا تھا.
حقیقت یہ ہے کہ وہ دو سطح کے ٹیبل کے اس طرح سے تھا جہاں انہوں نے خلائی تھا یہاں
اور یہاں نیچے خلا اصل مطلب تھا کہ اس نے دو بار زیادہ سے زیادہ جگہ کا استعمال کرتے ہوئے کر رہا ہے
اندراج کی طرح، بلبلا، ترتیب دیں، یا انتخاب طرح - ہماری الگورتھم کے کسی بھی اس طرح اب تک کے طور پر -
لیکن وہ اقدام کی چیزوں کی طرح اس اضافی جگہ استعمال کیا گیا تھا اور پیچھے
جبکہ حکم میں چیزوں کو مد نظر رکھتے ہوئے.
اور اگرچہ یہ محسوس ہوتا ہے جیسے ہم کے مطابق فہرست میں ہے، کہ اس نے محسوس کیا جیسے اس میں کچھ دیر لے لیا.
حقیقت میں، روب کیا کر رہی تھی بالکل اس الگورتھم تھا.
وہ پہلے سائز N کا مسئلہ لیا، بائیں نصف اور ایک صحیح نصف میں تقسیم کیا.
اس وقت ہے جب وہ کپ کو منتقل کر دیا گیا ہے. پھر انہوں نے اس عمل دہرایا.
انہوں نے 2 کے 2 سیٹ میں یہاں اور یہاں 4 تقسیم کیا ہے.
اس کے بعد انہوں نے اس عمل کو بار بار اور 2 1 2 سیٹ میں ان مختلف کپ میں سے ہر ایک کے لئے تقسیم.
اور یہ ہے جہاں شاندار موقع پیدا ہوتا ہے.
کہانی میں اس وقت، روب 1 سائز کے 8 فہرستوں تھا،
جن میں سے سب پہلے ہی کے مطابق کیا گیا ہے.
>> تو پھر وہ کیا کارروائی تھا؟
Pairwise وہ اس کے مطابق کی فہرست اور اس کے مطابق کی فہرست کو لیا اور ان کو ملا دیا گیا ہے.
پھر اس نے اس سے لیا اور ان ضم، تو یہ بھی اور ان کے ضم،
تو یہ ایک اور نے ان کو ملا دیا گیا ہے.
اور پھر کیا وہ اگلے کیا؟
اس کے بعد انہوں نے بڑی فہرستوں تو دوبارہ ضم اور بڑی فہرستوں کی دوبارہ ضم.
اور اگر آپ اس کے بارے میں اب لگتا ہے کہ صرف intuitively، کیا وہ واقعی کر رہے تھے؟
انہوں نے مسئلہ نصف میں تقسیم کیا گیا تھا، نصف میں، نصف میں نصف میں،
تاکہ ان سپر چھوٹے کی فہرست حاصل کرنے کے لئے.
پھر انہوں نے ڈبل، ڈبل، ڈبل ڈبل، امتزاج کی طرح تھا.
تو اس نے سارا کام کے طور پر دو بار کر رہا تھا جیسا کہ ہم نے ابھی تک دیکھا ہے
تقسیم اور فتح، لیکن کوئی بڑی بات نہیں شامل کچھ کے ساتھ.
دو بار زیادہ سے زیادہ کام اتنا بڑا سودا نہیں ہے. یہ صرف ایک مستقل عنصر ہے.
اور بہت کچھ ہمارے ریاضی پہلے اظہار کی طرح، میں صرف مسلسل عوامل پار جا رہا ہوں
2 مرتبہ کی طرح. کسے پرواہ ہے؟ اگر یہ 2 ارب 2 مرتبہ، کہ اب بھی بہت سے اقدامات کے ہے.
تو اس ولی قدم اہم بصیرت لگتا ہے.
ہم اس کے ذریعے سے پہلے صرف numerically چل - اوہ، یہ ابھی تک جاری نہیں ہے.
numerically صرف اصل میں کس طرح یہ ادا کرتا ہے کو دیکھنے کے لئے کے ذریعے چلنے دو.
یہ زیادہ تر صرف ایک چھوٹا سا غریب آدمی کی حرکت پذیری ہے.
چلو، اس تجویز ہے.
ضم طرح کی رننگ ٹائم - ہم صرف اس کے بارے میں بات کرنے کا ایک طریقہ کی ضرورت ہے.
یہ ریاضی نہیں ہے، یہ صرف اپنے آپ کو ظاہر کرنے کا ایک succinct راستے سے قسم ہے.
تو T وقت کی نمائندگی کرتا ہے اور این جو کی نمائندگی کرتا ہے؟ >> [طالب علم] کا سائز -
>> [Malan] مسئلے کے سائز، لوگوں کی تعداد.
لہذا میں نے دعوی کیا کہ چلانے ن لوگوں کو الگ الگ کرنے کا وقت آ 0 رقم ہونے جا رہا ہے کر رہا ہوں
اگر (ن) 2 سے بھی کم ہے، کیونکہ اگر آپ کے پاس 1 کپ یا کوئی کپ نہیں ہے، تو آپ کو حل کرنے کی کوئی بات نہیں ہے.
لیکن عام طور پر، میں تجویز ہے کہ رننگ ٹائم ن عناصر کو الگ الگ کرنے پر جا رہا ہوں
وقت بائیں نصف ترتیب پر لے جاتا ہے ہے کے علاوہ صحیح نصف ہو جائے گا
پلس - کیا اس اضافی + ن ہے؟ >> [طالب علم] ضم طرح.
[Malan] یہ اصل میں ولی ہے، کیونکہ اگر تم N / 2 عناصر یہاں ہے
اور آپ N / 2 عناصر یہاں ہے، کتنا وقت ان ضم کرتا ہے؟
بس روب کی طرح، آپ کو یہاں اس سے توڑو ہے، شاید یہاں جمع کرنا،
یہاں جمع کرنا، یہاں جمع کرنا، یہاں جمع کرنا.
آپ کپ میں سے ہر ایک کو ایک بار چھو.
اور اگر میں 4 کپ کے علاوہ 4 کپ ہے، 8 کپ ہے
یا عام طور پر، 8 ن کپ.
تو ہم ولی قدم (ن) کے طور پر اظہار کر سکتے ہیں،
اور یہ کہ لفظی اوقات کی تعداد لوٹنے جسمانی چھوا شامل
ان Styrofoam کپ کے ایک.
تو اب ایک صوابدیدی مثال دیتے.
اگر 16 کپ ہے، چھںٹائی کی رننگ ٹائم کیا ہے، روب الگورتھم، 16 کپ کا استعمال کرتے ہوئے؟
یہ 2 اوقات وقت کی رقم 8 کپ ترتیب لیتا ہے
کیونکہ ہم نے 8 کپ یہاں ہے، 8 کپ یہاں.
مجھے پتہ نہیں کتنی دیر تک کہ لیتا ہے، تو ہم اسے T کے طور پر لمحے کے لئے generalizing رہے ہیں.
کون جانتا ہے کہ یہ کیا ہے؟
لیکن اب میں تکراری طور پر یا بار بار ایک ہی سوال پوچھ ترتیب کر سکتے ہیں.
کتنا وقت 8 کپ ترتیب کرتا ہے؟
8 کپ میں کہنے جا رہا ہوں وقت کی رقم 4 کپ کے علاوہ 4 کپ ترتیب پر لے جاتا ہے ہے لیتا ہے،
تو ان کے ولی مل کر.
ٹھیک ہے. ہم پہلے سے ہی ایک سائیکل میں ہو رہے ہیں. کتنا وقت 4 کپ ترتیب کرتا ہے؟
4 کپ ترتیب پر لے جاتا ہے ہے 2 کپ کے علاوہ 2 کپ کو حل کرنے کے علاوہ ولی کے عمل ہے.
ٹھیک ہے. کتنا وقت 2 کپ ترتیب کرتا ہے؟
2 کپ وقت کی رقم 1 کپ ترتیب پر لے جاتا ہے ہے کے علاوہ وقت یہ دوسرا کپ ترتیب پر لے جاتا ہے ہے ہے
علاوہ وقت کی رقم ضم لیتا ہے، جس میں صرف 2 ہے.
>> ٹھیک ہے. آخری سوال. کتنا وقت 1 کپ ترتیب کرتا ہے؟
بنیاد مقدمہ ہے کہ ہم نے پیش گوئی کی ہم پہلے مارا تھا.
حقیقت یہ ہے کہ یہ کوئی کام نہیں لیتا ہے جو مسائل کی سب سے چھوٹی ترتیب
کا مطلب ہے اب کہ، گریڈ اسکول کے سٹائل کے ترتیب دیں
ہم نے ان اعداد و شمار کے اندر واپس plugging شروع کی جا سکتے ہیں
اب ہم یہ جانتے ہیں 1 T کیا ہے، میں 1 T 0 میں ہونا کر سکتے ہیں.
یہ آپ کے وزٹرز کا ریکارڈ رکھا 2 T، جس میں اعلی اپ میں تو ہونا کر سکتے ہیں کا جواب دے گا.
کہ کے وزٹرز کا ریکارڈ رکھا جائے گا. میرے 4 T دے گا، جس میں اعلی اپ میں ہونا کر سکتے ہیں.
کہ کے وزٹرز کا ریکارڈ رکھا جائے گا. میرے 8 T دے گا، جس میں اعلی اپ میں ہونا کر سکتے ہیں.
اور اگر میں واقعی میں ان جوابات میں plugging کی طرف سے کرتے ہیں کہ ریاضی،
میں تو 16 T 64 ہے.
اور 64 اور جو کی نمائندگی کرتا ہے؟
اگر 16 T ہے، جی ہاں، یہ 16 بار 4.
تو میں دعوی کرتے ہیں اب ہے کہ اس بات کی رننگ ٹائم طرح ضم فون -
اور یہ ہیں ہم ابھی تک دیکھا ہے fanciest جا رہا ہے -
کیا ہے اور اس کا کہا جا جا ن لاگ ان ن
وجہ سے کتنی بار نصف میں ایک کپ کے پورے گچرچھی تقسیم لوٹنے کر سکتے ہیں؟ ن لاگ ان کریں.
یہ فون بک مثال کے طور پر ایک ہی ہے، مثال کے طور پر خود گنتی کے طور پر ایک ہی ہے.
>> تمہیں کتنی بار اور نصف میں کچھ کی تقسیم کر سکتے ہیں؟
تاہم، وہاں اس ولی قدم ہے.
آپ نصف میں کپ بار بار بار تقسیم ہو سکتا ہے،
لیکن ہر بار تم جا رہے ہو ضم کرنا پڑے.
اور ہم نے پہلے کہا ہے کہ این کپ ولی ن اقدامات
کیونکہ آپ ایک کپ پر جمع کرنا ہے، ایک کپ جمع کرنا، اور تم ہر کپ ایک بار چھو ہے،
روب طرح کیا.
تو اگر ہم کچھ لاگ ان کریں N اوقات کر رہے ہیں اور ہم نے ان تکرار میں سے ہر ایک پر ن باتیں کر رہے ہیں،
ان halvings میں سے ہر ایک، ہم نے (ن) کے اوقات کے لاگ ان ن ہے.
تو اگر ہم اس مثال میں 16 میں ہونا 16 16 بار لاگ ان -
کیوں یہ اب کے لئے معاملہ ہے کے بارے میں فکر مت کرو کیونکہ میں نے بیس تیار نہیں ہے -
لیکن 16 2 اڈے کے لاگ ان 4، 16 4 اوقات 64 ہے.
لیکن اس کے برعکس کی طرف سے، اگر ہم 16 کی تعداد کے ساتھ بلبلا طرح یا انتخاب طرح یا اندراج کی طرح استعمال کیا ہے،
رننگ ٹائم ہوتا اگر (ن) 16؟
16 مربع، جو 256 ہے، جو یہاں تک کہ اگر آپ ریاضی کے بعد کافی نہیں ہے، کریں گے
256 64 سے بھی بڑا ہے. یہ واقعی جادو یہاں takeaway ہے.
اور احساس ہے کہ چھوٹے مثالوں میں آپ اس کے ذریعے ایک pset پر کام کر رہے
زیادہ بدیہی تمام کر دیتا ہے.
لیکن کیا ہے کہ واقعی اس الگورتھم کی احساس کے لحاظ سے کا مطلب یہ ہے:
اگر ہم واقعی ضم طرح میں یہاں دیکھتے ہیں - مجھے اس ونڈو میں یہاں ھیںچو -
یہ تھوڑا سا مختلف مثال ہے جس میں ہم سب ان یلگوردمز کی 3 ہے -
بلبلا، انتخاب، اور ضم - پارٹی کی طرف سے کی طرف.
>> وہ سب بے ترتیب سلاخوں کے ساتھ کرنا شروع کر دیا ہے، اور یہ اچھی بات ہے.
کوئی بھی ایک دوسرے پر ایک بنیادی فائدہ ہے.
میں ایک لمحے میں جا رہا ہوں یہ متحرک تصاویر میں سے ہر ایک پر کلک کریں - شروع کریں، شروع، شروع کریں -
تاکہ میں کر سکتا ہوں روزہ کے طور پر، تقریبا ایک ہی وقت میں، وہ سب کے سب شروع
دو اور غور کریں کہ بلبلا طرح برا وقت چل رہا کیس کیا ہے؟ >> [طالب علم] مربع N.
N مربع. سلیکشن طرح سب سے زیادہ وقت چل رہا معاملہ ہے؟ N مربع.
اور ضم طرح بظاہر ہے - یہاں تک کہ اگر آپ ریاضی کی پیروی کافی نہیں تھا،
وقت کے ساتھ بہت بدیہی ہو جائیں گے -، ہم دعوی کرتے ہیں، (ن) بار لاگ ان کریں (ن) ہے.
اور اس وجہ سے لاگ ان ن سختی سے کم ہے (ن) ایک بار ہم نے بڑی تعداد میں ہیں،
(ن) کے بار لاگ ان ن ن کے اوقات سے چھوٹا ن ن یا مربع ہے.
تو کیا یہ اصل میں رننگ ٹائم کے لحاظ سے ایک بہتر الگورتھم محسوس ہوتا ہے،
(ن) کے اوقات کے لاگ ان ن مربع ن کے خلاف ہے؟ یہاں ہم چلے. پر کلک کریں، کلک کریں، کلک کریں.
>> یہی ہے جو ضم طرح کی طرح کچھ استعمال کرنے کے لئے کا مطلب ہے.
ہم نے ایک لمحے ہے. دو دیکھو یہاں کیا ہوتا ہے.
جس کی رقم بلبلا طرح ہے [منہ دبا ہںسنا]
یہ بلکہ کبھی کبھی ان پٹ پر منحصر ہے.
چلو دیکھتے ہیں.
چلو. ایسا لگتا ہے جیسے وہ پکڑ رہا ہے. >> [طالب علم]، بلبلا طرح جاؤ!
[طالب علموں بڑبڑا]
[Malan] جی ہاں، جی ہاں.
[بڑبڑا طالب علموں] جاؤ، جاؤ، جاؤ!
[تعریف] [تمام اتساہی]
1 آخری، حتمی ڈیمو کے ساتھ تو اب، اگر یہ تھوڑا مشکل ہے ریاضی کے ارد گرد آپ کے دماغ لپیٹ
یا وہاں تصور کی طرح، آپ کی رفتار اصل میں سن سکتے ہیں
کے مختلف مختلف یلگوردمز.
یہ ایک حرکت پذیری کی ہے کہ اصل میں ساتھیوں آواز کوئی ہے
گماگمن کے عمل اور سلاخوں کے عروج کے ساتھ.
جیسا کہ ہم یہاں نظر آئے گا، کچھ زیادہ چھنٹائی یلگوردمز وہاں ہے کہ لوگوں کے بارے میں سوچا ہے.
یہ پہلا اندراج کی طرح جا رہا ہے، اور اس سے اڑ جائے گا
اور آپ کو کہ کس طرح ان مختلف الگورتھم کے کام کی ایک شروی احساس دیتے ہیں.
یہاں اندراج طرح ہے.
[الیکٹرانک beeping]
[Malan] بلبلا طرح.
[تیز الیکٹرانک beeping]
[Malan] سلیکشن طرح.
[تیز الیکٹرانک beeping]
[Malan] ضم طرح ہے.
[الیکٹرانک beeping]
[ہنسی] [beeping سست]
[Malan] GNOME ترتیب دیں.
[الیکٹرانک beeping]
>> یہ CS50 ہے. ہم اگلے ہفتے آپ کو نظر آئے گا. [تعریف اور اتساہی]
>> [CS50.TV]