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

لہذا، قابل ہونے کی وجہ سے تجزیہ کرنے کے لئے الگورتھم، اس آلے کے سیٹ کا استعمال کرتے ہوئے بنیادی طور پر، question-- پوچھتا اس الگورتھم پیمانے کرتا ہے کس طرح ہم اس پر زیادہ سے زیادہ ڈیٹا پھینک کے طور پر؟ CS50 میں، ہم اعداد و شمار کی رقم ہو کے ساتھ کام بہت چھوٹا ہے. عام طور پر، ہمارے پروگرام جا رہے ہیں ایک دوسرے یا less-- میں چلانے کے لئے شاید بہت کم خاص طور پر جلد. 

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

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

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

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

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

اب، ہم واقعی پرواہ نہیں کرتے بالکل (ن) کے F کیا ہے کے بارے. اصل میں، ہم بہت کم will-- یقینی طور پر کبھی اس class-- میں کوئی واقعی گہری میں کودو چ ن ہے کا تجزیہ. ہم صرف کیا F کے بارے میں بات کرنے کے لئے جا رہے ہیں N تقریبا یا جو اس کے لئے جاتا ہے. اور ایک الگورتھم کی پدررتی ہے اس سب سے زیادہ آرڈر کی اصطلاح کی طرف سے مسلط. اور ہم دیکھ سکتے ہیں میں لے کر اس سے کیا مطلب ایک سے زیادہ ٹھوس مثال کے طور پر نظر آتے ہیں. 

تو ہم کا کہنا ہے کہ دو تین مختلف یلگوردمز. جن میں سے پہلے ن لیتا ہے وسائل کی cubed کی، کچھ یونٹس سائز (ن) کے ایک ڈیٹا مذکور کارروائی کے. ہم سے لیتا ہے کہ ایک دوسرے الگورتھم ہے cubed کی علاوہ مربع ن وسائل N سائز (ن) کے ایک ڈیٹا مذکور کارروائی کے. اور ہم نے ایک تہائی ہے کہ in-- چلتا ہے کہ الگورتھم لیتا ن cubed مائنس 8N مربع وسائل کے علاوہ 20 N یونٹس ایک الگورتھم پر عملدرآمد کرنے میں سائز (ن) کے مقرر کی معلومات کے ساتھ. 

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

ہمارے اعداد و شمار سیٹ سائز 10 ہے تو جس ، بڑے، لیکن ضروری نہیں کہ بہت بڑی نہیں ہے ہم وہاں ہے کہ دیکھ سکتے ہیں اصل میں ایک فرق کے تھوڑا سا. تیسری الگورتھم زیادہ موثر ہو جاتا. یہ اصل میں 40٪ کے بارے میں - یا 60 فیصد زیادہ موثر. یہ 40٪ وقت کی رقم لیتا ہے. یہ لے سکتے ہیں کر سکتے ہیں run-- وسائل کی 400 یونٹس سائز 10 کے اعداد و شمار مذکور کارروائی کے. پہلے جبکہ الگورتھم، اس کے برعکس کی طرف سے، وسائل کی 1،000 اکائیوں لیتا سائز 10 کے اعداد و شمار مذکور کارروائی کے. لیکن دیکھو کیا ہوتا ہے ہماری تعداد بھی بڑا حاصل. 

اب، فرق یہ الگورتھم کے درمیان تھوڑا کم واضح بننے کے لئے شروع. وہاں ہو اور حقیقت کم آرڈر terms-- یا بلکہ، کم exponents-- ساتھ شرائط غیر متعلقہ بننے کے لئے شروع. ایک ڈیٹا سیٹ سائز کی ہے تو 1،000 اور سب سے پہلے الگورتھم ایک ارب مراحل میں چلتا ہے. اور دوسری الگورتھم میں چلتا ہے ایک ارب اور ایک ملین اقدامات. اور تیسری الگورتھم چلاتے ہیں ایک ارب اقدامات کا صرف شرم میں. یہ بہت زیادہ ایک ارب قدم ہے. وہ نچلے حکم کی اصطلاحات شروع واقعی غیر متعلقہ بننے کے لئے. اور صرف واقعی کرنا گھر ہتھوڑا point-- ڈیٹا کی ان پٹ سائز کی ہے million-- ان تینوں بہت ایک quintillion-- تو لے میری ریاضی correct-- قدم ہے ایک ڈیٹا کی ان پٹ پر عملدرآمد کرنے میں سائز ایک ملین. کہ اقدامات کی ایک بہت ہے. اور حقیقت یہ ہے کہ ان میں سے ایک ہو سکتا ہے ایک جوڑے 100،000، یا ایک جوڑے لے 100 ملین سے بھی کم ہے جب ہم ایک بڑی تعداد کے بارے میں بات کر رہے ہیں کہ اس قسم کی غیر متعلقہ ہے big--. وہ سب لے جاتے ہیں تقریبا ن cubed، اور تو ہم اصل سے رجوع کریں گے ان یلگوردمز کی سب کے لئے (ن) کے حکم پر کیا جا رہا ہے کے طور پر cubed کی یا ن cubed کی بڑی اے. 

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

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

پھر چیزیں تھوڑا more-- حاصل کم عظیم وہاں سے. آپ کبھی کبھی، لکیری طالبدق وقت ہے لاگ ان لکیری وقت کہا جاتا ہے یا صرف (ن) کے لاگ ان ن. اور ہم ایک مثال گے ایک الگورتھم کی ہے کہ اب بھی بہتر ہے جو ن لاگ ان N، رنز سے چکوری ہیں وقت مربع ن. یا رقمی وقت، (ن) دو دو کے مقابلے میں زیادہ سے زیادہ کسی بھی تعداد. یا اسیاتی وقت، جس میں بھی worse-- سی (ن) کے ہے. تو کچھ مسلسل نمبر پر اٹھایا ان پٹ کے سائز کی طاقت. اگر ایسا ہے تو 1،000-- ہے تو ڈیٹا کی ان پٹ، سائز 1،000 ہے یہ 1،000th اقتدار میں سی لے جائے گا. یہ کثیر رقمی وقت کے مقابلے میں ایک بہت برا ہے. 

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

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

اصل میں، 2 nums-- شامل ہے جس ہم جتنی well-- پہلے دیکھا ہے صرف دو integers پر عملدرآمد. یہ ایک قدم نہیں ہے. یہ اصل میں ایک جوڑے کے اقدامات ہے. آپ کو ایک حاصل، آپ B حاصل، آپ کو ان میں شامل کریں ایک دوسرے کے ساتھ، اور آپ کی پیداوار کے نتائج. تو یہ 84 قدم ہے. لیکن یہ ہمیشہ مسلسل ہے قطع نظر ایک یا ب. آپ کو ایک حاصل کرنے کے لئے، ب حاصل، شامل ان کے ساتھ، آؤٹ پٹ نتیجہ. تو یہ ایک مسلسل وقت الگورتھم ہے. 

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

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

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

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

ہم ایک بیرونی لوپ ہے اگر ایسا ہے جس میں اندر P بار چلتا ہے ایک اندرونی لوپ کہ کیا مرتبہ دوبارہ P چلتا ہے بدترین کیس رن ٹائم کوڈ کا یہ ٹکڑا کے؟ آپ P کے بڑے اے مربع لگتا ہے کیا؟ 

میں ڈوگ لایڈ ہوں. یہ CS50 ہے.