[موسیقی بجانے] 

ڈیوڈ جے MALAN: ٹھیک ہے. تو واپسی پر خوش آمدید. یہ CS50 ہے، اور ہے تین ہفتے کے اختتام. 

لہذا، گزشتہ کئی ہفتوں میں یاد ہم بہت تھوڑا سا خرچ کر دیا گیا ہے سی پر، پروگرامنگ پر، نحو پر وقت. اگر آپ اب بھی کر رہے ہیں اور اگر یہ بہت عام ہے ہونے کا مسئلہ سیٹ کریں 2 کے ساتھ جدوجہد دیوار کے خلاف اپنے سر پیٹنے. یہ خفیہ نظر خرابی کے پیغامات ہے اور کیڑے کہ آپ کافی نیچے کا پیچھا نہیں کر سکتا. کیونکہ، آرام کو یقین دلایا، کہ میں صرف ایک چند ہفتوں کا وقت تم پر واپس نظر آئے گا سیزر کی طرح چیزوں کو، اور [؟ V-genair،؟] شاید بھی توڑ، اور تم آ گئے صرف کس حد تک احساس وقت کی ایک مختصر مدت میں. کسی بھی تسلی ہے اگر ایسا ہے تو اب کے لئے وہاں میں پھانسی پر لٹکا. 

آج، اگرچہ، ہم تبدیلی کرنا شروع چیزوں کو اعلی سطح پر. اور ہم نے حاصل کی جاچکی کے لئے لے جانے کے لئے شروع ہے کہ آپ لوگ پروگرام کو کس طرح جانتے ہیں، یا اس پر کے آغاز میں کم از کہ اطمینان کا درجہ. اور ہم کس طرح ہم کر سکتے ہیں پر غور کرنے کا آغاز کریں گے مزید پروگراموں کے ڈیزائن کے بارے میں مؤثر طریقے سے. ہم اصلاح کے بارے میں کیسے جا سکتے ہیں ہمارے الگورتھم کی کارکردگی، اور عام طور پر زیادہ سے زیادہ حل دلچسپ مسائل. اور، کہ حاصل کی جاچکی کے لئے لے جانے کے لئے شروع ہم چاہتے تھے تو ہم کسی کو کوڈ کر سکتے ہیں ہم ذہن میں مثال کے طور پر کی. آج تو، ہم کی بورڈ مت چھونا کوڈ کے کسی بھی فارم کے لئے. یہ بہت زیادہ سطح پر ہو، اور گے بالآخر، مسائل کو حل کرنے کے بارے میں. 

لہذا اس نقطہ کرنے کے لئے حاصل کرنے کے لئے، آپ کے وزٹرز کا تجویز کرتے ہیں جو کہ مندرجہ ذیل سات rectangles کے پیچھے سات دروازے کی نمائندگی کرتے ہیں جس کے پورے گچرچھی ہیں نمبر، جن میں نمبر 50 ہے. مجھے اس پر یہ منصوبہ دو اس کے ساتھ ساتھ یہاں کی سکرین. اور ہم پر ایک رضاکار کی ضرورت ہے تجویز میرے سامنے ایک بڑی تعداد کو تلاش کرنے میں مدد دیکھنے کے لئے یہاں انٹرنیٹ. گلابی میں، اپ چلو. ٹھیک ہے. آپ کا نام کیا ہے؟ 

جینیفر: [اشراوی] 

ڈیوڈ جے MALAN: معاف کیجئے گا؟ 

جینیفر: جینیفر. 

ڈیوڈ جے MALAN: جینیفر. ٹھیک ہے، جینیفر. آپ سے مل کر اچھا لگا. اپ چلو. تو یہ یہاں سات دروازے ہیں، اور کیا میں، آپ نے ہمیں یہاں کے لئے کیا کرنا چاہتے ہیں اپنے ہم جماعتوں کے تمام کے سامنے، ہم سے تعداد میں، 50 کو تلاش کر رہی ہے. ایک بڑی تعداد کو تلاش کرنے کے لئے، آپ کے پیچھے جھانکنا کر سکتے ہیں صرف ٹیپ کی طرف سے ان دروازوں میں سے کسی دروازے میں سے ایک، اور اس پر اس تعداد کو ظاہر کرے گا. اور دیکھتے ہیں کہ کس طرح فوری طور پر آپ ہم سے نمبر، 50 تلاش کر سکتے ہیں. 

15. 16. 50. اچھی طرح سے کیا. ٹھیک ہے. جینیفر کے لئے تعریف کا گول. 

[تالیاں] 

ٹھیک ہے. تو آپ کی حکمت عملی کے لئے کیا تھا ، 50 نمبر کو تلاش کرنے؟ 

جینیفر: ام، میں شاید اگر سوچا - [اشراوی] 

ڈیوڈ جے MALAN: اوہ. یہ ایک دوسرے کو دے دو. تو آپ کی حکمت عملی کے لئے تھا ، 50 نمبر کو تلاش کرنے؟ 

جینیفر: تو میں نے ابھی سے شروع دیکھنے کے لئے شروع کیا سب سے پہلے نمبر ہو سکتا ہے تو، تھا، اور پھر میں نے سوچا وہ حل کر رہے ہیں، میں صرف کرتے رہیں گے اپ اعلی ٹیپ؟ 

ڈیوڈ جے MALAN: ٹھیک ہے. اور ہم نے محسوس کیا ہے لگ رہے ہو معاملہ ہو کہ. اگرچہ واپس چھیل تہوں چلو صرف تھوڑا سا، اور آپ کو جانا چاہتا ہوں آگے اور دوسرے دروازے ظاہر آپ نے منتخب کیا کر سکتا تھا؟ 

جینیفر: اوہ، عزیز. 

ڈیوڈ جے MALAN: آہ. 

جینیفر: تو میں صرف خوش ہو گیا. 

ڈیوڈ جے MALAN: تو کیا تم خوش ہو گیا. ٹھیک ہے. اتنا برا بھی نہیں. لیکن یہ ایک دلچسپ بات ہے بصیرت، صحیح؟ ، آپ کو فرض کیا گیا ہے، اور آپ کو حاصل کیا تو بے شک، وہاں تھوڑا سا خوش قسمت. لیکن تم تعداد نے مانا ہے کہ اگر کے مطابق، آپ کو زیادہ عین مطابق ہو سکتا ہے کہ متاثر کس طرح تمہارے رویے؟ 

جینیفر: وہ حل کر رہے تھے اگر ایسا ہے تو میں سب سے بڑا کرنے کے لئے شاید سب سے چھوٹی سوچا. 

ڈیوڈ جے MALAN: ٹھیک ہے. 

جینیفر: یا اس کے ختم ہونے کی وجہ سے اگر سب سے چھوٹا اس وقت سب سے بڑا، بہت بڑا. 

ڈیوڈ جے MALAN: ٹھیک ہے. تو سب سے چھوٹی کرنے کے لئے سب سے بڑا ہے، یا سب سے بڑا کرنے کے لئے سب سے چھوٹا. لیکن مجھے تجویز کرتے ہیں، آپ کو لگتا تھا اشوب ہو، اور لگتا ہے کہ وہ ، حقیقت میں، حل نہیں کیا گیا، کتنے کی ان کے دروازے آپ جھانکنا کرنا پڑا ہو کہ بدترین کیس میں کے پیچھے؟ 

جینیفر: ان میں سے سب. 

ڈیوڈ جے MALAN: ان میں سے سب. تو کی وسیع کرتے ہیں (ن) کے طور پر ہے. آمدید 7 ہو، لیکن لشکر طیبہ زیادہ ہے عام طور پر کی (ن) کے دروازے وہاں کا کہنا ہے کہ یہاں سکرین. تو بدترین صورت میں، آپ کو پڑے گا 7 دروازے، یا (ن) کے دروازوں کے پیچھے دیکھنے کے لئے. اور اس طرح یہ واقعی اس کا ایک تھوڑا سا ہے، ہے قسمت آج، لیکن یہ واقعی ایک لکیری ہے قسم کی الگورتھم، اگرچہ آپ کو کے ارد گرد اچٹیں کی طرح تھے. کیا یہ ٹھیک ہے؟ 

جینیفر: جی ہاں. 

ڈیوڈ جے MALAN: ٹھیک ہے، مجھے دیکھنے دو اگر آپ کا حکمت عملی تبدیلیوں میں ہمارے لئے منتقل اگر یہاں کے ساتھ ہماری دوسری مثال 7 مختلف دروازے. اسی نمبرز، لیکن اس وقت وہ حل کر رہے ہیں. ہونے جا رہا یہاں آپ کی حکمت عملی کیا ہے، آپ کے دماغ کے باہر ڈال کرنے کی کوشش کر رہا کیا دوسرے نمبرز تھے - 

جینیفر: ٹھیک ہے. 

ڈیوڈ جے MALAN: - پہلے؟ 

جینیفر: کی شروع کرتے ہیں سب سے پہلے ایک کے ساتھ. 

ڈیوڈ جے MALAN: ٹھیک ہے. سب سے پہلے ایک کے ساتھ شروع کریں. 4. اب تم کہاں جا رہے، اور کیوں؟ 

جینیفر: 4 واقعی چھوٹا ہے. انہوں نے طرح شاید سب سے چھوٹی ہو تو اگر سب سے بڑا کرنے کے لئے، اسے ہونا چاہئے - دو بار ہے، اور ہو. 

ڈیوڈ جے MALAN: ٹھیک ہے. چلو آپ کو لگتا ہے، جو دیکھ رہے ہو؟ 

جینیفر: گزشتہ ایک کی کوشش کریں. اچھا. 

ڈیوڈ جے MALAN: بہت اچھی طرح کیا. ٹھیک ہے. 

[تالیاں] 

ڈیوڈ جے MALAN: ٹھیک ہے. تو کیا تم واقعی یہ کر رہے ہیں تم بری، کیونکہ بہت اچھی طرح سے کر رہے. جس نے ہمیں کرنے کے قابل نہیں چھوڑ دیتا ہے بعض پوائنٹس بناتے ہیں. تو یہاں واپس لینے کی کوشش کرتے ہیں. 

جینیفر: ٹھیک ہے. 

ڈیوڈ جے MALAN: بہت اچھا بہر حال، کیا. تو کیا تم، آغاز میں شروع تم نے اسے اس کے بعد، آپ 4 نے دیکھا کہ آخر میں منتقل کر دیا. لیکن اگر آپ خوش قسمت نہیں ملی لگتا ہے ، اور وہاں فرض 50 کہیں اور تھا. کیا آپ کا تیسرا قدم کیا گیا ہے؟ 

جینیفر: ابتدا میں واپس جاؤ. 

ڈیوڈ جے MALAN: واپس جاؤ شروع کرنے کے لئے. ٹھیک ہے، لہذا آپ کو چھو لیا ہوتا 8 تھا جو اس دروازے،. ٹھیک ہے. تو یہ 50 نہیں ہے. تم کہاں اگلے دیکھا ہوتا؟ 

جینیفر: میں نے نہیں کیا تو وہ حل جانتے ہیں. 

ڈیوڈ جے MALAN: صحیح. ٹھیک ہے، تم نے کیا تھا اگر جانتے وہ حل کر رہے تھے - 

جینیفر: اوہ، جی ہاں، پتہ چلا. 

ڈیوڈ جے MALAN: - لیکن آپ نے ایسا نہیں کیا 50 ابھی تھا کہاں ہے؟ 

جینیفر: بس جاتے رہتے ہیں. 

