Potential method
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, સંભવિત પદ્ધતિ એ માહિતી માળખાના ઋણમુક્ત સમય અને અવકાશ જટિલતાનું વિશ્લેષણ કરવા માટે ઉપયોગમાં લેવાતી એક પદ્ધતિ છે, જે કામગીરીના ક્રમ પર તેની કામગીરીનું માપ છે જે વિરલ પરંતુ ખર્ચાળ કામગીરીના ખર્ચને સરળ બનાવે છે. ઋણમુક્ત સમયની વ્યાખ્યા સંભવિત પદ્ધતિમાં, એક કાર્ય પસંદ કરવામાં આવે છે જે ડેટા સ્ટ્રક્ચરની સ્થિતિને બિન-નકારાત્મક સંખ્યાઓ સાથે મેપ કરે છે. જો S એ માહિતી માળખાની સ્થિતિ છે, તો φ (S) એ એવા કાર્યને રજૂ કરે છે જે ઋણમુક્ત વિશ્લેષણમાં ("ચૂકવેલ") માટે ગણવામાં આવ્યું છે પરંતુ હજુ સુધી કરવામાં આવ્યું નથી. આમ, φ (S) ને તે સ્થિતિમાં સંગ્રહિત સંભવિત ઊર્જાની માત્રાની ગણતરી તરીકે વિચારી શકાય છે. ડેટા સ્ટ્રક્ચરને શરૂ કરવાની કામગીરી પહેલાં સંભવિત મૂલ્યને શૂન્ય તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. વૈકલ્પિક રીતે, φ (S) ને S સ્થિતિમાં અવ્યવસ્થાના પ્રમાણ અથવા આદર્શ સ્થિતિથી તેના અંતરનું પ્રતિનિધિત્વ કરતી હોવાનું માનવામાં આવે છે. ચાલો કેટલાક ડેટા સ્ટ્રક્ચર પર કામગીરીના ક્રમમાં કોઈપણ વ્યક્તિગત કામગીરી હોઈ શકે, જેમાં SbFore ઓપરેશન પહેલાં ડેટા સ્ટ્રક્ચરની સ્થિતિને સૂચવે છે અને ઓપરેશન o પૂર્ણ થયા પછી તેની સ્થિતિને સૂચવે છે. એકવાર φ પસંદ થઈ ગયા પછી, ઓપરેશન o માટેનો ઋણમુક્ત સમય એ રીતે વ્યાખ્યાયિત કરવામાં આવે છે કે જ્યાં C એ પ્રમાણસરતાનો બિન-નકારાત્મક અચળાંક (સમયના એકમોમાં) છે જે સમગ્ર વિશ્લેષણ દરમિયાન નિશ્ચિત રહેવો જોઈએ. એટલે કે, ઋણમુક્ત સમયને ઓપરેશન દ્વારા લેવામાં આવેલા વાસ્તવિક સમય વત્તા C ગુણ્યા ઓપરેશનને કારણે સંભવિતતામાં તફાવત તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. મોટા ઓ નોટેશનનો ઉપયોગ કરીને એસિમ્પ્ટોટિક કોમ્પ્યુટેશનલ જટિલતાનો અભ્યાસ કરતી વખતે, અચળ પરિબળો અપ્રસ્તુત હોય છે અને તેથી અચળાંક સી સામાન્ય રીતે અવગણવામાં આવે છે. ઋણમુક્ત અને વાસ્તવિક સમય વચ્ચેનો સંબંધ તેના કૃત્રિમ દેખાવ છતાં, કામગીરીના ક્રમનો કુલ ઋણમુક્ત સમય કામગીરીના સમાન ક્રમ માટે વાસ્તવિક સમય પર માન્ય ઉપલી સીમા પ્રદાન કરે છે. કામગીરીના કોઈપણ ક્રમ માટે, વ્યાખ્યાયિત કરો કેઃ કુલ ઋણમુક્ત સમયઃ કુલ વાસ્તવિક સમયઃ પછીઃ જ્યાં સંભવિત કાર્ય મૂલ્યોનો ક્રમ ટેલીસ્કોપિંગ શ્રેણી બનાવે છે જેમાં પ્રારંભિક અને અંતિમ સંભવિત કાર્ય મૂલ્યો સિવાયના તમામ શબ્દો જોડીમાં રદ થાય છે. આને ફરીથી ગોઠવતા, આપણે મેળવીએ છીએઃ ત્યારથી અને, તેથી ઋણમુક્ત સમયનો ઉપયોગ કામગીરીના ક્રમના વાસ્તવિક સમય પર સચોટ ઉપલી સીમા પ્રદાન કરવા માટે થઈ શકે છે, ભલે વ્યક્તિગત કામગીરી માટેનો ઋણમુક્ત સમય તેના વાસ્તવિક સમયથી વ્યાપક રીતે બદલાઈ શકે. સૌથી ખરાબ-કેસ ઇનપુટ્સનું ઋણમુક્ત વિશ્લેષણ સામાન્ય રીતે, ઋણમુક્ત વિશ્લેષણનો ઉપયોગ ઇનપુટ ક્રમ વિશેની સૌથી ખરાબ કેસ ધારણા સાથે કરવામાં આવે છે. આ ધારણા સાથે, જો X એ ઓપરેશનનો એક પ્રકાર છે જે ડેટા સ્ટ્રક્ચર દ્વારા કરી શકાય છે, અને n એ આપેલ ડેટા સ્ટ્રક્ચરના કદને વ્યાખ્યાયિત કરતો પૂર્ણાંક છે (ઉદાહરણ તરીકે, તેમાં સમાવિષ્ટ વસ્તુઓની સંખ્યા), તો પછી પ્રકાર X ની કામગીરી માટેનો ઋણમુક્ત સમય મહત્તમ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, કદ n ના ડેટા સ્ટ્રક્ચર્સ પરની કામગીરીના તમામ સંભવિત ક્રમમાં અને ક્રમમાં પ્રકાર X ની તમામ કામગીરીઓમાં, ઓપરેશન Oi માટે ઋણમુક્ત સમય. આ વ્યાખ્યા સાથે, કામગીરીનો ક્રમ કરવાના સમયનો અંદાજ તે પ્રકારની કામગીરીની સંખ્યા દ્વારા ક્રમમાં દરેક પ્રકારની કામગીરી માટે ઋણમુક્ત સમયનો ગુણાકાર કરીને કરી શકાય છે. ઉદાહરણો ડાયનેમિક એરે એ વસ્તુઓની શ્રેણી જાળવવા માટેનું ડેટા માળખું છે, જે એરેની અંદરની સ્થિતિને રેન્ડમ એક્સેસ અને એરેના કદને એક દ્વારા વધારવાની ક્ષમતા બંનેને મંજૂરી આપે છે. તે જાવામાં "એરે લિસ્ટ" પ્રકાર તરીકે અને પાયથોનમાં "સૂચિ" પ્રકાર તરીકે ઉપલબ્ધ છે. ડાયનેમિક એરેને ડેટા સ્ટ્રક્ચર દ્વારા અમલમાં મૂકી શકાય છે, જેમાં કેટલીક લંબાઈ N ની વસ્તુઓની એરે A હોય છે, જેમાં સંખ્યા 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 ઉમેરો. વાંચોઃ વર્તમાન કાઉન્ટર મૂલ્ય પરત કરો. આ ઉદાહરણ માટે, આપણે ટ્રાન્સડીકોટોમસ મશીન મોડેલનો ઉપયોગ કરી રહ્યાં નથી, પરંતુ તેના બદલે વૃદ્ધિમાં બિટ ઓપરેશન દીઠ સમયના એક એકમની જરૂર છે. અમે બતાવવા માંગીએ છીએ કે ઇન્ક ઓ (1) ઋણમુક્તિ સમય લે છે. આ રચનાનું વિશ્લેષણ સંભવિત કાર્યનો ઉપયોગ કરીને કરી શકાય છેઃ ± = બિટ્સની સંખ્યા-સમાન-થી-1 = હેમિંગવેઇટ (કાઉન્ટર) આ સંખ્યા હંમેશા બિન-નકારાત્મક હોય છે અને જરૂરિયાત મુજબ 0 થી શરૂ થાય છે. ઇન્ક ઓપરેશન સૌથી ઓછું નોંધપાત્ર ફેરવે છે. પછી, જો એલ. એસ. બી. ને 1 થી 0 પર પલટી દેવામાં આવે, તો પછીનો બીટ પણ પલટી જાય છે. આ ત્યાં સુધી ચાલે છે જ્યાં સુધી આખરે બીટ 0 થી 1 પર ફેરવવામાં ન આવે, તે સમયે ફ્લિપિંગ બંધ થાય છે. જો કાઉન્ટર શરૂઆતમાં k1 બિટ્સમાં સમાપ્ત થાય છે, તો આપણે કુલ k + 1 બિટ્સને ફેરવીએ છીએ, વાસ્તવિક સમય k + 1 લઈએ છીએ અને પોટેન્શિયલને k−1 ઘટાડીએ છીએ, તેથી ઋણમુક્ત સમય 2 છે. તેથી, એમ. આઈ. એન. સી. કામગીરી ચલાવવા માટેનો વાસ્તવિક સમય ઓ (એમ) છે. સંભવિત કાર્ય પદ્ધતિનો ઉપયોગ સામાન્ય રીતે ફિબોનાકી ઢગલાનું વિશ્લેષણ કરવા માટે થાય છે, જે અગ્રતા કતારનું એક સ્વરૂપ છે જેમાં વસ્તુને દૂર કરવામાં લઘુગણક ઋણમુક્તિ સમય લાગે છે, અને અન્ય તમામ કામગીરીઓ સતત ઋણમુક્તિ સમય લે છે. તેનો ઉપયોગ સ્પ્લે વૃક્ષોનું વિશ્લેષણ કરવા માટે પણ થઈ શકે છે, જે દ્વિસંગી શોધ વૃક્ષનું સ્વ-સમાયોજન સ્વરૂપ છે, જેમાં કામગીરી દીઠ લઘુગણક ઋણમુક્ત સમય હોય છે. અલ્ગોરિધમ્સનું સંદર્ભ વિશ્લેષણ