[Powered by Google Translate] آپ نے شاید سنا ہے لوگوں کو ایک روزہ یا موثر الگورتھم کے بارے میں بات کرتے ہو آپ کی مخصوص کام کا قتل کرنے کے لئے، لیکن یہ بالکل وہی جو یا پھر روزے رکھنا موثر الگورتھم کے لئے کیا مطلب ہے؟ ٹھیک ہے، یہ اصل وقت میں ایک پیمائش کے بارے میں بات نہیں کر رہا، اور یا منٹ کی طرح. اس کا ہے کیونکہ کمپیوٹر ہارڈویئر اور سافٹ ویئر بڑی تیزی سے مختلف ہوتی ہیں. میرا پروگرام تم سے سست چلانے کے لئے کر سکتے ہیں، کیونکہ میں نے اسے ایک بڑی عمر کے کمپیوٹر پر چلا رہا ہوں، یا اس وجہ سے کہ میں نے ایک آن لائن ویڈیو گیم کھیلنے ہوا ایک ہی وقت میں، جس میں میرے تمام میموری hogging ہے، یا میں مختلف سافٹ ویئر کے ذریعے اپنے پروگرام چلا رہا ہو سکتا ہے جو مشین کے ساتھ کم سطح پر بات چیت مختلف ہے. یہ سیب اور سنتری کا موازنہ کرنے کی طرح ہے. صرف اس لیے کیونکہ میرا سست کمپیوٹر اب لیتا ہے سے تمہارا واپس ایک کا جواب دینے کے لئے کا مطلب یہ نہیں ہے آپ کو زیادہ موثر الگورتھم ہے. 

تو، ہم براہ راست پروگراموں کے runtimes نہیں کا آپس میں موازنہ کر سکتے ہیں ، اور یا منٹ میں ہم نے 2 مختلف یلگوردمز کو کس طرح آپس میں موازنہ ان کی ہارڈ ویئر یا سافٹ ویئر کے ماحول سے قطع نظر؟ algorithmic کی کارکردگی کی پیمائش کا ایک وردی طرح تخلیق کرنے کے لئے، کمپیوٹر کے سائنسدانوں اور ریاضی وضع ہے ایک پروگرام کے asymptotic پیچیدگی کی پیمائش کرنے کے لئے تصورات اور ایک سنکیتن قرار دیا 'بگ Ohnotation' اس بیان کے لئے. باضابطہ تعریف یہ ہے کہ ایک تقریب F (X) G (X) کے حکم پر چلتا ہے اگر وہاں کچھ قدر (X) بھی موجود ہے ₀، x اور کچھ مسلسل، C، جس کے لئے (X) F سے کم یا برابر ہے کہ مسلسل اوقات (X) G تمام ₀ X سے بڑا x کے لیے. 

لیکن دور باضابطہ تعریف کی طرف سے ڈر نہیں لگتا. کیا یہ کم نظریاتی لحاظ سے اصل میں کیا مطلب ہے؟ ٹھیک ہے، یہ بنیادی طور پر تجزیہ کرنے کا ایک طریقہ ہے روزہ کس طرح ایک پروگرام رن ٹائم asymptotically اگتا ہے. یہ ہے کہ، کے طور پر آپ کے آدانوں کی سائز انفنٹی کی طرف بڑھ جاتی ہے، کہو، تم 10 سائز کے ایک صف کے مقابلے میں 1000 سائز کے ایک صف چھںٹائی کر رہے ہیں. آپ کے پروگرام کے رن ٹائم کس طرح اگتے ہے؟ مثال کے طور پر، حروف کی تعداد کی گنتی کا تصور ایک تار میں آسان ترین طریقہ  پوری سٹرنگ کے ذریعے چلنے کی طرف سے خط کی طرف سے خط اور ہر کردار کے لئے ایک کاؤنٹر 1 انہوں نے مزید کہا. یہ الگورتھم لکیری وقت میں چلانے کے لئے کہا جاتا ہے حروف کی تعداد کے لحاظ سے، سٹرنگ میں 'این'. مختصر میں، یہ O (ن) میں چلتا ہے. یہ کیوں ہے؟ ٹھیک ہے، اس نقطہ نظر کا استعمال کرتے ہوئے، وقت کی ضرورت ہے مکمل سٹرنگ گزرنا حروف کی تعداد کے متناسب ہے. 20 حروف کی سٹرنگ میں حروف کی تعداد کی گنتی دو مرتبہ جب تک کے طور پر یہ لگتا ہے جا 10 حروف کی سٹرنگ میں حروف شمار، کیونکہ آپ تمام حروف کو دیکھنے کے لئے ہے اور ہر کردار کو دیکھنے کے لئے کے لئے وقت کے اسی رقم لیتا ہے. جیسا کہ آپ حروف کی تعداد میں اضافہ رن ٹائم ان پٹ کی حد کے ساتھ linearly اضافہ ہو جائے گا. 

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

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

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

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

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

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

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

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

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

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

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

اگر آپ O الگورتھم (ن) ² میں چلا رہے ہیں، یا برا، ایک O (2 ⁿ) الگورتھم سب سے تیز رفتار سے بڑھتی ہوئی اقسام میں سے ایک، آپ کو سست نوٹس سچ میں شروع کر دیں گے جب آپ اعداد و شمار کی بڑی مقدار کے ساتھ کام کرنے لگتے ہیں. 

یہ asymptotic پیچیدگی ہے. شکریہ.