ڈیوڈ جے MALAN: ٹھیک ہے. ٹھیک ہے. بڑھتے رہو. ٹھیک ہے، کہ جس کے ساتھ میں کام کر سکتے ہیں. 

جینیفر: ٹھیک ہے. 

ڈیوڈ جے MALAN: اب، تم ہو جاری رکھنے کے لئے جا رہے ہیں، کیا بات ہے آپ کی الگورتھم میں حمایت devolving. 

جینیفر: لکیری -. 

ڈیوڈ جے MALAN: یہ لکیری کی قسم ہے. لیکن دو، مجھے تجویز کرتے ہیں آپ کے وزٹرز کا موقع پر ہی ڈال دیا. آپ کے وزٹرز کا صفحہ کی تازہ کاری کرتے ہیں. اتنی ہی تعداد اسی نظام، ایک ہی دروازے. لیکن میں اس کے پہلے دن پر واپس لگتا ہے ہم میں ایک فون کتاب پھاڑ جب کلاس نصف، کی طرح، اور کیا تھا وہاں ہماری حکمت عملی؟ 

جینیفر: وسط میں شروع کریں. 

ڈیوڈ جے MALAN: ٹھیک ہے. تو وسط سے شروع. تو آگے بڑھو اور اس کے انکرن ہیں. کی طرف سے مشرق میں شروع اس دروازے سے ظاہر. تو نمبر 16. اتنا مضبوط آدمی نے کیا کیا ہوتا، جو نصف میں فون بک پھاڑ اگلے اندازہ کرنے کے لئے حاصل کرنے کے لئے؟ 

جینیفر: اس نصف میں دیکھیں. 

ڈیوڈ جے MALAN: اور کیوں حق ہے؟ 

جینیفر: وہ تھے تو سب سے چھوٹی قسم کا سب سے بڑا کرنے کے لئے، پھر 50 ہونا چاہئے کہ آخر میں. 

ڈیوڈ جے MALAN: اچھا. مکمل طور پر مناسب. تو ایک فون کتاب کی طرح، آپ کے پاس جاؤ حق کے طور پر بائیں طرف کی مخالفت کی، لیکن یہاں اہم takeaway ہے. اب آپ، دور پھینک دیتے ہیں، یا بند فاڑ کر سکتے ہیں اس مسئلہ کے نصف، آپ کو نہیں چھوڑ 7 دروازے کے ساتھ، لیکن واقعی صرف 3 کے ساتھ. جن میں سے تقریبا نصف ہے مسئلہ کا سائز. ٹھیک ہے. تو اب آپ کے پاس کیا تم ٹھیک کہہ جانے کے بعد کیا؟ 

جینیفر: تو 16، اب بھی بہت چھوٹی ہے 50 رشتہ دار، تو شاید میں، کوشش کریں گے یہ ایک جیسے. 

ڈیوڈ جے MALAN: ٹھیک ہے. 42. ٹھیک ہے، تو اب کیا بات ہے آپ کی تم سے کہہ سنتیں؟ 

جینیفر: میں پھینک کر سکتے ہیں یہ اور اس کے بعد صرف - 

ڈیوڈ جے MALAN: ٹھیک ہے. اچھا، آپ کو دور پھینک کر سکتے ہیں وہاں بائیں نصف. 

جینیفر: - اس سے ایک منتخب کریں. 

ڈیوڈ جے MALAN: اور درست. 

جینیفر: جی ہاں. 

ڈیوڈ جے MALAN: یہ مشکل ہے تو اگرچہ صرف وہاں ہے جب، شاید دیکھ کر 7 دروازے،، اب، کے بارے میں سوچتے کی مستقل مزاجی آپ کو صرف لاگو الگورتھم. گزشتہ صورت میں، تم نے کیا تھا بہت اچھا تھا، جس سے خوش ہو جاؤ. لیکن اگر آپ ایک heuristic استعمال کیا میں کہونگا. آپ کو آپ کے instincts کی طرح استعمال کیا جاتا ہے، اور یہ سندر ہے تو، حل جاننے کے شروع میں چھوٹے، ظاہر ہے، ہم نے حق کے لئے زیادہ جانا ہے. لیکن کچھ احساس میں، آپ کو خوش قسمت ہو گیا شاید یہ تعداد 100 تھی کیونکہ اور شاید 50 وسط میں زیادہ تھا. شاید 50 یہاں بھی تھا. 

لیکن آپ کو مختلف طریقے سے تھوڑا سا کیا اس وقت تھا، آپ ایک ہی کام کیا بار بار. اور میں دلیل ہے کہ کیا آپ کو صرف ، تاہم فون سے متاثر تھا کتاب مثال کے طور پر، بہت کچھ ہے مزید algorithmic، اور بہت کچھ کم خصوصی cased. بہت کم آسان. تو دن کے آخر میں، کس طرح کرے گا آپ کی کارکردگی کی وضاحت آپ کہاں گئے سب سے پہلے الگورتھم، بمقابلہ، بائیں سے دائیں یہاں دوسری الگورتھم؟ 

جینیفر: یہ ایک ہونا چاہئے، جیسا، ہو سکتا ہے وقت آدھا ہے، یا اس سے بھی زیادہ، جی ہاں. 

ڈیوڈ جے MALAN: ٹھیک ہے، شاید اس سے بھی زیادہ. کی اس پر تھوڑا مشکل دھکا ہیں. واقعی کیا، ہم اس جاری رکھتے ہیں تو منطق، ہم یقینی طور پر آدھی یہ دوسری الگورتھم کے ساتھ وقت چل رہا ہے کے نصف دور پھینک کر تعداد، لیکن ہم اگلے پر کیا کیا جینیفر انکشاف جب iteration، دوسرے نمبر؟ 

ہم پھر دروازے کی تعداد آدھی. اور پھر ہم نے اس کے بعد کیا کیا تو کے ساتھ کھیلنے کے لئے زیادہ دروازے تھے؟ ہم نے انہیں دوبارہ آدھا ہے، اور کرے گا اور پھر سے، اور میں دوبارہ. اور یہ سب صرف تم لوگوں کی طرح تھا کے پہلے ہفتے میں کھڑے آپ کو نیچے بیٹھنے کی کلاس، نصف، نصف آپ کو، آپ کے نصف بیٹھ کر ایک واحد تک بیٹھ کر روح کھڑا تھا. اور ہم نے کہا کہ کی رننگ ٹائم کہ لیا اقدامات کی تعداد تھی کس کے حکم پر نہیں ہیں؟ 

اسپیکر: 1 [اشراوی] 

ڈیوڈ جے MALAN: تو لاگ ان کی بنیاد (ن) کے 2، یا صرف اور صرف، (ن) کی لاگ ان کریں. تو لوگارتمی کچھ. اور گراف ایک براہ راست لائن نہیں تھا صرف بدتر اور بدتر ہو گیا ہے، یہ تھا نہیں کیا ہے کہ اس دلچسپ وکر وقت کے ساتھ اتنا برا ملتا ہے. تو اس خیال پر پکڑنے کرو کی جینیفر کا شکریہ ادا کرتے ہیں. اپ پر آنے کے لئے شکریہ بہت بہت. اور، ایک سیکنڈ. کوئی ڈیسک لیمپ آج، لیکن ہم CS50 کشیدگی گیند ہے. 

جینیفر: Yay. 

ڈیوڈ جے MALAN: ٹھیک ہے، یہاں. دیئے لئے آپ کا شکریہ یہاں کشیدگی اپ. ٹھیک ہے. تو چلو دیکھتے ہیں ہم نہیں اب اگر ہو سکے تو تھوڑا سا زیادہ یہ رسمی طور پر. تو ایک بار پھر، ہم صرف نے کیا کیا تھا ہم نے کیا کے طور پر بنیادی طور پر ایک ہی بات کہ پہلے ہفتے میں. بلکہ آخر کے مقابلے میں صرف ایک لکیری کے ساتھ ہم دکھایا گیا جس الگورتھم، پہلے ہی اس براہ راست لائن کے طور پر، جس کے تحت، ہم پر ایک اور دروازے پر ڈال دیا تو سکرین، تو جینیفر گے ، ممکنہ طور پر، دیکھو پڑا ہے ایک دروازے کے پیچھے. ہم دو دروازے ڈال دیا تو وہ ہو سکتا ہے دو دروازوں کے پیچھے دیکھنے کے لئے. 

اور اس طرح، اس لکیری نہیں تھا کے سائز کے درمیان تعلقات X-محور، کا کہنا ہے کہ، پر مسئلہ ہے، اور اس پر لیتا ہے وقت کی رقم Y پر حل. لیکن میں نے کرنے کے لئے کیا گیا تھا alluding تصویر اس سبز لکیر تھی. گرین جان بوجھ کر، کیونکہ یہ صرف بہتر محسوس کیا. نظریہ میں ہم یہ الگورتھم، کیا جب فون کتاب کے ساتھ، جب ہم نے یہ کیا تم لوگوں کو ایک دوسرے کے گنتی، اور کے ساتھ دوسری صورت میں، جب جینیفر صرف یہاں اپ نے کیا تھا، اس طرح تھا بنیادی طور پر بہتر ہے. یہ صرف دو مرتبہ روزہ کے طور پر نہیں تھا کیونکہ. اس سے روزہ کے طور پر بھی چار مرتبہ نہیں تھا. یہ کیا پر مکمل طور پر انحصار تھا ان پٹ کے سائز کے طور پر تھا، کتنے یہ بالآخر لیا اقدامات. 

اور ہم سب لے لیا ہے تاکہ اس سادہ خیال فون بک کے ساتھ حاصل کی جاچکی کے لئے، اسی طرح لاگو کیا جا سکتا کچھ اس طرح کرنے کے لئے. اور یہ اتفاق سے زیادہ ہو سکتا ہے آپ کو طاقت کے طور پر، کے طور پر جانا تقسیم اور فتح، تصور. نہیں ہم نے کیا کیا ہے کے برعکس، کورس کے، فون بک کے ساتھ. 

لیکن pseudocode، یاد، یہ تھا. تو ہم نے پھر سے یہ کرتے ہیں، لیکن یاد نہیں رکھا جائے کہ پہلے ہفتے، ہم سب کو کھڑے ہوئے اور اس کے بعد تم میں سے نصف نصف کی، بیٹھ گیا آپ بیٹھ گئے، آپ کی نصف بیٹھ گیا. یہ الگورتھم ایک میں لاگو کی گئی تھی کہ میں ایک دھوکہ دہی کے راستے سے تھوڑا سا، ہے، یہ مجھ سے صرف ایک، گنتی نہیں کیا گیا تھا بنیادی طور پر، زیادہ مؤثر طریقے سے. اس صورت میں، میں نے فائدہ دیا گیا تھا ایک ثانوی وسائل. کی ترتیب، ایک سے زیادہ CPUs، ایک سے زیادہ دماغ، میں ایک سے زیادہ ہوشیار لوگوں کمرے میں مجھ سے کچھ سے حاصل مدد کر رہے تھے کچھ لکیری کچھ کی طرف سے، لوگارتمی کچھ سبز سرخ. 

