Potential method
கணக்கீட்டு சிக்கலான கோட்பாட்டில், சாத்தியமான முறை என்பது ஒரு தரவு கட்டமைப்பின் கடனளிக்கப்பட்ட நேரம் மற்றும் இட சிக்கலை பகுப்பாய்வு செய்யப் பயன்படுத்தப்படும் ஒரு முறையாகும், இது அரிதான ஆனால் விலையுயர்ந்த செயல்பாடுகளின் செலவை மென்மையாக்கும் செயல்பாடுகளின் வரிசைகளின் மீது அதன் செயல்திறனின் அளவீடு ஆகும். பணத்தைத் திருப்பிச் செலுத்தும் நேரத்தின் வரையறை சாத்தியமான முறையில், தரவு கட்டமைப்பின் நிலைகளை எதிர்மறை அல்லாத எண்களுக்கு வரைபடமாக்கும் ஒரு செயல்பாடு தேர்ந்தெடுக்கப்படுகிறது. S என்பது தரவு கட்டமைப்பின் ஒரு நிலையாக இருந்தால், கடனுதவி செய்யப்பட்ட பகுப்பாய்வில் கணக்கிடப்பட்ட ("பணம் செலுத்தப்பட்டது") ஆனால் இன்னும் செய்யப்படாத வேலையைக் குறிக்கிறது. எனவே, அந்த நிலையில் சேமிக்கப்படும் ஆற்றல் ஆற்றலின் அளவைக் கணக்கிடுவதாக φ (S) கருதப்படலாம். ஒரு தரவு கட்டமைப்பை துவக்குவதற்கான செயல்பாட்டிற்கு முந்தைய சாத்தியமான மதிப்பு பூஜ்ஜியமாக வரையறுக்கப்படுகிறது. மாற்றாக, φ (S) என்பது S நிலையில் உள்ள கோளாறின் அளவு அல்லது ஒரு சிறந்த நிலையில் இருந்து அதன் தூரத்தைக் குறிக்கிறது என்று கருதப்படலாம். சில தரவு கட்டமைப்பில் செயல்பாடுகளின் வரிசைக்குள் எந்தவொரு தனிப்பட்ட செயல்பாடும் இருக்கட்டும், செயல்பாட்டிற்கு முன் தரவு கட்டமைப்பின் நிலையை குறிக்கும் எஸ். பி. ஓ மற்றும் செயல்பாடு ஓ முடிந்த பிறகு அதன் நிலையை குறிக்கும் சாஃப்டர். φ தேர்ந்தெடுக்கப்பட்டவுடன், சி என்பது விகிதாசாரத்தின் (நேரத்தின் அலகுகளில்) எதிர்மறை அல்லாத மாறிலி, இது பகுப்பாய்வு முழுவதும் நிலையானதாக இருக்க வேண்டும். அதாவது, பணத்தைத் திருப்பிச் செலுத்தும் நேரம் என்பது செயல்பாட்டால் எடுக்கப்பட்ட உண்மையான நேரம் மற்றும் செயல்பாட்டால் ஏற்படும் ஆற்றலில் உள்ள வித்தியாசத்தின் சி மடங்கு என வரையறுக்கப்படுகிறது. பெரிய ஓ குறியீட்டைப் பயன்படுத்தி அறிகுறியற்ற கணக்கீட்டு சிக்கலைப் படிக்கும்போது, நிலையான காரணிகள் பொருத்தமற்றவை, எனவே மாறிலி சி பொதுவாக தவிர்க்கப்படுகிறது. கடனுதவி மற்றும் உண்மையான நேரத்திற்கு இடையிலான உறவு அதன் செயற்கை தோற்றம் இருந்தபோதிலும், செயல்பாடுகளின் வரிசையின் மொத்த கடனுதவி நேரம் அதே செயல்பாடுகளின் வரிசைக்கு உண்மையான நேரத்தில் செல்லுபடியாகும் மேல் வரம்பை வழங்குகிறது. செயல்பாடுகளின் எந்தவொரு வரிசைக்கும், வரையறுக்கவும்ஃ மொத்த கடன்தொகை நேரம்ஃ மொத்த உண்மையான நேரம்ஃ பின்னர்ஃ சாத்தியமான செயல்பாட்டு மதிப்புகளின் வரிசை ஒரு தொலைநோக்கி தொடரை உருவாக்குகிறது, இதில் ஆரம்ப மற்றும் இறுதி சாத்தியமான செயல்பாட்டு மதிப்புகளைத் தவிர மற்ற அனைத்து சொற்களும் ஜோடிகளாக ரத்து செய்யப்படுகின்றன. இதை மறுசீரமைத்தால், நாம் பெறுவதுஃ முதல் மற்றும், எனவே ஒரு தனிப்பட்ட செயல்பாட்டிற்கான கடன்தொகை நேரம் அதன் உண்மையான நேரத்திலிருந்து பரவலாக மாறுபடலாம் என்றாலும், செயல்பாடுகளின் வரிசையின் உண்மையான நேரத்தில் துல்லியமான மேல் வரம்பை வழங்க கடன்தொகை நேரத்தைப் பயன்படுத்தலாம். மோசமான-வழக்கு உள்ளீடுகளின் கடன்தொகை பகுப்பாய்வு பொதுவாக, கடன்தொகை பகுப்பாய்வு உள்ளீட்டு வரிசை பற்றிய மோசமான வழக்கு அனுமானத்துடன் இணைந்து பயன்படுத்தப்படுகிறது. இந்த அனுமானத்துடன், X என்பது தரவு கட்டமைப்பால் செய்யப்படக்கூடிய ஒரு வகை செயல்பாடாகவும், n என்பது கொடுக்கப்பட்ட தரவு கட்டமைப்பின் அளவை வரையறுக்கும் ஒரு முழு எண்ணாகவும் இருந்தால் (எடுத்துக்காட்டாக, அதில் உள்ள உருப்படிகளின் எண்ணிக்கை), பின்னர் வகை X இன் செயல்பாடுகளுக்கான கடன்தொகை நேரம் அதிகபட்சமாக வரையறுக்கப்படுகிறது, அளவு n இன் தரவு கட்டமைப்புகளில் செயல்பாடுகளின் அனைத்து சாத்தியமான வரிசைகளிலும் மற்றும் வரிசைக்குள் வகை X இன் அனைத்து செயல்பாடுகளிலும், செயல்பாட்டிற்கான கடன்தொகை நேரத்தின் கடன்தொகை நேரமாகும். இந்த வரையறையின் மூலம், ஒவ்வொரு வகை செயல்பாட்டிற்கும் வரிசைப்படுத்தப்பட்ட நேரத்தை அந்த வகை செயல்பாடுகளின் எண்ணிக்கையால் பெருக்குவதன் மூலம் செயல்பாடுகளின் வரிசையைச் செய்வதற்கான நேரத்தை மதிப்பிடலாம். எடுத்துக்காட்டுகள் டைனமிக் வரிசை ஒரு டைனமிக் வரிசை என்பது உருப்படிகளின் வரிசையை பராமரிப்பதற்கான ஒரு தரவு கட்டமைப்பாகும், இது வரிசைக்குள் உள்ள நிலைகளுக்கு சீரற்ற அணுகல் மற்றும் வரிசை அளவை ஒன்றால் அதிகரிக்கும் திறன் ஆகிய இரண்டையும் அனுமதிக்கிறது. இது ஜாவாவில் "அரே லிஸ்ட்" வகையாகவும், பைத்தானில் "லிஸ்ட்" வகையாகவும் கிடைக்கிறது. ஒரு மாறும் வரிசை ஒரு தரவு கட்டமைப்பால் செயல்படுத்தப்படலாம், இதில் ஒரு வரிசை A உருப்படிகள் உள்ளன, சில நீளம் N, ஒரு எண்ணுடன் n ≤ N இதுவரை பயன்படுத்தப்பட்ட வரிசைக்குள் உள்ள நிலைகளைக் குறிக்கிறது. இந்த கட்டமைப்பின் மூலம், டைனமிக் வரிசைக்கான சீரற்ற அணுகல்கள் உள் வரிசை A இன் அதே கலத்தை அணுகுவதன் மூலம் செயல்படுத்தப்படலாம், மேலும் n <N போது டைனமிக் வரிசை அளவை அதிகரிக்கும் ஒரு செயல்பாடு வெறுமனே n ஐ அதிகரிப்பதன் மூலம் செயல்படுத்தப்படலாம். இருப்பினும், n = N போது, A ஐ மறுஅளவிடுவது அவசியம், அவ்வாறு செய்வதற்கான ஒரு பொதுவான உத்தி அதன் அளவை இரட்டிப்பாக்குவது, A ஐ 2n நீளத்தின் புதிய வரிசையால் மாற்றுவதாகும். இந்த கட்டமைப்பை சாத்தியமான செயல்பாட்டைப் பயன்படுத்தி பகுப்பாய்வு செய்யலாம்ஃ மறுஅளவிடுதல் உத்தி எப்போதும் 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 ஆகும். எனவே, எம் இன்க் செயல்பாடுகளை இயக்குவதற்கான உண்மையான நேரம் ஓ (எம்) ஆகும். பயன்பாடுகள் ஃபைபோனாச்சி குவியல்களை பகுப்பாய்வு செய்ய சாத்தியமான செயல்பாட்டு முறை பொதுவாகப் பயன்படுத்தப்படுகிறது, இது முன்னுரிமை வரிசையின் ஒரு வடிவமாகும், இதில் ஒரு பொருளை அகற்றுவதற்கு மடக்கை கடன்தொகை நேரம் எடுக்கும், மேலும் மற்ற அனைத்து செயல்பாடுகளும் நிலையான கடன்தொகை நேரத்தை எடுக்கும். பிளே மரங்களை பகுப்பாய்வு செய்வதற்கும் இது பயன்படுத்தப்படலாம், இது பைனரி தேடல் மரத்தின் சுய சரிசெய்தல் வடிவமாகும், இது ஒரு செயல்பாட்டிற்கு மடக்கை கடன்தொகை நேரத்துடன் உள்ளது. வழிமுறைகளின் குறிப்புகள் பகுப்பாய்வு