# வரிசையாக்கப் படிமுறை

## படிமுறைகளின் ஒப்பீடு

இந்த அட்டவணையில், *n* என்பது வரிசையாக்கம் செய்யப்பட்ட எண்ணிக்கையிலான பதிவுகளைக் குறிப்பிடுகிறது. “சராசரி” மற்றும் ”மோசமான” நெடுவரிசைகள் ஒவ்வொரு நிலையிலும் சிக்கலான நேரத்தை அளிக்கின்றன, கருத்தின் அடிப்படையில் ஒவ்வொரு சாவியின் நீளமும் நிலையானது, மேலும் அனைத்து ஒப்பீடுகள், மாறுதல்கள், மற்றும் மற்ற தேவைப்படும் செயல்பாடுகள் அனைத்தும் சீரான இடைவெளியில் அளிக்கப்பட்டு வருகின்றன. “நினைவகம்” பட்டியலின் உதவியுடன் துணைத் தேக்கத்தின் அளவை வரையறை செய்கிறது. தீட்டா, சிக்மா, பிக்-O, ஸ்மால்-o, மற்றும் பல்வேறு குறிமானங்களைப் பயன்படுத்திப் படிமுறைகளின் நேர ஓட்டம் மற்றும் நினைவகம் ஆகியவை அளவீடு செய்யப்படுகிறது. கீழ்காணும் நேர ஓட்டம் மற்றும் நினைவகம் ஆகியவை அனைத்து குறிமானங்களுக்கும் பொருந்தும்படியாக இருக்கின்றன.  
| குமிழி வரிசையாக்கம் | ஆம் | பரிமாற்றம் | நுணுக்கமான குறியீடு |
| --- | --- | --- | --- |
| கலப்பு வரிசையாக்கம் | ஆம் | பரிமாற்றம் |  |
| வாரி வரிசையாக்கம் | இல்லை | பரிமாற்றம் | சிறிய அளவிலான குறியீடு |
| ஜீனோம் வரிசையாக்கம் | ஆம் | பரிமாற்றம் | நுண்ணிய அளவிலான குறியீடு |
| தேர்ந்தெடுக்கும் வரிசையாக்கம் | சார்ந்தது | தேர்ந்தெடுத்தல் | அதன் நிலைப்புத்தன்மை வரையைறைச் சார்ந்ததாகும். |
| செருகும் வரிசையாக்கம் | ஆம் | செருகுதல் | மேலும் சராசரியான நிலையும் கூட<math>\mathcal{O}\( {n + d} \)</math>, *d* என்பது தலைகீழியின் எண்ணிக்கையாகும் |
| மறைமுக வரிசையாக்கம் | இல்லை | செருகுதல் | வரிசைப்படுத்துதல்=இடதுபுறமாக |
| ரும மர வரிசையாக்கம் | ஆம் | செருகுதல் | தானே சமநிலை செய்துகொள்ளும் தேடும் ரும மரத்தைப் பயன்படுத்தும்போது |
| நூலக வரிசையாக்கம் | ஆம் | செருகுதல் |  |
| சேர்ப்பு வரிசையாக்கம் | ஆம் | சேர்ப்பு | வரிசைப்படுத்துதல்=இடதுபுறமாக |
| சரியான சேர்ப்பு வரிசையாக்கம் | சார்ந்தது | சேர்ப்பு | எடுத்துக்காட்டான விளக்கப்படம் இங்கே: [http://citeseer.ist.psu.edu/472101.html ]; நிலையான பொருத்தமான சேர்ப்பின் அடிப்படையில் நிலையான வரிசையாக்கத்தைப் போல செய்து முடிக்க இயலும்: [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381 ] |
| குவியல் வரிசையாக்கம் | இல்லை | தேர்ந்தெடுத்தல் |  |
| மென்மையான வரிசையாக்கம் | இல்லை | தேர்ந்தெடுத்தல் | மாற்றியமைக்கும் வரிசைப்படுத்துதல் - <math>\mathcal{} {n} </math> ஏற்கனவே தரவு வரிசையாக்கம் செய்யப்பெற்று, <math>\mathcal{O}\( {0} \)</math> பரிமாற்றம் செய்யப்பட்டிருந்தால் ஒப்பீடு பயன்படுத்தப்படுகிறது. |
| விரைவு வரிசையாக்கம் | சார்ந்தது | பிரித்தல் | மையமானது எப்படிக் கையாளப்படுகிறது என்பதன் அடிப்படையில் நிலையான வரிசையாக்கத்தைப் போல செய்து முடிக்க இயலும். எளிமையான <math>\mathcal{O} \( n \)</math>வேறுபட்ட பயன்பாட்டினாலான இடைவெளி |
| உள்ளாய்வு வரிசையாக்கம் | இல்லை | கலப்பினம் | எஸ்ஜிஐ எஸ்டிஎல் திட்டங்களில் பயன்படுகிறது |
| நீண்ட வரிசையாக்கம் | இல்லை | செருகுதல் & தேர்ந்தெடுத்தல் | ஓ(*n* log *n* ) இற்குள் உள்ள அனைத்து நீண்ட அதிகரிக்கும் துணை வரிசைமுறைகளைக் கண்டறிதல் |
| திரிக்கும் வரிசையாக்கம் | ஆம் | தேர்ந்தெடுத்தல் |  |
| போட்டியிலான வரிசையாக்கம் | தேர்ந்தெடுத்தல் | } |  |  
பின்வரும் அட்டவணை ஒப்பீட்டு வரிசையாக்கம் அல்லாத வரிசையாக்கப் படிமுறையை வரையறுக்கிறது. அதே போல, அவைகள் ஒரு குறைந்த பிணைப்பினால் <math>\Omega\( {n \log n} \)</math> கட்டுப்படுத்தப்படுவது இல்லை. பின்வருவனவற்றுள் *n* , என்பது வரிசையாக்கம் செய்யப்பட்ட உருப்படிகளின் எண்ணிக்கையைக் குறிக்கிறது, *k* , என்பது ஒவ்வொரு சாவியின் அளவைக் குறிக்கிறது, மேலும் *s* , என்பது பயன்படுத்தப்படும் துண்டின் அளவைக் குறிக்கிறது. இவைகளில் பெரும்பாலானவை ஊகத்தின் அடிப்படையிலானவை என்பதுடன், சாவியின் அளவு போதுமான அளவைக் காட்டிலும் பெரியதாக இருந்தால் அனைத்துப் பதிவுகளும் ஒரே அளவிலான சாவியின் மதிப்புகளைக் கொண்டிருக்கும், இதிலிருந்து *n* << 2<sup>*k* </sup> என்றறியப்படுகிறது, மேலும் << என்பது “மிகவும் சிறியது” என்று பொருள்படும்.  
| தாமதமான வரிசையாக்கம் | <math>\mathcal{O}\( {n + 2^k} \)</math> | <math>\mathcal{O}\( {n + 2^k} \)</math> | <math>\mathcal{O}\( {2^k} \)</math> | ஆம் | ஆம் |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| கலன் வரிசையாக்கம் | <math>\mathcal{O}\( {n \cdot k} \)</math> | <math>\mathcal{O}\( {n^2 \cdot k} \)</math> | <math>\mathcal{O}\( {n \cdot k} \)</math> | ஆம் | இல்லை | அணியின் களத்திலிருந்து பெறப்படும் தனிமங்களைச் சீரான முறையில் வழங்குதல். |  |
| எண்ணும் வரிசையாக்கம் | <math>\mathcal{O}\( {n + 2^k} \)</math> | <math>\mathcal{O}\( {n + 2^k} \)</math> | <math>\mathcal{O}\( {n + 2^k} \)</math> | ஆம் | ஆம் |  |  |
| எல்எஸ்டி தோற்றுவாய் வரிசையாக்கம் | <math>\mathcal{O}\( {n \cdot \frac{k}{s}} \)</math> | <math>\mathcal{O}\( {n \cdot \frac{k}{s}} \)</math> | <math>\mathcal{O}\( n \)</math> | ஆம் | இல்லை |  |  |
| எம்எஸ்டி தோற்றுவாய் வரிசையாக்கம் | <math>\mathcal{O}\( {n \cdot \frac{k}{s}} \)</math> | <math>\mathcal{O}\( {n \cdot \frac{k}{s} \cdot 2^s} \)</math> | <math>\mathcal{O}\( {\frac{k}{s} \cdot 2^s} \)</math> | இல்லை | இல்லை |  |  |
| விரவிய வரிசையாக்கம் | <math>\mathcal{O}\( {n \cdot \frac{k}{s}} \)</math> | <math>\mathcal{O}\( {n \cdot \( {\frac{k}{s} + s} \) } \)</math> | <math>\mathcal{O}\( {\frac{k}{s} \cdot 2^s} \)</math> | இல்லை | இல்லை | கணிதரீதியான வழிமுறையனது n << 2<sup>k</sup> இன் ஊகத்தினாலாது, ஆனால் படிமுறைக்கு இது தேவைப்படுவதில்லை. | } |  
மிகவும் மோசமான செயல்பாடுகள் அல்லது தனித்தன்மை வாய்ந்த வன்பொருளுக்கான தேவையின் காரணமாக, பின்வரும் அட்டவணை உண்மையான வாழ்க்கைக்குப் பயன்படாத அனுபவமற்ற சில வரிசையாக்கப் படிமுறைகளை வரையறுக்கிறது.  
| அணியிலான வரிசையாக்கம் | குறிப்பு இல்லை | குறிப்பு இல்லை | — | குறிப்பு இல்லை | இல்லை | சிறப்பு வாய்ந்த வன்பொருள் தேவைப்படுகிறது |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| எளிய அகழிலான வரிசையாக்கம் | <math>\mathcal{} n </math> | <math>\mathcal{} n </math> | <math>\mathcal{} {\log n} </math> | இல்லை | ஆம் | எண்ணிக்கையிலான திருப்பங்களக் கணக்கிடுதல். |  |
| வரிசையாக்க வலைப்பின்னல்கள் | <math>\mathcal{} {\log n} </math> | <math>\mathcal{} {\log n} </math> | <math>\mathcal{} {n \cdot \log (n)} </math> | ஆம் | இல்லை | சுருள்களின் அளவிலான விதி தேவைப்படுகிது <math>\mathcal{O}\( n \cdot \log (n) \)</math> | } |  
கணிப்பொறி விஞ்ஞானிகள் காலச் சிக்கலுக்கு ஏற்றார் போல <math>\mathcal{O}\( {n \log n} \)</math> மற்ற சிறந்த வரிசையாக்கப் படிமுறைகளை அளித்தனர்:  
- ஹேனின் படிமுறை, சாவிகளை வரிசையாக்கம் செய்வதற்காக எல்லைக்குட்பட்டு செயல்படும் ஒரு வரையறுக்கப்பட்ட படிமுறை என்பதுடன், <math>\mathcal{O}\( {n \log \log n} \)</math> காலம் மற்றும் <math>\mathcal{O}\( {n} \)</math> இடைவெளியைப் பயன்படுத்திக்கொள்கிறது.
- தோர்ப்பின் படிமுறை, சாவிகளை வரிசையாக்கம் செய்வதற்காக எல்லைக்குட்படாமல் செயல்படும் ஒரு தொடர்பற்ற படிமுறை என்பதுடன், <math>\mathcal{O}\( {n \log \log n} \)</math> காலம் மற்றும் <math>\mathcal{O}\( {n} \)</math> இடைவெளியைப் பயன்படுத்திக்கொள்கிறது.
- முழு எண்ணிலான வரிசையாக்கப் படிமுறை காலம் மற்றும் <math>\mathcal{O}\( {n} \)</math> இடைவெளியைத் <math>\mathcal{O}\( {n \sqrt{\log \log n}} \)</math> தவிர்த்து மற்றதைப் பயன்படுத்திக்கொள்கிறது.