لیکن اس معاملے میں، جینیفر اکیلے کر سکتے ہیں بنیادی صلی اللہ علیہ وسلم کو بہتر بنانے کے اس کا پہلا الگورتھم کی کارکردگی کی طرف سے، ایک بار پھر، صرف ایک چھوٹی سی مشکل سوچ. اور اب، اس پر عملدرآمد کرنے کا وقت آتا ہے تو ان چیزوں کو، باہر figuring اگر آپ اس طرح لکھ سکتے ہیں کیا کوڈ کی لائنیں آپ کو انہیں دوبارہ دہرانے کی، اور کر سکتے ہیں پھر سے، اور پھر قسم کے ایک looping فیشن میں. آپ کے پاس نہیں جا رہے ہیں کیونکہ جینیفر طرح عیش و آرام کی، پر، سب سے پہلے میں نے کیا تھا صرف، لیکن کے پورے گچرچھی ہیں اور کہتے ہیں ہمم، یہ پہلی تعداد 4 ہے، مجھے ختم کرنے کے لئے تمام طریقہ کود ہیں. یہ تعداد بہت بڑی ہے، اگر ؤہ، مجھے منمانے واپس دو دوسرا عنصر ہے. تم اس کے بہت ہونے جا رہا ہے کہ تلاش کر لیں گے مشکل رسمی طور پر کیا ہم انسان بہت مناسب طور پر حاصل کی جاچکی کے لئے لے heuristics، لیکن ایک کمپیوٹر ہی ہے تم کرتے ہو اسے بتا کیا کرنے جا رہے. 

اب یہ بہت دلچسپ ہے مضمرات. یہ گراف طرح کی طرح کرنا ہے ضعف مغلوب، لیکن نوٹس، جہاں اس گراف میں براہ راست لائن ہے؟ لکیری گراف کہاں ہے ہم (ن) فون ہے؟ ٹھیک ہے، یہ سب سے نیچے کی طرف طرح کی ہے اس تصویر کے، ہے نا؟ ہم نے تمام ہم طرح کی ہے ہے X-محور اور باہر یکبر Y محور کیا کا احساس حاصل کرنے کے لئے کوشش کرنے کے لئے منحنی خطوط کے دیگر اقسام کی طرح نظر آتے. 

اور حساب کی تفصیلات اظہار آج اتنے سے کوئی فرق نہیں رکھا جائے بہت، لیکن کی ایک بہت ہے کہ متعلقہ سے کہیں بدتر ہیں کہ یلگوردمز لکیری ہے کہ کچھ. بے شک، cubed (ن) بہت برا لگ رہا ہے. 2 (ن) پر بہت برا لگ رہا ہے. مربع (ن) بہت برا لگ رہا ہے. اور ہم دیکھیں گے کہ کیا ان میں سے کچھ حقیقت میں آج ہو سکتا ہے. اور لاگ (ن) کے طور پر برا لگ رہا ہے، لیکن نہیں ہے (ن) سے بہتر (ن) کے لاگ ان بیس 2 ہے. لیکن آپ کو پتہ ہے، یہ بھی ہوتا زیادہ حیرت انگیز تو جینیفر، یا ہم تو، کہ پہلے ہفتے، کے ساتھ آیا تھا (ن) کی لاگ ان کی لاگ ہے کہ کچھ. 

تو دوسرے الفاظ میں، یہ مکمل ہے کرنے کے لئے ممکنہ حل کی حد مسائل، لیکن یہاں بھی نوٹس کیا ہونے جا رہا ہے. ان منحنی خطوط کے میں باہر زوم، تو جو مطلق ثابت کرنے جا رہی ہے اب کی سکرین پر اپنے پیاروں کا سب سے برا؟ تو (ن) cubed خوبصورت لگتا ہے وقت برا. لیکن ہم باہر زوم اور اس سے زیادہ کے دیکھو تو جا رہا ہے جو X اور Y محور، بالآخر غلبہ؟ تو یہ اصل میں ہے کہ 2 باہر کر دیتا ہے (ن)، اور آپ کو صرف کی طرف سے اس کو سمجھ کر سکتے ہیں کچھ تیزی سے بڑی میں plugging نمبرز، اور آپ دیکھیں گے کہ 2 سے (ن)، بے شک، بڑے زیادہ تیزی سے ہو جاتا ہے. ہم واقعی کرنے کے لئے، ایک 2 باہر زوم تو (ن) الگورتھم بالکل بیکار ہے. کیا میں یہ لے جا رہا ہے کا مطلب کے لئے وقت کی کافی تھوڑا سا کمپیوٹر کے ذریعے دودھ کا مٹکا کرنے کے لئے. 

لیکن آپ کو، خاص طور پر وقت کے ساتھ نظر آئیں گے مستقبل مسئلہ سیٹ کے ساتھ اور بھی حتمی منصوبوں، آپ کے ڈیٹا ہے سیٹ، ٹھیک ہے بڑی ہو جاتا ہے؟ یہاں تک کہ فیس بک کے پہلے ورژن میں، دوستوں کی تعداد، اور کے طور پر رجسٹرڈ صارفین کی تعداد، بڑی ملا آپ میں فون کی طرح کر سکتے ہیں ، لکیری تلاش کے ساتھ کچھ پر عمل درآمد یا ایک بہت سادہ چھنٹائی آج ہم دیکھیں گے کے طور پر الگورتھم،. آپ مشکل میں سوچ شروع کرنے کے لئے ہے اور ان مسائل کے بارے میں مشکل. اور مسائل مقامات کی اقسام کی طرح فیس بک، اور گوگل، اور مائیکروسافٹ، اور پر کام دوسروں یہ بالکل ہے سوالات کی بڑی ڈیٹا طرح کی ترتیب دیں تیزی سے ان دنوں. 

ٹھیک ہے. کہ دوسری میں جینیفر کی کامیابی تو الگورتھم، واضح طور سے، وہ حیرت انگیز تھا ساتھ ساتھ پہلی بار، لیکن چلو یہ قسمت کے طور پر لکھ تاکہ ہم اس نقطہ کر سکتے ہیں. دوسری صورت میں، وہ ایک لیوریجڈ ایک بار پھر دہرایا اور اس الگورتھم حاصل کی جاچکی کے لئے دوبارہ، لیکن اس نے لیا ایک ہم نے اجازت دی ہے کہ بعض مفروضے اس کی، لیکن وہ کچھ تفصیل سے استحصال وہ نہیں تھا کہ دوسری بار پہلی بار. کیا کون سا تھا؟ 

فہرست کے مطابق کیا گیا تھا. فہرست کے مطابق کیا گیا تھا تو جیسے ہی کے طور پر، ہم جینیفر کرنے کے قابل تھا کا دعوی ہے کہ بنیادی طور پر بہتر. 7 دروازے، جی ہاں،، کہ دلچسپ نہیں ہے لیکن ہم نے 7 لاکھ دروازے ہیں یہ فرض. (ن) کے لاگ ان یقینی طور پر ہو رہا ہے بہت، بہت کچھ انجام دینے کے لئے طویل مدت میں زیادہ تیزی سے. لیکن اس نے ہی پڑا دروازے اس کے لئے حل. اب، میں اس فعل کی آزادی لیا کمپیوٹر سکرین پر پیشگی یہاں، لیکن اس جینیفر فرض خود کو ایسا کرنے کے لئے تھا؟ فرض کریں کہ سوال میں دروازے نمائندگی ایک ڈیٹا بیس میں اعداد و شمار، یا فیس بک کے لئے رجسٹرڈ دوستوں، یا انٹرنیٹ پر کسی بھی ویب کے صفحات کہ مختلف ویب سائٹس کی ضرورت ہو سکتی ہے انڈیکس یا اس سے زیادہ تلاش کرنے کے لئے. 

آپ کو صرف ایک خام ڈیٹا تھا کہ فرض کریں سیٹ اور یہ آپ پر چھوڑ دیا گیا تھا، یا جینیفر کہ چھنٹائی کرنا؟ کہ، بلکہ، ہم جواب دینے کی ضرورت ہے کہ سوال یہ ہے، ٹھیک ہے، کتنا وقت جینیفر، یا یہاں تک کہ مجھ سے، لیا جائے گا پیشگی میں ان کی تعداد الگ الگ کرنے کیلئے اتنی وہ اس کا فائدہ اٹھا سکتا ہے؟ ٹھیک ہے؟ نہتارت، کورس کی ہے، کیونکہ یہ الگ الگ کرنے کیلئے مجھے کافی وقت لیتا ہے تو heck آپ کو پرواہ ہے کہ جو نمبرز، اتنی تیزی سے 50 کی طرح ایک بڑی تعداد حاصل کر سکتے ہیں، کے مقابلے میں جینیفر کی صورت میں، کے طور پر اگر ہم زیادہ کل وقت کی رقم ابیبھوت یہ پیشگی چیزوں چھانٹ رہا ہے کی طرف سے لیا؟ 

تو ہم نہیں کر سکتے ہیں دیکھتے ہیں یہاں تصویر پینٹ. میں نے ایک پورے گچرچھی زیادہ کشیدگی ہے گیندوں، میں مدد ملتی ہے کہ اگر یہاں برف توڑ. اور تم میں کوئی اعتراض نہیں کرے گا تو ہم سات رضاکارانہ کی ضرورت ہے - ٹھیک ہے، پر. واہ. تو ہم نے خرچ کرنے کی ضرورت نہیں ہے ڈیسک لیمپ پر، ایسا لگتا ہے. ٹھیک ہے. تو کس طرح سامنے دو آپ کے بارے میں. پیٹھ میں دو لوگ کس طرح کے بارے میں آپ. تو یہ چار ہے. کس طرح کے بارے میں آپ سامنے پانچ، چھ اور سات. ٹھیک وہاں. آپ کے دوست، آپ کو باہر کی طرف اشارہ ہے تو آپ کو انعام ملتا ہے. 

ٹھیک ہے. اپ چلو. اور کیوں ہم نے آپ کو نہیں ہے لوگ یہاں آو. میں آپ کو ہر ایک نمبر دینے کے لئے جا رہا ہوں. اور آگے بڑھو اور اپنے آپ کو بندوبست identically ہے کیا سکرین پر دکھائے جانے والے تاثر. 

[آوازیں INTERPOSING] 

ڈیوڈ جے MALAN: Oop، معاف کرنا. بگ. ٹھیک ہے. ٹھیک ہے، یہاں ہم چلے. نمبر پانچ. نمبر چھ. ایک، دو، تین، چار، پانچ، چھ، سات. اوہ، یہ عجیب ہے. 

اسپیکر 2: میں صرف ایک مل جائے گا -. 

ڈیوڈ جے MALAN: اچھا سودا. ٹھیک ہے. حصہ لینے کے لئے آپ کا شکریہ. 

[تالیاں] 

ٹھیک ہے. ٹھیک ہے. تو ہم نے، چار، دو، چھ ہے ایک، تین، سات، پانچ. ہم سات رضاکاروں تاکہ کامل یہاں چوڑائی کے برابر ہیں ہم کھیل رہے ہو کہ سرنی پہلے سے. اور میں نے وجوہات کی بنا پر سات کا انتخاب کیا کہ ہو جائے گا صرف تھوڑا سا میں آسان. اور میں سب سے پہلے تجویز کرنے جا رہا ہوں کہ ہم ان سات رضاکاروں حل. آپ، سب سے پہلے، چاہیں تو اگرچہ ہیلو. کہنا یہ ایک ہونے جا رہا ہے کے بعد سے عجیب کئی منٹ. اپنے آپ کو متعارف کرانے. 

GRACE: ہیلو، میں فضل ہوں. میں Leverett گھر میں sophomore ہوں. 

BRANSON: ہیلو. میں Branson ہوں. میں ویلڈ میں ایک freshman ہوں. 

GABE: ہیلو. میں Gabe ہوں. میں Cabot میں ایک جونیئر ہوں. 

نیل: میں نیل ہوں. میں Matthews میں ایک freshman ہوں. 

جیسن: میں جیسن ہوں. میں Greenough میں ایک freshman ہوں. 

