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