कंप्यूटेशनल कॉम्प्लेक्सिटी थ्योरी के अनुसार, पोटेंशियल मेथड को एक डेटा स्ट्रक्चर के एमोर्टाइज़्ड टाइम और स्पेस कॉम्प्लेक्सिटी का विश्लेषण करने के लिए लागू एक विधि के रूप में परिभाषित किया जाता है, जो ऑपरेशन्स के सीक्वेंस पर इसके प्रदर्शन का एक माप है जो दुर्लभ लेकिन महंगे ऑपरेशन्स की लागत को समाप्त करता है।
पोटेंशियल मेथड में, एक फ़ंक्शन Φ चुना जाता है जो डेटा स्ट्रक्चर के स्टेट्स को नॉन-नेगेटिव नंबर्स में बदल देता है। यदि S को डेटा स्ट्रक्चर के स्टेट के रूप में माना जाता है, तो Φ(S) उस कार्य को दर्शाता है जिसकी गणना एमोर्टाइज़्ड विश्लेषण में की गई है लेकिन अभी तक निष्पादित नहीं किया गया है। इस प्रकार, Φ(S) की कल्पना उस स्टेट में संग्रहीत पोटेंशियल ऊर्जा की मात्रा की गणना के रूप में की जा सकती है। डेटा स्ट्रक्चर को इनिशियलाइज़ करने से पहले, पोटेंशियल मान को शून्य परिभाषित किया जाता है। वैकल्पिक रूप से, Φ(S) की कल्पना स्टेट S में अव्यवस्था की मात्रा या उसके आदर्श स्टेट से दूरी का प्रतिनिधित्व करने के रूप में की जा सकती है।
उदाहरण
मान लीजिए हम एक पोटेंशियल फ़ंक्शन Φ (पढ़ें "फाई") को डेटा स्ट्रक्चर के स्टेट्स पर दर्शा सकते हैं जो निम्नलिखित गुणों को संतुष्ट करता है:
- Φ(a₀) = 0, जहां a₀ डेटा स्ट्रक्चर की प्रारंभिक अवस्था है।
- कम्प्यूटेशन के दौरान होने वाले डेटा स्ट्रक्चर के सभी स्टेट्स aₜ के लिए Φ(aₜ) ≥ 0।
सहज रूप से, पोटेंशियल फ़ंक्शन कम्प्यूटेशन में किसी भी बिंदु पर प्री-चार्ज्ड समय को ट्रैक करने में सक्षम होगा। यह महंगे ऑपरेशन्स के भुगतान के लिए उपलब्ध सेव्ड-अप समय की मात्रा को मापता है। यह बैंकर की विधि में बैंक बैलेंस की तरह है। लेकिन दिलचस्प बात यह है कि यह केवल डेटा स्ट्रक्चर की वर्तमान अवस्था पर निर्भर करता है, उस कम्प्यूटेशन के इतिहास पर नहीं जो इसे उस अवस्था में ले आया।
हम तब एक ऑपरेशन के एमोर्टाइज़्ड समय को इस प्रकार परिभाषित करते हैं:
c + Φ(a') – Φ(a),
जहां c ऑपरेशन की मूल लागत है और a और a' ऑपरेशन से पहले और बाद में डेटा स्ट्रक्चर की अवस्थाएं हैं, क्रमशः। इस प्रकार एमोर्टाइज़्ड समय को वास्तविक समय प्लस पोटेंशियल में परिवर्तन के रूप में परिभाषित किया जाता है। आदर्श रूप से, Φ को इस तरह परिभाषित किया जाना चाहिए कि प्रत्येक ऑपरेशन का एमोर्टाइज़्ड समय छोटा हो। इस प्रकार पोटेंशियल में परिवर्तन को कम-लागत वाले ऑपरेशन्स के लिए पॉजिटिव और उच्च-लागत वाले ऑपरेशन्स के लिए नेगेटिव मापा जाना चाहिए।