MIKE: میں مائیک ہوں. میں Grays میں ایک freshman ہوں. 

JESS: میں جیس ہوں. میں Leverett میں ایک sophomore ہوں. 

ڈیوڈ جے MALAN: بہترین. ٹھیک ہے. ٹھیک ہے، ہمارا سب کا شکریہ اس طرح اب تک یہاں رضاکاروں. اور ہاتھ میں چیلنج اب جا رہی ہے ان لوگوں کی طرح ہو، لیکن پھر پر ہم ایک چھوٹی سی سوچنا پڑے کرنے کے لئے جا رہے ہیں کس طرح موثر انداز میں ہم واقعی اس کے بارے میں مشکل ان کے حل. تو سب سے پہلے اس کی کوشش کرتے ہیں. تم لوگوں کو ایک دوسرے کی تعداد میں دیکھ سکتے ہیں صرف کونے کے ارد گرد رکھ کر. آگے بڑھو اور چند سیکنڈ لگیں، اور ترتیب دیں سب سے چھوٹی سے اپنے آپ کو حق پر سب سے بڑا کرنے کے لئے چھوڑ دیا. جاؤ. 

ٹھیک ہے. اچھا ہے. یہ واقعی خوفناک تیز تھی. اب یہاں کوئی الگورتھم کیا تھا ان لوگوں کا اطلاق ہے؟ 

اسپیکر 1: سب سے زیادہ کم سے کم. 

ڈیوڈ جے MALAN: ٹھیک ہے. سب سے زیادہ کرنے کے لئے کم از واقعی کی طرح ہے مقصد، لیکن میں اس بات کا یقین نہیں ہوں واقعی ایک الگورتھم. سب سے زیادہ کرنے کے لئے کم از کم نہیں بتاتی مجھ سے کیا قدم بہ قدم. جی ہاں؟ 

اسپیکر: 1 [اشراوی] 

ڈیوڈ جے MALAN: ٹھیک ہے. تم سے ایک شخص چھوٹے دیکھ تو آپ کا نمبر، پھر میں منتقل ان میں سے حق. تاکہ اب، زیادہ ابیوینجک ہو رہا ہے مزید ایک الگورتھم کی طرح، کیونکہ آپ پھر، کہ یہ تو کہہ سکتے ہیں. تو ہم کسی قسم کے ہیں مشروط تعمیر. اور یہ لوگ جو چند کرنے کے لئے لگ رہا تھا اوقات، آپ میں سے کچھ تھوڑا سا منتقل کر دیا گیا ہے کیونکہ فاصلے کا. تو شاید کسی قسم کے بھی نہیں تھا ان کے دماغ میں کیا چل رہا looping. 

لیکن یہ رسمی طور پر کوشش کرتے ہیں. تم لوگوں کو واپس ری سیٹ کر سکتے ہیں تو اس نظام کے لئے. ہم یہ رسمی طور پر نہیں کر سکتے تو چلو دیکھتے ہیں تھوڑا سا، اور پھر سوال پوچھنا، صرف یہ کس طرح موثر ہے؟ کورس کے، ہم زیادہ آہستہ آہستہ ایسا کرتے ہیں، اس کے طور پر اچھا محسوس کرنے کے لئے جا رہا ہے ایک الگورتھم، لیکن دیکھتے ہیں ہم کر سکتے ہیں تو عین مطابق اقدامات پر اپنی انگلیاں ڈال دیا. 

تو تم دونوں لڑکوں اور دو چار ہوتے ہیں. یا آپ نے درست یا غلط حکم؟ ظاہر ہے غلط ہے. تو ہم نے تبدیل. اب میں ایک طرف منتقل کرنے کے لئے جا رہا ہوں یہاں اور چار چھ، کا کہنا ہے کہ. آپ درست یا غلط ہے؟ 

GABE: صحیح. 

ڈیوڈ جے MALAN: صحیح. چھ اور ایک؟ نہیں. ادل بدل. تاکہ دو سویپ ہے. چھ اور تین؟ نہیں. ادل بدل. چھ اور سات؟ اچھا لگ رہا ہے. سات اور پانچ؟ 

JESS: [اشراوی] 

ڈیوڈ جے MALAN: ٹھیک ہے، تبادلہ. اور حل. ٹھیک ہے. تو ظاہر ہے نہیں، ہے نا؟ تو زیادہ پر وہاں جا رہا تھا. لیکن، بے شک، یہ لوگ، یہاں تک کہ صرف instinctively. منتقل رکھا. انہوں نے صرف ایک بار، نہیں روکا وہ ایک مسئلہ درست. تو. بے شک، میں نے کیا کرنے جا رہا ہوں ایک ہی بات کرنا. میں ماضی پیٹھ کے حل کرنے کی ضرورت کرنے جا رہا ہوں اس مسئلہ کے آغاز پر، یا اس سرنی کے آغاز لوگوں کو ان کے بلا شروع کرتے ہیں. 

اور اب کیا کرنا چاہئے میری الگورتھم دوسری پاس پر ہو؟ 

اسپیکر 1: ایک ہی بات. 

ڈیوڈ جے MALAN: ایک ہی بات. اور یہ، میں نے صحیح، پسند کرنے کے لئے شروع کر رہا ہوں؟ تم اپنے آپ کو تلاش کر سکتے ہیں کر جیسے ہی کے طور پر ایک ہی بات بار بار، اس ، زیادہ سے زیادہ ایک الگورتھم کی طرح بننے اور کم انسانی سنتیں. 

تو اب، یہاں ہم ایک بار پھر جانا. دو اور چار؟ نمبر چار اور ایک؟ آہ، کچھ واقعی وہاں تھا کیا جا کرنے کے لئے اب بھی کام کرتے ہیں. کے لئے اور تین؟ اچھا ہے. چار اور چھ؟ چھ اور پانچ؟ چھ اور سات؟ ٹھیک ہے، اب، کیا. ٹھیک ہے، نہیں. میں واپس جانا ہے. 

تو اب، ایک بار پھر، ہم یہ کر رہے ہیں تھوڑا اور جان بوجھ کر. اور اب، صرف ایک دماغ ہے اس الگورتھم عمل. ایک سی پی یو، اگر آپ. اور واضح طور سے، کہ صرف وسائل کی ہے ہم تک رسائی حاصل کرنے کے لئے جا رہے ہیں. اور ایک بار ہم نے ایک کی بورڈ پر واپس جانا ہے اور ہمارے میں سی کچھ اس طرح ہے رفع فضلات، ہم صرف ایک پروگرام لکھ رہے ہیں کہ ایک وقت میں ایک بات کر سکتے ہیں. ایک لمحے پہلے یہ لوگ، جبکہ، ہم لیوریجڈ ان کی مجموعی brainpower تم لوگوں کو ہفتے صفر میں کیا تھا کی طرح. لہذا یہ کر رکھتے ہیں. 

دو اور ایک. دو اور تین. تین اور چار. چار اور پانچ. پانچ اور چھ. چھ اور سات. کیا؟ تو میں ہوں، لیکن مجھے کھیلنے دو شیطان کی وکالت. کرو میں، کمپیوٹر کی قسم جو صرف اس سرنی کے ذریعے ایک پاس کر دیا لوگوں، میرا ہو گیا ہے؟ 

اسپیکر 1: نہیں. 

ڈیوڈ جے MALAN: تو کیوں؟ اگر میں کرنے کے لئے کرنا پڑے گا میں کیا کر رہا ہوں کہ فیصلہ کن نتیجہ اخذ؟ شاید ایک اور پاس. ٹھیک ہے؟ کیونکہ میں اس سابقہ ​​جانتے تمام پاس میں نے ایک غلطی درست ہے. اور اس کا مطلب ہے، ہو سکتا ہے ابھی تک ایک اور غلطی میں کو درست کرنے کی ضرورت ہے. تو میں صرف rewinding کی طرف سے اس بات کا یقین ہو، اور کر سکتے ہیں پھر، کی جانچ پڑتال ایک سے دو، دو اور تین، تین اور چار، چار اور پانچ، پانچ اور چھ، چھ اور سات. ٹھیک ہے، اب میں کوئی کام نہیں کیا. 

میں یقینی طور پر میں نہیں کیا یاد ہے کہ کر سکتے ہیں ، ایک متغیر کی طرح کچھ کے ساتھ کام ایک INT پسند کرتے ہیں. یہ سویپ کال کریں، اور میں نے ایک بار سویپ 0 ہے تو یہاں ملتا ہے، اور یہ اس وقت، 0 سے شروع میں صرف جاری رکھنے کے لئے پاگل ہو جائے گا آگے پیچھے، پھر سے جانچ پڑتال، اور پھر سے، اور میں دوبارہ، ہے نا؟ آپ کو کچھ میں پھنس جاتے ہیں کیونکہ لامحدود لوپ کی قسم. 0 سویپ، ہے تو جیسے ہی ہم اس کا دعوی کر سکتے ہیں الگورتھم یقینا مکمل ہے. 

اب، اس پر ایک نام رکھ دیں. میں صرف ہم تجویز ہے کہ الگورتھم بلبلا کہا جاتا ہے نافذ معنوں میں اس طرح کے طور پر جانا جاتا طرح، کہ بڑی قسم کے ہیں کہ نمبرز اپ سب سے اوپر بلبلا ان کا راستہ، یا نمبروں کی سرنی کے آخر تک. لیکن یہ الگورتھم کس طرح موثر تھا؟ میں جسمانی طور پر کتنے اقدامات کی کیا ضرورت تھی ان الگ الگ کرنے کیلئے، مثال کے طور پر لینا سات انسانوں؟ 

چار سے پانچ؟ ٹھیک ہے، بہت سے آخر میں ہے جواب ہونے جا رہا. لیکن پھر بھی، تعداد متعین اتنی دلچسپ نہیں ہے. اس (ن) کے طور پر وسیع ہیں. میں یہاں لوگوں کو (ن) کے، اور وہ تھا تو اگر میں بے ترتیب ترتیب میں، قسم کے تھے، کہ اصل ترتیب میں، شروع. ٹھیک ہے، کس طرح بہت سے اقدامات میں تھا سب سے پہلے پاس پر لینے کے لئے؟ یہ، ایک، دو، تین، چار، پانچ تھا تو چھ، اور وہ سات افراد ہیں، کہ، چھ سات ہے -، (ن) ہے تاکہ مائنس ایک پہلی بار قدم. 

اب، کس طرح بہت سے اقدامات میں تھا میں rewound جب لینے کے لئے؟ ٹھیک ہے، ہم اصل میں دوگنا کر سکتے ہیں کہ اگر ہم واقعی کرنا چاہتا تھا، لیکن اب کے لئے، میں ہوں صرف،، ٹھیک کہنے والا ایک اور ن مائنس 1. تو ن مائنس 1 حاصل کرنے کے لئے جا رہی ہے کا ٹریک رکھنے کے لئے پریشان کن ہے، تو چلو صرف تھوڑا سا گھیر لینا. تو 2n اقدامات. اس لئے 14 اقدامات، دے یا لے. 

میں نے کتنی بار لے گئے ایک قدم اگلی بار؟ ٹھیک ہے، یہ 3n ہے. واقعی. اور اب، بدترین صورت میں، کے لئے مثال کے طور پر، کتنی بار میں ہوگا ، آگے پیچھے، آگے پیچھے چلی گئی گماگمن، اس الگورتھم عمل ہر ایک کے پاس پر لوگوں کو، موٹے طور پر؟ یہ دراصل حق، مربع ن ہے؟ 

