Potential method
کمپیوٹیشنل پیچیدگی کے نظریہ میں، ممکنہ طریقہ ایک ایسا طریقہ ہے جو ڈیٹا ڈھانچے کے تخفیف شدہ وقت اور جگہ کی پیچیدگی کا تجزیہ کرنے کے لیے استعمال ہوتا ہے، جو کارروائیوں کے سلسلے پر اس کی کارکردگی کا ایک پیمانہ ہے جو کبھی کبھار لیکن مہنگے آپریشنز کی لاگت کو ہموار کرتا ہے۔ تخفیف شدہ وقت کی تعریف ممکنہ طریقہ کار میں، ایک فنکشن کا انتخاب کیا جاتا ہے جو اعداد و شمار کے ڈھانچے کو غیر منفی نمبروں سے جوڑتا ہے۔ اگر S اعداد و شمار کے ڈھانچے کی حالت ہے، تو φ (S) اس کام کی نمائندگی کرتا ہے جس کا حساب لیا گیا ہے ("ادائیگی کے لیے") ادائیگی شدہ تجزیہ میں لیکن ابھی تک انجام نہیں دیا گیا ہے۔ اس طرح، φ (S) کو اس حالت میں ذخیرہ شدہ ممکنہ توانائی کی مقدار کا حساب لگانے کے طور پر سوچا جا سکتا ہے۔ ڈیٹا ڈھانچے کو شروع کرنے کے عمل سے پہلے ممکنہ قدر کو صفر کے طور پر بیان کیا جاتا ہے۔ متبادل طور پر، ± (S) کو حالت S میں خرابی کی مقدار یا کسی مثالی حالت سے اس کے فاصلے کی نمائندگی کرنے کے طور پر سوچا جا سکتا ہے۔ او کو کسی ڈیٹا ڈھانچے پر کارروائیوں کی ترتیب کے اندر کوئی بھی انفرادی آپریشن ہونے دیں، جس میں ایس بی فور آپریشن او سے پہلے ڈیٹا ڈھانچے کی حالت کو ظاہر کرتا ہے اور سیفر آپریشن او مکمل ہونے کے بعد اس کی حالت کو ظاہر کرتا ہے۔ ایک بار φ کا انتخاب ہو جانے کے بعد، آپریشن o کے لیے تخفیف شدہ وقت کی تعریف اس طرح کی جاتی ہے جہاں C متناسبیت کا ایک غیر منفی مستقل (وقت کی اکائیوں میں) ہے جو پورے تجزیے میں طے رہنا چاہیے۔ یعنی، تخفیف شدہ وقت کی تعریف آپریشن کے ذریعے لیے گئے اصل وقت کے ساتھ ساتھ آپریشن کی وجہ سے پیدا ہونے والی صلاحیت میں فرق کے C گنا کے طور پر کی جاتی ہے۔ بگ او نوٹیشن کا استعمال کرتے ہوئے ایسمپٹوٹک کمپیوٹیشنل پیچیدگی کا مطالعہ کرتے وقت، مستقل عوامل غیر متعلقہ ہوتے ہیں اور اس لیے مستقل سی کو عام طور پر خارج کر دیا جاتا ہے۔ تخفیف شدہ اور حقیقی وقت کے درمیان تعلق اس کی مصنوعی ظاہری شکل کے باوجود، کارروائیوں کے سلسلے کا کل تخفیف شدہ وقت کارروائیوں کے اسی سلسلے کے لیے حقیقی وقت پر ایک درست اوپری حد فراہم کرتا ہے۔ کارروائیوں کے کسی بھی سلسلے کے لیے، وضاحت کریں: کل تخفیف شدہ وقت: کل اصل وقت: پھر: جہاں پوٹینشیل فنکشن ویلیوز کی ترتیب ایک دوربین کی سیریز بناتی ہے جس میں ابتدائی اور حتمی پوٹینشیل فنکشن ویلیوز کے علاوہ تمام اصطلاحات جوڑوں میں منسوخ ہو جاتی ہیں۔ اس کو دوبارہ ترتیب دیتے ہوئے، ہم حاصل کرتے ہیں: چونکہ اور، لہذا تخفیف شدہ وقت کو کارروائیوں کے سلسلے کے اصل وقت پر درست اوپری حد فراہم کرنے کے لیے استعمال کیا جا سکتا ہے، حالانکہ انفرادی آپریشن کے لیے تخفیف شدہ وقت اس کے اصل وقت سے وسیع پیمانے پر مختلف ہو سکتا ہے۔ بدترین صورت کے آدانوں کا تخفیف شدہ تجزیہ عام طور پر، تخفیف شدہ تجزیہ ان پٹ ترتیب کے بارے میں بدترین صورت کے مفروضے کے ساتھ مل کر استعمال کیا جاتا ہے۔ اس مفروضے کے ساتھ، اگر X ایک قسم کا آپریشن ہے جو ڈیٹا اسٹرکچر کے ذریعے انجام دیا جا سکتا ہے، اور n ایک انٹیجر ہے جو دیئے گئے ڈیٹا اسٹرکچر کے سائز کی وضاحت کرتا ہے (مثال کے طور پر، اس میں موجود آئٹمز کی تعداد)، تو ٹائپ X کے آپریشنز کے لیے امورٹائزڈ ٹائم کو زیادہ سے زیادہ، سائز n کے ڈیٹا اسٹرکچرز پر آپریشنز کے تمام ممکنہ ترتیبات اور ترتیب کے اندر ٹائپ X کے تمام آپریشنز کے درمیان، آپریشن Oi کے لیے امورٹائزڈ ٹائم کے طور پر بیان کیا جاتا ہے۔ اس تعریف کے ساتھ، کارروائیوں کے سلسلے کو انجام دینے کے وقت کا تخمینہ اس ترتیب میں ہر قسم کے عمل کے لیے ادا کیے گئے وقت کو اس قسم کے عمل کی تعداد سے ضرب دے کر لگایا جا سکتا ہے۔ مثال متحرک صف ایک متحرک صف اشیاء کی صف کو برقرار رکھنے کے لیے ایک ڈیٹا ڈھانچہ ہے، جو صف کے اندر پوزیشنوں تک بے ترتیب رسائی اور صف کے سائز کو ایک سے بڑھانے کی صلاحیت دونوں کی اجازت دیتا ہے۔ یہ جاوا میں "ارے لسٹ" قسم کے طور پر اور ازگر میں "لسٹ" قسم کے طور پر دستیاب ہے۔ ایک متحرک صف کو ڈیٹا ڈھانچے کے ذریعے نافذ کیا جا سکتا ہے جس میں آئٹمز کی ایک صف A پر مشتمل ہوتی ہے، جس کی لمبائی کچھ N ہوتی ہے، جس میں ایک نمبر n ≤ N ہوتا ہے جو اب تک استعمال ہونے والی صف کے اندر پوزیشنوں کی نمائندگی کرتا ہے۔ اس ڈھانچے کے ساتھ، متحرک صف تک بے ترتیب رسائی کو اندرونی صف A کے اسی سیل تک رسائی حاصل کرکے نافذ کیا جاسکتا ہے، اور جب n <N ایک ایسا آپریشن جو متحرک صف کے سائز کو بڑھاتا ہے تو اسے صرف n میں اضافہ کرکے نافذ کیا جاسکتا ہے۔ تاہم، جب n = N، تو A کا سائز تبدیل کرنا ضروری ہے، اور ایسا کرنے کے لیے ایک عام حکمت عملی اس کے سائز کو دوگنا کرنا ہے، جس کی جگہ A کی لمبائی 2n کی نئی صف ہے۔ اس ڈھانچے کا تجزیہ پوٹینشیل فنکشن کا استعمال کرتے ہوئے کیا جا سکتا ہے: ± = 2n−N چونکہ سائز تبدیل کرنے کی حکمت عملی ہمیشہ A کو کم از کم نصف بھرا ہونے کا سبب بنتی ہے، اس لیے یہ پوٹینشیل فنکشن ہمیشہ غیر منفی ہوتا ہے، جیسا کہ مطلوبہ ہوتا ہے۔ جب انک سائز آپریشن ریز سائز آپریشن کا باعث نہیں بنتا ہے، تو φ میں 2 کا اضافہ ہوتا ہے، ایک مستقل۔ لہذا، آپریشن کا مستقل اصل وقت اور صلاحیت میں مسلسل اضافہ اس قسم کے آپریشن کے لیے مستقل تخفیف شدہ وقت دینے کے لیے یکجا ہوتا ہے۔ تاہم، جب انک سائز آپریشن ریز سائز کا سبب بنتا ہے، تو ریز سائز کے بعد φ کی پوٹینشل ویلیو کم ہو کر صفر ہو جاتی ہے۔ ایک نئی اندرونی صف A کو مختص کرنا اور پرانی اندرونی صف سے نئی میں تمام اقدار کو کاپی کرنے میں O (n) اصل وقت لگتا ہے، لیکن (متناسب C کے مستقل کے مناسب انتخاب کے ساتھ) یہ پوٹینشل فنکشن میں کمی کی وجہ سے مکمل طور پر منسوخ ہو جاتا ہے، جس سے آپریشن کے لیے ایک مستقل کل تخفیف شدہ وقت باقی رہ جاتا ہے۔ ڈیٹا ڈھانچے کی دیگر کارروائیاں (صف کے سائز کو تبدیل کیے بغیر صف کے خلیوں کو پڑھنا اور لکھنا) ممکنہ فنکشن کو تبدیل کرنے کا سبب نہیں بنتی ہیں اور ان کا مستقل وقت ان کے اصل وقت کے برابر ہوتا ہے۔ لہذا، سائز تبدیل کرنے کی حکمت عملی اور ممکنہ فنکشن کے اس انتخاب کے ساتھ، ممکنہ طریقہ سے پتہ چلتا ہے کہ تمام متحرک صف کی کارروائیوں میں مستقل وقت لگتا ہے۔ اس کو کارروائیوں کے سلسلے کے مقابلے میں تخفیف شدہ وقت اور اصل وقت سے متعلق عدم مساوات کے ساتھ جوڑ کر، اس سے پتہ چلتا ہے کہ n متحرک صف کی کارروائیوں کا کوئی بھی سلسلہ بدترین صورت میں O (n) اصل وقت لیتا ہے، اس حقیقت کے باوجود کہ کچھ انفرادی کارروائیوں میں خود ہی وقت لگ سکتا ہے۔ جب متحرک صف میں ایسی کارروائیاں شامل ہوتی ہیں جو صف کے سائز کو کم کرنے کے ساتھ ساتھ اسے بڑھاتی ہیں، تو ممکنہ فنکشن کو منفی ہونے سے روکنے کے لیے اس میں ترمیم کی جانی چاہیے۔ ایسا کرنے کا ایک طریقہ یہ ہے کہ اوپر دیے گئے فارمولے کو اس کی مطلق قیمت سے تبدیل کیا جائے۔ ملٹی پاپ اسٹیک ایک اسٹیک پر غور کریں جو مندرجہ ذیل کارروائیوں کی حمایت کرتا ہے: شروع کریں-ایک خالی اسٹیک بنائیں۔ دبائیں-اسٹیک کے اوپر ایک عنصر شامل کریں، اسٹیک کو 1 سے بڑھا دیں۔ پاپ (کے)-اسٹیک کے اوپری حصے سے کے عناصر کو ہٹا دیں، جہاں کے موجودہ اسٹیک سائز سے زیادہ نہیں ہے۔ پاپ (کے) کے لیے او (کے) وقت درکار ہوتا ہے، لیکن ہم یہ ظاہر کرنا چاہتے ہیں کہ تمام کارروائیوں میں او (1) کی ادائیگی کا وقت لگتا ہے۔ اس ڈھانچے کا تجزیہ پوٹینشل فنکشن کا استعمال کرتے ہوئے کیا جا سکتا ہے: φ = عناصر کی تعداد اسٹیک یہ نمبر ہمیشہ غیر منفی ہوتا ہے، جیسا کہ ضرورت ہوتی ہے۔ پش آپریشن میں مستقل وقت لگتا ہے اور اس میں 1 کا اضافہ ہوتا ہے، اس لیے اس کا تخفیف شدہ وقت مستقل ہوتا ہے۔ ایک پاپ آپریشن میں وقت O (k) لگتا ہے لیکن یہ k کے ذریعے بھی کم کرتا ہے، اس لیے اس کا تخفیف شدہ وقت بھی مستقل ہوتا ہے۔ یہ ثابت کرتا ہے کہ m کارروائیوں کی کسی بھی ترتیب میں بدترین صورت میں O (m) اصل وقت لگتا ہے۔ بائنری کاؤنٹر بائنری نمبر کے طور پر پیش کردہ کاؤنٹر پر غور کریں اور مندرجہ ذیل کارروائیوں کی حمایت کریں: شروع کریں: قدر 0 کے ساتھ کاؤنٹر بنائیں۔ انکارپوریٹڈ: کاؤنٹر میں 1 شامل کریں۔ پڑھیں: موجودہ کاؤنٹر ویلیو واپس کریں۔ اس مثال کے لیے، ہم ٹرانسڈیکوٹومس مشین ماڈل استعمال نہیں کر رہے ہیں، بلکہ اس کے بجائے انکریمنٹ میں فی بٹ آپریشن میں وقت کی ایک اکائی کی ضرورت ہوتی ہے۔ ہم یہ دکھانا چاہتے ہیں کہ انکارپوریٹڈ O (1) کی ادائیگی میں وقت لیتا ہے۔ اس ڈھانچے کا تجزیہ پوٹینشیل فنکشن کا استعمال کرتے ہوئے کیا جا سکتا ہے: ± = نمبر-آف-بٹس-ایکول-ٹو-1 = ہیمنگ ویٹ (کاؤنٹر) یہ نمبر ہمیشہ غیر منفی ہوتا ہے اور ضرورت کے مطابق 0 سے شروع ہوتا ہے۔ ایک انکارپوریٹڈ آپریشن کم سے کم اہم بٹ کو پلٹ دیتا ہے۔ پھر، اگر ایل ایس بی کو 1 سے 0 پر پلٹ دیا جاتا ہے، تو اگلا بٹ بھی پلٹ جاتا ہے۔ یہ اس وقت تک جاری رہتا ہے جب تک کہ آخر کار تھوڑا سا 0 سے 1 پر پلٹ نہیں جاتا، جس مقام پر پلٹنا رک جاتا ہے۔ اگر کاؤنٹر ابتدائی طور پر k1 بٹس میں ختم ہوتا ہے، تو ہم کل k + 1 بٹس کو پلٹاتے ہیں، اصل وقت k + 1 لیتے ہیں اور پوٹینشل کو k−1 سے کم کرتے ہیں، لہذا امورٹائزڈ ٹائم 2 ہے۔ لہذا، ایم انک آپریشنز کو چلانے کا اصل وقت او (ایم) ہے۔ ایپلی کیشنز پوٹینشل فنکشن کا طریقہ عام طور پر فبونیکی ڈھیر کا تجزیہ کرنے کے لیے استعمال ہوتا ہے، ترجیحی قطار کی ایک شکل جس میں کسی شے کو ہٹانے میں لوگرتھمک امورٹائزڈ وقت لگتا ہے، اور دیگر تمام کارروائیوں میں مستقل امورٹائزڈ وقت لگتا ہے۔ اس کا استعمال اسپلے ٹریز کا تجزیہ کرنے کے لیے بھی کیا جا سکتا ہے، جو بائنری سرچ ٹری کی ایک خود ایڈجسٹ کرنے والی شکل ہے جس میں فی آپریشن لوگرتھمک امورٹائزڈ ٹائم ہوتا ہے۔ حوالہ جات کا الگورتھم کا تجزیہ