بدترین صورت میں، آپ کو قسم کے کر سکتے ہیں intuitively اس کے بارے میں سوچنے کی، یہ تھوڑا سا لگ سکتے ہیں اگرچہ رکنیت ڈوبنے کے وقت کا تھوڑا سا بدترین صورت میں، کیا ہوگا ان سات افراد میں، کی طرح دیکھا ہے انتظام کی شرائط ان کی تعداد کی وجہ سے؟ مکمل طور پر پیچھے کی طرف، صحیح؟ اور بس، اس کے انکرن کرنے کے لئے آپ کا نام ایک بار پھر کیا تھا؟ 

MIKE: مائک. 

ڈیوڈ جے MALAN: مائیک؟ ٹھیک ہے، مائیک، تم صرف مجھ پر شامل ہو سکتے ہیں یہاں صرف ایک سیکنڈ کے لئے؟ اصل میں، نہیں. معذرت مائک، چلو ماضی. تمہارا نام کیا ہے دوبارہ؟ 

نیل: نیل. 

ڈیوڈ جے MALAN: نیل. ٹھیک ہے، نیل، آپ کے ساتھ آئے مجھے، آپ کو برا نہ لگے تو. تو میں صرف کے لئے تجویز کرنے جا رہا ہوں سادگی، کہ نیل ان میں ہے سب سے زیادہ ممکن کیس. لیکن میں عملدرآمد کس طرح یاد میری الگورتھم. میں موازنہ کا موازنہ، موازنہ، رہا ہوں اوہ، موازنہ، موازنہ. اب یہ لوگ باہر ہیں حکم کی، تو میں نے طے کر لو. تو کیا تم لوگ تبادلہ. لیکن کتنی دور، اب غور نیل جانا ہے؟ یہ موٹے طور پر (ن) ہے. تم جانتے ہو، یہ اصل میں (ن) نہیں ہے. اس طرح، (ن) مائنس 1 ہے، لیکن میں ہو رہی ہوں چھوٹی سی کے پریشان رکھ ٹریک نمبر، تو صرف اس کے (ن) کو کال کرتے ہیں. 

نیل زیادہ سے زیادہ ہر ایک قدم چلتا ہے تو اگر وقت، اور نیل ایک قدم منتقل کرنے کے لئے، مجھے یہ واقعی تکاؤ پاس بنانا ہے آگے پیچھے، یہ تقریبا ہے یہ کر رہے، (ن) کے اقدامات، (ن) کے اوقات کی کل، اس سے مجھے لے جا رہا ہے کیونکہ کئی مراحل نیل تمام حاصل کرنے کے لئے ہے کہ وہ تعلق رکھتا ہے جہاں کا راستہ. ہر کسی کے چھوڑ دو تم لوگوں کو تو سب کے ساتھ ساتھ غلط کا حکم دیا گیا. 

تو بلبلا کی طرح ن مربع فون ہیں. اس الگورتھم کی رننگ ٹائم، اس الگورتھم کی کارکردگی، اس الگورتھم کی کارکردگی، ہم صرف مزید وضاحت کرے گا ن مربع عام طور پر کے طور پر. میں کر سکتا جس کی وجہ سے، اچھا ہے آٹھ افراد، نو کے ساتھ ایک ہی مثال کے طور پر لوگوں کو، ایک ملین افراد، اور اس جواب تبدیل کرنے کے لئے نہیں جا رہا ہے. 

تم لوگوں کو کوئی اعتراض نہیں کرے گا تو چلو تم نے شروع کیا ہے جہاں آپ کو دوبارہ ترتیب. اور دو کی دو دیگر طریقوں کی کوشش کریں اور ہم بنیادی طور پر ایسا نہیں کر سکتے تو دیکھ اس سے بہتر. اس وقت تو میں نے تجویز پیش کرنے جا رہا ہوں مختلف الگورتھم کی ایک قسم. یہی وجہ ہے کہ آخری بار ہم میں سے بہت ہوشیار تھا اور تم لوگوں کو ہے درست تھے صرف قسم کی حق instincts pairwise گماگمن کی. لیکن مجھے واقعی میں اس نقطہ نظر کرنا چاہتے تھے اگر صرف، اور میرا مقصد منتقل کرنے کے لئے ہے چھوٹی سی تعداد کے سب اس طرح، اور کہ بڑی تعداد کے تمام دھکا جس طرح، کیوں میں صرف میں ایسا نہ کرو سب سے زیادہ ممکن راستہ بولی اور دیکھ تو میں ایک کیا تھا کے مقابلے میں بہتر کر سکتے ہیں کافی پیچیدہ الگورتھم؟ 

تو دیکھتے ہیں. چار ایک خوبصورت چھوٹا سا نمبر ہے، لہذا میں ہوں وہاں لمحے آپ کو چھوڑ کر جا. ؤہ، نمبر دو اس سے بھی بہتر ہے. تو تم صرف اگے قدم کر سکتے ہیں ایک لمحے کے لئے؟ یہ اس وقت میری سب سے چھوٹی تعداد ہے امیدوار، اور میں یاد کرنے کے لئے جا رہا ہوں کہ ایک متغیر، پسند، کے ساتھ. لیکن میں کی جانچ پڑتال رکھنے کے لئے جا رہا ہوں. جس کا کوئی ہے تعداد چھوٹی ہے؟ چھ، نہیں. اوہ، پھر نیل ہے. 

تو میں نے آپ کو واپس دھکا کرنے جا رہا ہوں ترتیب دیں conceptually کی. نیل آگے آئیں گے. اور اب، میں متغیر استعمال کر رہا ہوں کہ سب سے چھوٹی ہے جو کی یاد رکھیں تعداد پر مشتمل کرنے کے لئے اپ ڈیٹ کیا جاتا نیل کے مقام. ٹھیک ہے، چلو دیکھتے ہیں. تین، سات، پانچ. ٹھیک ہے، میں نیل سب سے چھوٹا تھا. سادہ ترین چیز کیا ہے میرے لئے اب کیا کرنا ہے؟ میں صرف کی طرف سے اپنا وقت برباد کرنے کے لئے نہیں جا رہا ہوں بائیں نیل ایک جگہ bubbling. کیوں میں صرف نیل میں نہ ڈالو جہاں انہوں نے تعلق رکھتا ہے، جس میں جہاں کورس کی ہے؟ 

شروع میں تمام راستہ. نیل تو، میرے ساتھ چلو. اور تمہارا نام ایک بار پھر کیا تھا؟ 

GRACE: فضل. 

ڈیوڈ جے MALAN: فضل. ٹھیک ہے. فضل تو، بدقسمتی سے، تم راہ میں کی قسم. تو کس طرح ہم اس مسئلے کو حل کر سکتا ہوں؟ ٹھیک ہے؟ یہ ایک سرنی ہے، تو ہے صرف سات مقامات. روب کے ساتھ، اس کو یاد ہے، ہم کے بارے میں بات عمر قرار دیا، اور ہم صرف ایک تھا عمر کے تبدوست نمبر؟ یہاں بھی یہی خیال ہے. ہم صرف ints کی ایک محدود تعداد میں ہے. فضل ہمارے میں قسم کی ہے جس طرح، ہم ایسا کس طرح ٹھیک کروں؟ 

آسان ترین طریقہ، کی طرح ہے گریس، معاف کرنا. تم پر جانے کے لئے کرنے کے لئے جا رہے ہیں تو ہم نے کمرے وہاں کر سکتے ہیں. اب، تم ہو سکتا ہے، اس کے بارے میں لگتا ہے کہ اگر ہم صرف مسئلہ بھی بدتر بنا دیا. اور شاید ہم نے کیا کیا کیونکہ اگر فضل صحیح جگہ میں تھے؟ لیکن ہم وہ وجہ سے، نہیں ہے دوسری صورت میں، وہ ہوتا اگے کھڑے بجائے اس وقت نیل، ہے نا؟ ہم نے پہلے ہی اس کی تعداد میں باہر کی جانچ پڑتال کی. 

ٹھیک ہے. تو اب، نیل صحیح جگہ میں ہے، اور میں ایک معمولی اصلاح کر سکتے ہیں. اگلے منٹ کے لئے، میں نے نظر انداز کرنے جا رہا ہوں تاکہ نہ ایک دوسرے کے ساتھ نیل تمام، اس کا وقت برباد، یا اتفاقی طور پر غلط جگہ پر اس سے تبادلہ. تو اب، میں کس طرح اگلے حاصل کر سکتا ہوں سب سے چھوٹی ہے کہ عنصر؟ دو. تو یہی وجہ ہے کہ ایک خوبصورت اچھی تعداد میں ہے آپ آگے قدم اور کرنا چاہتا ہوں میں تمہیں یاد کروں گا. چھ، اچھا نہیں. چار، تین، سات، پانچ، اچھا نہیں. تو کیا تم مجھ سے منتقل کرتے ہیں آپ صحیح جگہ. اور ہم صرف اس وقت خوش ہو گیا. 

اب، میں نے ان کو نظر انداز کرنے جا رہا ہوں دو لوگ، اور اب ایک اور کرتے ہیں اس سے گزر. چھ، کہ ایک بہت چھوٹی سی تعداد. اگے چلو. اوہ، معاف کرنا. گریس کی تعداد، بہتر ہے تاکہ مستقبل کے حوالے سے پر قدم. چار. معذرت، فضل. پھر واپس چلے جاؤ. نمبر تین بہتر ہے. سات. پانچ. اور اب ایک بار پھر آپ کا نام کیا ہے؟ 

جیسن: جیسن. 

ڈیوڈ جے MALAN: جیسن. تو جیسن اب سب سے چھوٹی ہے عنصر میں نے منتخب کیا ہے. وہ جانے کے لئے کہاں جا رہا ہے؟ تو جہاں چھ ہے. اور تمہارا نام دوبارہ ہے؟ 

GABE: Gabe. 

ڈیوڈ جے MALAN: Gabe. Gabe راہ میں ہے. کرنے کے لئے سب سے آسان چیز کیا ہے؟ ان دو لڑکوں کو ادل بدل اور جاری رکھیں. تو اب چلو دیکھتے ہیں. کون چھوٹا ہے؟ چار. مجھے دھوکہ میں سے صرف قسم کے ہیں. پانچ سب سے چھوٹی ہونے جا رہا ہے. ، آپ کو قدم کرنا چاہتے ہیں تو میں نے اگلے تلاش مستقبل کے حوالے سے، میں کے ساتھ کیا کرنا ہے Gabe کے ساتھ ان لوگوں کو،؟ دوبارہ ادل بدل. تو اب، اب بھی تھوڑا سا حکم سے باہر. میں Gabe تو، سب سے چھوٹی پائے میں نے اسے باہر پاپ تم لوگوں سے زیادہ منتقل. اور کیا. 

تو اس کا جواب ایک ہی ہے. آخر نتیجہ ایک ہی ہے. ان دونوں میں سے کس الگورتھم بہتر ہے؟ دوسرا، میں نے سنا. کیوں؟ 

اسپیکر 3: یہ اقدامات [اشراوی] ن ہے. 

ڈیوڈ جے MALAN: یہ زیادہ سے زیادہ (ن) کے اقدامات پر ہے. دلچسپ. تو یہ اگرچہ ہے؟ تو مجھے کس طرح پتہ چلا سب سے چھوٹا عنصر؟ کتنے اقدامات میں لینے کی کیا ضرورت تھی سب سے چھوٹا عنصر تلاش کریں؟ میں نے ایک پورے راستے نظر تھا آخر میں، ہے نا؟ کہ بدترین صورت میں، کیا کیونکہ نیل یہاں تھے تو کیا ہوگا؟ تو صرف سب سے چھوٹی عنصر کی تلاش مجھے ن اقدامات، یا ن مائنس 1 لیتا ہے. لیکن، ٹھیک ہے. تو نیل طے کر لو. ، ایک منٹ یا اس سے پہلے یاد رکھیں کہ. 

لیکن کس طرح میں اگلے ملا سب سے چھوٹا عنصر؟ یہ ن مائنس 1، یا ن مائنس واقعی 2، ہے اقدامات کی تعداد سے. تو ٹھیک ہے. تو میں نے 2 مائنس ن تھا. ٹھیک ہے. تاکہ تھوڑا بہتر لگ رہا ہے. ٹھیک ہے. اگلی بار کتنے قدم نمبر تین تلاش کرنے کے لئے؟ تو ن مائنس 4. تو یہ ایک کم کم ہے ہر iteration پر قدم. تو یہ درست، بہتر محسوس ہوتا ہے؟ آخری بار تو، موٹے طور پر (ن) کے اوقات ن تھا اس وقت یہ ن مائنس 1، پلس مائنس ن ہے 2، کے علاوہ ن مائنس 3، پلس (ن) مائنس 4، ڈوٹ، ڈوٹ، ڈوٹ. لیکن آپ نے اپنے ہائی اسکول سے یاد ہو درسی کتب، تھوڑا دھوکے باز فارمولوں ہے کہ پشت پر شیٹ، اگر آپ کو اعداد کی اس سیریز کو شامل اقدامات کی کل تعداد کیا ہے میں یہاں لے کہ ہونے جا رہا؟ 

یہ ان میں سے ایک، پسند، ن مائنس ہے 1، 2 سے تقسیم اوقات ن. تو میں ھیںچو کر سکتے ہیں اگر مجھے دیکھنے دو صرف ایک لمحے کے لئے اس اپ. اور پھر، میں پکڑ دھکڑ کی طرح کچھ ہوں تعداد صرف، ہماری زندگی آسان رکھنے کے لئے لیکن مجھے یاد ہے، یہ تو کچھ اس طرح ہے پھر میں، ن مائنس 1 چیز ن مائنس 2، پھر (ن) مائنس 3، یہ ​​تقریبا ہے 2 سے زیادہ کچھ اس طرح، اور اگر میں نے یہ باہر ضرب، کہ ہے اصل میں (ن) مربع. وہ بھی اچھا نہیں لگ رہا ہے. 2 سے زیادہ ن مائنس ن. 

لیکن یہاں بات ہے. کمپیوٹر سائنس، مسائل جب میں (ن) جب دلچسپ حاصل کرنے کے لئے شروع ہوتا ہے واقعی میں بڑی ہو جاتا ہے. اور (ن) نے واقعی بڑے ہو جاتا ہے جب، جس ان اقدار سب پر غلبہ حاصل کرنے جا رہی ہے دوسروں کی؟ یہ درست ہے، مربع (ن) کی طرح ہے؟ جی ہاں، 2 کی طرف سے تقسیم بہت اچھا ہے. لیکن آپ کو اربوں روپے کے بارے میں بات کر رہے ہیں تو اعداد و شمار کے ٹکڑے ٹکڑے کر، یا کھربوں کی اعداد و شمار کے ٹکڑے ٹکڑے کر، ٹھیک ہے، تو آپ دگنا تیز ہو. لیکن جو واقعی ہے کہ بڑی تعداد اگر پرواہ کرتا ہے اس عنصر ملتا ہے کیا ہے اگر بڑا اور بڑا. اور یقینا، اس کے زیادہ کرتا ہے اس آدمی کے مقابلے میں ایک فرق ہے. تم لوگوں کو ٹھیک کہہ رہے ہو تو، اگرچہ دوسری الگورتھم، ہم اسے فون کروں گا انتخاب ترتیب دیں،، حقیقی دنیا میں، ہے تھوڑا سا تیز تر ممکنہ طور پر، میں ہوں کیونکہ لینے کے کم اور کم ہر وقت اقدامات. 

یہ واقعی بنیادی تیز نہیں ہے. کیونکہ ہم واقعی اس کے لئے اس سے باہر کھیلتے ہیں تو کے آخر میں (ن) کی بڑی اقدار، دن، بڑے کافی (ن) کے لیے، یہ اب بھی ہے بہت سست محسوس کرنے کے لئے جا رہے ہیں. ٹھیک ہے، مجھے ایک لے جانے دو کہ میں گزشتہ پاس. لہذا میں نے فون کیا ہے انتخاب ترتیب دیں. تم لوگوں کو اپنے آپ کو بحال کر سکتے ہیں ایک آخری بار؟ اور یہ آخری صورت میں، میں جا رہا ہوں کچھ تجویز اندراج کی طرح سے ملاقات کی. اضافے کی طرح کیا جا رہا ہے، conceptually، تھوڑا مختلف. 

آگے پیچھے جا کر اور بجائے سب سے چھوٹا عنصر کو منتخب، میں ہوں صرف ان میں سے ہر ایک سے نمٹنے کے لئے جا میں ان کا سامنا، اور ڈالنے کے طور پر لوگ انہیں ان کے صحیح جگہ میں. تو میں صرف، فضل کے ساتھ شروع کرنے کے لئے جا رہا ہوں اور میں نے وہ نمبر چار ہے کہ دیکھتے ہیں. نمبر چار کہاں سے تعلق ہے؟ میں نے کچھ بھی چھںٹائی شروع نہیں کیا ہے تو فضل حق وہاں رہنے کے لئے ہو جاتا ہے. آپ کر سکتا ہے تو اور اب میں، کا دعوی کرنے جا رہا ہوں یہ، اپنے دائیں کرنے کے لئے ایک قدم میرے مطابق فہرست، یہ میرا ہے ناچھانٹا ہوا باقی فہرست. تو اب میں، اگلے آگے بڑھنے کے لئے جا رہا ہوں اور تمہارا نام کیا ہے دوبارہ؟ 

BRANSON: Branson. 

ڈیوڈ جے MALAN: Branson. تو Branson نمبر دو ہے. تو میں تمہیں لے جا رہا ہوں ایک لمحے کے لئے باہر. اور اب، تم کہاں سے تعلق رکھتے ہو اس صف میں؟ تو فضل کے دائیں جانب. تو ایک بار پھر، ہم بنانے کی طرح ہیں گریس یہاں بہت کام کرتے ہیں. ہم آپ کو کہاں رکھنی چاہئیے؟ تو ہم آپ کو سلائڈ کرنے جا رہے ہیں چھوڑ دیا، اور وہاں Branson ڈالیں. لیکن اب میں نے کا دعوی ہے کہ آپ لوگ کیا کر رہے ہیں. لیکن نوٹس، میں اضافی جگہ کا استعمال نہیں کر رہا ہوں. یہ اب بھی 2 عناصر ہے یہاں، یہاں 5. کل سرنی سائز 7 ہے، لہذا میں ہوں ٹھیک ہے، دھوکہ نہیں؟ 

تو اب ہم یہاں Gabe کے ساتھ ہے، نمبر چھ، تم کہاں کے ہو؟ تم پھر سے خوش ہو گیا. تو کیا تم ابھی وہاں رہنے کے لئے ملتا ہے. صرف صحیح کرنے کے لئے ایک معمولی قدم صرف آپ کو حل کر رہے ہیں یہ واضح کرنے کے لئے. اور اب ہم ایک بار پھر نمبر نیل ہے ایک، تم کہاں جاتے ہو؟ ہم اس کو دیکھنے کے لئے شروع کریں گے اور کہاں اب ہے اگرچہ سب سے پہلے پر اس الگورتھم، نظر، خوبصورت سمارٹ محسوس ہوتا ہے، دیکھتے ہیں ہونے کے بارے میں کیا ہے. آپ آگے قدم ہو جاتے ہیں تو. 

ہم کہاں نیل ڈال کرنا چاہتے ہیں؟ تو ظاہر ہے یہاں، تو کس طرح ہم وہاں نیل حاصل کروں؟ یہ قدم بہ قدم کر چلو. تمہیں جانے کی ضرورت ہے جہاں Gabe،؟ جی ہاں، تو، ایک بڑا قدم اٹھانے یا دو نصف اقدامات کرنے کے لئے وہاں ایک قدم. تم جاؤ جہاں فضل،؟ اچھا ہے. ایک اور قدم ہے. اور آخر میں، Branson؟ ایک اور قدم. اور اب ہم جگہ میں نیل ڈال کر سکتے ہیں. 

تو اب، یہ منطق جاری. ہم نیل منتقل نہیں کر رہے ہیں اگرچہ سے زیادہ، اور میں، اور، اس سے ڈال وہ بدترین صورت میں، کہاں جاتا ہے، ہم سامنا ہو سکتا ہے اگلے تعداد میں کر سکتے تھے نمبر ہونا، کا کہنا ہے کہ ایک بڑی تعداد موجود تھی صفر، تو ہم سب کو منتقل کرنے کے لئے جا رہے ہیں یہ لوگ. ایک بڑی تعداد، منفی ہے کہ مان لیں ایک، تو پھر ہم میں منتقل کرنا ہے ان لوگوں کے تمام. تو ہم واقعی flipping کے صرف اچھے ہو ہم اس طرح کی ہے کہ مسئلہ کے ارد گرد، کی طرف سے اخراجات میں منتقل انتخاب کے عمل اتنی اندراج تم لوگوں کو صرف تھا کہ اس طرح کے عمل کو، موٹے طور پر (ن) مائنس کچھ منتقل کرنے کے لئے اقدامات کی تعداد. اور اقدامات کی یہ تعداد صرف جا رہا ہے میں زیادہ تعداد کو منتخب کریں کے طور پر اضافہ کرنے کے لئے، میں تم لوگوں کو shoving رکھنے کے لئے ہے تو واپس، اور واپس، اور واپس. 

تو دکھ کی بات یہ ہے کہ اب ان میں سے ہے یلگوردمز مربع ن کر رہے ہیں. چلو آگے بڑھو اور ان کا شکریہ ادا کرنے کے لئے لڑکوں، اور ان تھوڑا دیکھ مختلف طریقے سے. بہت اچھا کیا. 

[تالیاں] 

ٹھیک ہے. تم وہاں جاؤ. کے لئے شکریہ - 

BRANSON: [اشراوی] نمبرز رکھنا. 

ڈیوڈ جے MALAN: نہیں، تم کر سکتے ہو اس کے ساتھ ساتھ تعداد میں رکھیں. ٹھیک ہے. اچھی طرح سے کیا. ٹھیک ہے. تو کیا اب ہم مختصر نہیں کر سکتے تو دیکھتے ہیں زیادہ تیزی سے، اور زیادہ ضعف، بالکل وہی جو صرف ہوا یہاں کے طور پر مندرجہ ذیل ہے. میں آگے جانے کے لئے جا رہا ہوں اور فائر فاکس ھیںچو. ہم نے اس مظاہرے سے منسلک کریں گے کورس کی ویب سائٹ پر. جاوا کام کر رہے ہیں کرنے کے لئے تھوڑا سا پریشان کن ہے کچھ براؤزرز ان دنوں میں. آپ کے گھر میں اس کے ساتھ کھیلتے ہیں اگر ایسا ہے تو اگر آپ فائر فاکس استعمال کرنے کے لئے ضرورت ہو سکتی ہے کا احساس یہ کام حاصل کرنے کے لئے. اور کیا میں اس کے ساتھ کیا کرنے جا رہا ہوں مظاہرے میں مندرجہ ذیل ہے. 

کے نیچے دیے گئے، میں کے پورے گچرچھی ہے آغاز اور ایک مینو کے اختیارات بھی شامل ہے، بٹن کو روکنے کے. اس کے علاوہ، ایک ایک طرف کے طور پر، ایک نہیں ہے ان پروگراموں میں بگ، آپ جس کے تحت اصل آغاز دیکھتے ہیں یا نہیں روک سکتے آپ کمانڈ یا آلٹ بٹن منعقد جب تک پلس اور زوم میں، جس میں دلچسپ آپ کو زیادہ کے بٹن ظاہر کرتا ہے. تم کھیلو تو بس FYI اس کے ساتھ گھر میں. اب میں صرف ایک میں شروع کلک کرنے کے لئے جا رہا ہوں لمحے کی تاخیر کی وضاحت کے بعد، یہاں 200 milliseconds، کی طرح تو ہم کیا ہوتا ہے دیکھ سکتے ہیں. 

تو میں نے یہ تصور ہے کہ دعوی پہلی الگورتھم کے یہ لوگ بلبلا ترتیب دیں، جس کے تحت، کیا ہم لوگوں کو جوڑے وار تبدیل. اس تصور کی کلید بصیرت یہ ہے کہ سلاخوں کے کی اونچائی تعداد کے سائز کی نمائندگی کرتا ہے. طویل بار تو، بڑی تعداد. کم بار، تعداد چھوٹے. آپ کو نوٹس تو، ہم کے ذریعے جا رہے ہیں اس الگورتھم کے پہلے iteration، تا کہ، بڑے اور چھوٹے کی تعداد گماگمن چھوٹی سی تعداد پہلا اور آتا ہے بڑی تعداد درست کرنے کے لئے جاتا ہے. 

اور جیسے ہی ہم سرنی کے آخر تک حاصل کرنے کے طور پر سات سے زیادہ بہت سے اعداد کی، ہم ہیں شروع کرنے کے لئے واپس جانے کے لئے جا رہے ہیں. اور یہ اندازہ. دور بائیں طرف، اس چھوٹے آدمی جا رہا ہے طرف تبادلہ، اور اس پر عمل دوہراتا. اب اس تصور کو فوری طور پر ہو جاتا ہے بورنگ، تو مجھے آگے بڑھو اور کو روک دیتے ہیں یہ، بہت تاخیر کچھ تبدیل تیزی سے صرف، اب کے لئے ایک احساس حاصل کرنے کے لئے اس الگورتھم. 

میں اسے sped ہے تو، اگرچہ یہ ہے خرید، میری پروسیسر اپ گریڈنگ کی طرح ایک نئے کمپیوٹر. میں بنیادی طور پر تبدیل کر دیا گیا نہیں کیا ہے میری الگورتھم، لیکن آپ بے شک زیادہ دیکھ سکتے ہیں واضح طور پر انسانوں کے ساتھ مقابلے میں، جو کہ بڑا نمبرز، چوٹی پر چڑھ bubbling کر رہے ہیں اور چھوٹے تعداد bubbling کر رہے ہیں نیچے نیچے. اور اب اس بات کو یہاں حل. اور ایک ایک طرف کے طور پر، چوکوں میں، وہاں ہے وہاں صرف کچھ منیمی ، آپ کس طرح بہت سے موازنہ شمار میں مدد یا کتنے سویپ ہے اصل میں کیا گیا. 

ٹھیک ہے، میں سے ایک کی کوشش کرنے دو دوسروں کو ہم نے دیکھا. مجھے یہاں بلبلا ترتیب دیں پر کلک کرتے ہیں، اور آپ کے وزٹرز کا انتخاب کرتے ہیں، اور اس پورے ویب صفحہ ایک چھوٹی سی چھوٹی گاڑی ہے. کی خطرے کو قبول کرتے ہیں اور اسے دوبارہ چلائیں. وہاں ہم چلے. لہذا انتخاب طرح کرتے ہیں. مجھے نہیں معلوم کیوں مینو وہاں ظاہر ہوتا ہے. کہ ٹھیک کرنے کے لئے میں زوم کی دو بگ، 50 کرنے کے لئے اس میں تبدیلی. آہ، اصل میں کرتے ہیں زیادہ تیزی ہے. پانچ milliseconds یا اس کے، اور شروع کریں. 

لہذا اس طرح کے انتخاب ہے. تو پھر، کیا ہم کے بارے میں سوچنا یہاں انسانوں اپ کے ساتھ کیا تھا. ہم سرنی کے ذریعے چلا گیا اور منتخب ایک بار پھر سب سے چھوٹی عنصر، اور پھر سے، اور میں دوبارہ. اب میں اب بھی بہت برا تھا کا دعوی ہے کہ. یہ ابھی بھی مربع ن کیا گیا تھا،، دے یا لے لیکن یہ تھوڑا سا، حقیقی دنیا میں تھا، تیزی سے، میں یقینا لے رہا تھا کیونکہ ہر وقت کے مراحل قدرے کم. لیکن ہم صرف اس صورت میں کیا بات کر رہے ہیں؟ یہاں شاید 40 یا اس سلاخوں؟ ہم نے 40 ملین بات نہیں کر رہے. تو یہ مکمل طور پر مجھ پر واضح نہیں ہے کہ یقینا ایک اہم فائدہ تھا. 

اب مجھے واپس جانا اور ہمارے کرنے کے لئے تبدیل کر دو کو منتخب کیا گیا تھا جس میں تیسری الگورتھم، اندراج ترتیب دیں. اور اب یہ واقعی چھوٹی گاڑی ہے کیونکہ مینو واقعی وہاں نہیں ہونا چاہئے. تو اب ہم یہاں واپس سکرال گے اور اس الگورتھم شروع. Whoop، شروع کریں اور کو روکنے کے. تو یہ ایک قسم کا ایک خوبصورت نمونہ ہے یہ کرنے کے لئے، جس کے تحت ہم ایک بار پھر رہے ہیں انسانوں ڈالنے، یا میں اس کیس، بار میں ان کے مناسب محل وقوع. اور یہ پہلے بھی ہو چکا ہے میں پیچھے مڑ. لیکن یہ ایک، بھی، اصول میں، اب بھی مربع (ن) ہے. 

تو ہم مختصر نہیں کر سکتے تو دیکھتے ہیں ان کے طور پر مندرجہ ذیل ہے. میں آگے جانے کے لئے اور صرف دینے کے لئے جا رہا ہوں بات کر کے ایک عام طریقہ سے ہمیں طرح ان چیزوں کے بارے میں، میرا تعارف دو یہاں سنکیتن کا صرف تھوڑا سا. تم نے کچھ کہا جاتا ہے کو دیکھنے کے لئے کے بارے میں بڑا ہو اے، یہ لفظی ہے کیونکہ ایک بڑا او اور یہ کہ ایک کمپیوٹر کا ایک طریقہ ہے سائنسدان یا اس سے بھی استعمال کرتا ہے ایک گنیتشتھ رننگ ٹائم کی وضاحت کرنے کے کچھ الگورتھم کی. یہ اصل میں کس طرح بہت سے اقدامات کرنے کی ہے؟ 

اب میں کے ساتھ اپنے آپ کو پریشان کرنے جا رہا ہوں یہاں صرف ایک لمحے میں میری لکھاوٹ. لیکن میرے آگے بڑھو اور اس کا کہنا ہے کہ دو یہ یہاں پر بڑی اے ہو جائے گا. اور مجھ سے ایک دوسرے سے متعارف کرانے دو سنہرے بالوں والی، ایک سرمایہ اومیگا. ومیگا، کے برعکس جا رہا ہے بنیادی طور پر، بڑی اے جبکہ بڑی او کے کا مطلب ہے، بدترین کیس میں کتنا وقت کچھ الگورتھم میں لے سکتا ہے (ن) کے لحاظ سے، اومیگا جا رہا ہے کتنا وقت یہ شاید سب سے بہتر صورت میں لیتے ہیں. اور ہم سے میرا کیا مطلب دیکھیں گے صرف ایک لمحے میں بہترین کیس. 

تو کچھ سادہ شروع کرتے ہیں. مجھے ایک لکیری تلاش کے ساتھ شروع کرتے ہیں. تو چھںٹائی نہیں. ہم اس لکیری تلاش کو بلاتا ہوں. اور اب، ایک چھوٹی سی بنا اس کی میز باہر. اور اب، لکیری تلاش کی صورت میں، بدترین صورت میں، کتنے قدم ہے یہ ایک تلاش کرنے کے لئے مجھے لے جا صوابدیدی کی پسند کا نمبر؟ اور (ن) کل دروازے ہے یا (ن) کل تعداد. بدترین. کتنے اقدامات میں ہے جا رہا ہوں ایک صف میں نمبر 50 تلاش کرنے کے لئے لے (ن) کے دروازوں کی؟ اور کیوں؟ یہ سب ہو سکتا ہے کیونکہ آخر پر ختم طریقہ. جینیفر کا سامنا کرنا پڑا اتنا پسند، نمبر 50 میں ایسا ہے، تو پوری طرح ختم ہو گیا تھا بدترین لکیری تلاش کریں (ن) کے بڑے اے، ہم کہیں گے کیا جاتا ہے. 

کیا بہترین کیس کے متعلق، اگر تم واقعی خوش ہو جاؤ تو کیا ہوگا؟ یہ صرف، ایک قدم لے جا رہا ہے اقدامات پر یا مسلسل نمبر. تو ہم نے 1 کے طور پر اس کی وضاحت کریں گے. تو یہ بہت اچھا ہے. اب ہم کچھ کیا تو بائنری تلاش پسند ہیں؟ بدترین میں تو بائنری تلاش، ، کیس لیا کتنا وقت؟ 

[آوازیں INTERPOSING] 

ڈیوڈ جے MALAN: تو اصل میں، میں نے ایک جوڑے کے مقامات میں یہ سنا. تو یہ اصل میں،، N لاگ ان دینے یا لینے ہے ہم نے نصف میں فہرست کے طور پر تقسیم کی وجہ سے پھر سے، اور پھر سے، اور میں دوبارہ، ہم قابل ہیں آخر میں، تلاش کرنے کے لئے، قیمت، یہ وہاں ہے، لیکن ایک کیچ ہو تو. ہم ہے کہ مفروضہ کیا ہے بائنری تلاش کے لئے حاصل کی جاچکی کے لئے لے؟ یہ حل ہو گا. یہ حل نہیں ہے، آپ بات کو تقسیم کر سکتے ہیں میں بار بار آدھا ہے، اور آپ چھوڑ کر جا سکتے ہیں، اور آپ کا حق جا سکتے ہیں، اور آپ کو بائیں اور دائیں جا سکتے ہیں، لیکن آپ ہیں عنصر اگر تلاش کرنے کے لئے نہیں جا رہا فہرست کے مطابق نہیں ہے، کیونکہ تم اس کی کمی محسوس ہو سکتا ہے. آپ heuristic وجہ سے، بائیں جا کے لئے یا دائیں یہ تو غلط ہونے جا رہا ہے یقینا حل نہیں. تو ایک چھپی ہوئی قیمت کی طرح ہے کچھ اس طرح کا استعمال کرتے ہوئے کرنے کے لئے. 

اب، ہمارے چھنٹائی میں جانے دو یلگوردمز تلاش نہیں - اوہ، اصل میں اس کی خالی میں چلتے ہیں. سب سے بہتر صورت میں ثنائی تلاش کریں؟ یہ صرف ہو تو یہ بھی ہے 1 بہت سرنی کے وسط، یا میں فون بک کے وسط. اب بلبلا طرح کرتے ہیں. تو ایک بار پھر، اب ہم میں داخل کر رہے ہیں قسم، نہیں تلاش. 

بدترین صورت میں، کتنے قدم کیا ہم دعوی بلبلا طرح لے جا رہا ہے؟ ن مربع. لہذا میں سمجھتا ہوں کہ اپنی طرف متوجہ کرنے کے لئے جا رہا ہوں. اوہ، میری لکھاوٹ بھی برا لگتا ہے یہ بڑی پیش کیا ہے جب. ٹھیک ہے. تاکہ مربع (ن) ہے. اور ببل قسم کی سب سے بہترین صورت میں، کتنے قدم یہ لے جا رہا ہے؟ 1، میں نے سنا. 

اسپیکر 1: N. 

ڈیوڈ جے MALAN: N، میں نے سنا. 

اسپیکر 1: 2. 

ڈیوڈ جے MALAN: 2، میں نے سنا. میں 3 سن رہے ہو؟ ٹھیک ہے. تو میں نے (ن)، 2، 1 سنا ہے، لیکن لینے چلو ان لوگوں کے علاوہ کم از کم سب سے پہلے تجاویز، 1. یہ اس وجہ سے، ایک بری سنتیں نہیں ہے کی طرح یہاں ایک پیٹرن مندرجہ ذیل ہے. لیکن یہ صرف اس صورت میں ہے کہ کس طرح میں 1 قدم لیتا ہے تو دنیا میں دعوی کر سکتا ہے اس فہرست میں صرف کی اجازت ہوں تو اس وجہ سے، کے مطابق ہے 1 قدم، کس طرح بہت سے عناصر پر لینے کے لئے میں واقعی میں اس بات کا یقین کرنے کے لئے کی جانچ پڑتال کر سکتا ہے؟ ٹھیک ہے، صرف 1، جس کا مطلب ہے کہ (ن) ہے مائنس 1 عناصر کہ باہر کر سکتے ہیں آرڈر میں، اور میں نے صرف اس کے بعد ایمان پر جا رہا ہوں 1 عنصر کی طرف دیکھ کہ چیز کے مطابق ہے. یہاں درست نہیں ہے تو 1. تو minimally، کتنے میں کی طرف دیکھنے کی کیا ضرورت ہے؟ 

[آوازیں INTERPOSING] 

واقعی ن مائنس 1، یا،: ڈیوڈ جے MALAN (ن) میں ہر طرف دیکھنے کی ضرورت ہے کیونکہ اس بات کو یقینی بنانے کے لئے عنصر اس حکم سے باہر نہیں ہے. لیکن ایک بار پھر، ہم لہر ہماری طرح ہوں گے چھوٹے نمبروں پر ہاتھ اور (ن) بڑی ہو جاتا ہے کے طور پر، وہ ہیں، جو فرض ویسے بھی uninteresting. تو وہ بلبلا طرح ہے. اور اب، یہ گزشتہ دو کرتے ہیں. پھر سلیکشن ترتیب دیں، اور ہم کروں گا اندراج کی طرح کرتے ہیں. اور پھر ہم آپ کے اڑا گا بہت کچھ کے ساتھ ذہنوں ان میں سے سب سے بہتر. ٹھیک ہے. 

چلانے کے سب سے زیادہ کیس کیا ہے ترتیب دیں انتخاب کے وقت؟ 

اسپیکر 4: N مربع. 

ڈیوڈ جے MALAN: N مربع، میں سن رہا ہوں. لیکن کیوں ن intuitively، مربع؟ 

اسپیکر 4: ہم صرف یہ کیا ہے. 

ڈیوڈ جے MALAN: ہم صرف یہ کیا ہے. ٹھیک ہے. جواب اچھا ہے. لیکن intuitively، کیوں انتخاب ہے ترتیب دیں N مربع؟ ہم کو کس بات کی کیا ضرورت تھی بار بار؟ ہم ہیں، کے ذریعے سکیننگ کے رکھنے کے لئے تھا آپ سب سے چھوٹی، تم ہو سب سے چھوٹا، آپ کو سب سے چھوٹی ہیں. اور حاصل کی جا چکی ہے، ہم (ن) کے لے جانے کے لئے کے قابل تھے اقدامات، پھر (ن) تو مائنس 1، N مائنس 2. لیکن آپ کو کس قسم کے ان سب کو شامل ہو، یا میں اضافہ کر دیا ہے کہ ایمان پر لے لو پیشگی میں ان کو، ہم (ن) موٹے طور پر حاصل کچھ چھوٹی تعداد مائنس مربع. تو میں نے اس (ن) مربع فون کرنے جا رہا ہوں. لیکن سب سے بہتر انتخاب میں ترتیب کے ساتھ کیس، یہ کتنے قدم ہے مجھے لینے کے لئے جا رہے ہیں؟ 

اسپیکر 5: [اشراوی] 

ڈیوڈ جے MALAN: یہ بدقسمتی ہے اب بھی (ن) مربع، ہے نا؟ میں سب سے چھوٹا منتخب رہا ہوں کیونکہ اگر عنصر، اور ہم، یہاں سات افراد تھے میں صرف جانتے ہیں، ایک بار میں بہت کرنے کے لئے حاصل آخر، کہ میں سب سے چھوٹا ملا ہے نمبر، جہاں کہیں بھی وہ یا وہ ہو سکتا ہے. لیکن کس طرح میں اگلے حاصل کر سکتا ہوں سب سے چھوٹا نمبر؟ میں ایک پاس کرنا ہے. تو سب سے بہتر صورت میں، کیا ہے انتخاب ترتیب دیں کرنے کے لئے ان پٹ؟ یہ ایک پہلے سے ہی ترتیب فہرست، نمبر ایک ہے، نمبر دو، نمبر تین، نمبر چار. لیکن میں نے ایک کمپیوٹر ہوں. مجھے صرف ایک ہی میں دیکھ سکتے ہیں ایک وقت میں بات. ایک قدم میں حل نہیں کر سکتے ہیں واپس ایک انسانی اور کہتے ہیں، جیسے اہ، یہ صحیح لگ رہا ہے. 

میں صرف میں درست فیصلہ کر سکتے ہیں منتخب کر کے انتخاب ترتیب دیں سب سے چھوٹا نمبر. لیکن میں نمبر ایک سب سے پہلے تلاش کرنے، چاہے میں اس بارے میں کچھ نہیں جانتے تو میں نہیں کرتا جو دوسرے نمبر،، سب میں میں ایک سرنی کے حوالے کر دیا گیا ہے کو معلوم ہے کہ ہیں جس کے پیچھے دروازے کی یا ایک سیٹ نمبر، میں نے اس سے ایک جانتے واحد راستہ سب سے چھوٹا تھا؟ میں یہاں کے تمام راستے میں ملتا ہے اور احساس ہے تو، لات، ایک بے شک سب سے چھوٹا تھا. 

لیکن میں کیسے پھر اس بات کا تعین کرتے ہیں دو اگلے سب سے چھوٹی ہے؟ اسی اکشمتا کرتے ہوئے بار بار. تو آخر، اندراج کے ساتھ ترتیب دیں، کس طرح، بدترین صورت میں، ہم اس کارکردگی کا مظاہرہ کہا تھا؟ یہ بھی مربع (ن) ہے. اور کس طرح کے بارے میں سب سے بہترین کیس کے ساتھ؟ ہم نے ایک cliffhanger کے طور پر کہ چھوڑ دیں گے. ہم نے ان کو خالی اگلی بار میں بھر دیں گے لیکن پہلے مجھے تجویز کرتے ہیں کہ ہم بنیادی طور سے بہتر کرتے ہیں ان میں سے سب، ٹھیک ہے؟ 

تو اپنے آپ کے لئے کیا سوچتے اندراج ترتیب دیں ہونے جا رہا ہے. ٹھیک ہے، کہ، بہت ڈرامائی نہیں تھا مجھے صرف ایک ہی ہوں کیونکہ اس تبدیلی کو دیکھا. واہ. ٹھیک ہے. تو یہاں ہم ایک حد تک ہے مختلف مظاہرے. میں یہاں پر میں زوم، تو آپ اس پر نظر آئیں گے بائیں ہم میں بلبلا طرح ہے ہم انتخاب قسم ہے مشرق، اور پر اب تک ٹھیک ہے، ہم کچھ ہے کہ ہم ابھی دیکھا نہیں ہے ترتیب دیں ضم ملاقات کی. لیکن ہم کیا گیا ہے کے بارے میں غور کیا آج ابھی تک یہاں کیا کر رہے. جینیفر پہلے مرحلے پر آیا تو ہم اعداد کی سرنی کے ذریعے چلا گیا پھر سے، اور میں دوبارہ، لکیری تلاش کے ساتھ، اور ہم بڑی اے، لکیری رننگ ٹائم ملا (ن) کی، تو بات کرنے کے لئے. 

ہم اب کے پہلے ہفتے پر غور کریں تو کلاس، ہم تقسیم اور فتح تھا، اور ہم نے فون بک، پھاڑنا تھا اور جینیفر، اور ہم نے اجتماعی طور پر تھا جس لیوریجڈ کہ کلیدی بصیرت، کی طرف سے بار بار اپنے آپ کو دوبارہ کسی نہ کسی طرح، دور پھینک، پھینک ، دور پھینک مسئلہ کے نصف ہے، یا عام طور پر، نصف میں ایک مسئلہ تقسیم، اور پھر اس کے چھوٹے ٹکڑے علاج conceptually برابر مسئلہ دوسرے، ہم کسی نہ کسی طرح کیا بنیادی طور پر بہتر. لیکن بلبلا ترتیب کے ساتھ، ساتھ انتخاب ترتیب دیں، اندراج کی ترتیب کے ساتھ، ہم نے کر سکتے ہیں جینیفر نے ایسی کوئی بصیرت. ہم بہت زیادہ صرف واپس ہوا اور آگے ایک مکمل وقت کے گروپ، اور ہم tweaked چیزوں تھوڑا سا، گماگمن اس آرڈر میں، ہو سکتا ہے ڈالنے یا منتخب. لیکن دن کے آخر میں، میں نے بہت کیا عجیب چلنے کی آگے پیچھے. ہم واقعی بیعانہ کچھ نہیں کیا جینیفر طرح ہوشیار تقسیم کی طرح تھا اور فتح. 

تو اس طرح ضم، اس کے برعکس کی طرف سے، جس کے ہم اگلے ہفتے تک نظر نہیں آئے گا، چل رہا ہے بیعانہ کی تقسیم کی طرف سے ہے کہ اہم خیال ان پٹ، اور پھر halving، اور پھر halving، اور پھر halving. اور اس کے لوپ میں سے ہر ایک iteration پر، بائیں نصف چھانٹ رہا ہے، اور صحیح نصف، بائیں نصف کے بائیں نصف تو، پھر بائیں اور دائیں نصف، بائیں، دائیں نصف کے نصف ہے، اور حق نصف کا حق نصف. اور بار بار بار بار. 

لہذا اگر آپ ضعف یہ دیکھو، لیکن یہ کریں گے اگلے ہفتے ہم سے انتظار کر رہا ہے کیا ہے. اور عام طور پر، جب ہم تھوڑا سا لگتا ہے ایسے کسی بھی مسئلہ پر تھوڑا سا مشکل. ہم بائیں طرف مربع (ن)، (ن) ہے وسط میں مربع، اور (ن) دائیں N لاگ ان کریں. تو آپ کا اصل cliffhanger ہے. ہم پیر کو نظر آئے گا. 

[تالیاں]