பெரிய O குறியீட்டைப் புரிந்துகொள்வதும் தீர்மானிப்பதும்

பெரிய O குறியீட்டு முறை என்பது கணினி அறிவியலில் ஒரு அடிப்படைக் கருத்தாகும், இது ஒரு வழிமுறையின் செயல்திறன் அல்லது சிக்கலான தன்மையை விவரிக்கப் பயன்படுகிறது. உள்ளீட்டு அளவு அதிகரிக்கும் போது ஒரு வழிமுறையின் வள பயன்பாட்டின் (பொதுவாக நேரம் அல்லது இடம்) வளர்ச்சி விகிதத்தில் ஒரு மேல் வரம்பை வழங்குகிறது. முக்கியமாக, பெரிய O வள பயன்பாட்டைக் குறிக்கும் செயல்பாட்டின் ஆதிக்கம் செலுத்தும் சொல் மீது கவனம் செலுத்துகிறது மற்றும் நிலையான காரணிகள் மற்றும் கீழ்-வரிசை சொற்களை புறக்கணிக்கிறது*. இதன் பொருள், ஒரு குறிப்பிட்ட கணினியில் அதன் துல்லியமான செயல்பாட்டு நேரத்தை அல்ல, பெரிய உள்ளீடுகளுடன் வழிமுறை எவ்வாறு அளவிடுகிறது என்பதில் நாங்கள் ஆர்வமாக உள்ளோம்.

பெரிய O ஏன் முக்கியமானது?

• வழிமுறை ஒப்பீடு: பெரிய O ஒரே சிக்கலைத் தீர்க்கும் வெவ்வேறு வழிமுறைகளின் செயல்திறனை ஒப்பிட அனுமதிக்கிறது. O(n) வழிமுறை பெரிய மாறிலி காரணியைக் கொண்டிருந்தாலும், O(n) உடன் ஒரு வழிமுறை பொதுவாக பெரிய உள்ளீடுகளுக்கு O(n²) உடன் ஒன்றை விட சிறந்தது.
• அளவிடுதல் கணிப்பு: உள்ளீட்டு அளவு அதிகரிக்கும்போது ஒரு வழிமுறை எவ்வாறு செயல்படும் என்பதைக் கணிக்க பிக் O-ஐப் புரிந்துகொள்வது உதவுகிறது. அதிக அளவிலான தரவைக் கையாளக்கூடிய அமைப்புகளை வடிவமைப்பதற்கு இது மிகவும் முக்கியமானது.
• தடை அடையாளம் காணல்: பிக் O பகுப்பாய்வு ஒரு நிரலின் மிகவும் வள-தீவிர பகுதிகளை துல்லியமாகக் கண்டறிய உதவும், இது உகப்பாக்க முயற்சிகளை வழிநடத்துகிறது.
• தரப்படுத்தப்பட்ட மொழி: அல்காரிதமிக் செயல்திறனைப் பற்றி விவாதிக்க பிக் O ஒரு பொதுவான, இயந்திர-சுயாதீன மொழியை வழங்குகிறது.

பொதுவான பிக் O குறிப்புகள் (சிறந்தது முதல் மோசமானது வரை):

பொதுவான பிக் O சிக்கல்களின் பட்டியல் இங்கே, மிகவும் முதல் குறைந்த செயல்திறன் வரை வரிசைப்படுத்தப்பட்டுள்ளது:

• O(1) - நிலையான நேரம்: உள்ளீட்டு அளவைப் பொருட்படுத்தாமல் அல்காரிதம் அதே அளவு நேரத்தை எடுக்கும். எடுத்துக்காட்டுகள்: ஒரு வரிசையில் ஒரு உறுப்பை அதன் குறியீட்டால் அணுகுவது, எளிய எண்கணித செயல்பாடுகள். O(log n) - மடக்கை நேரம்: உள்ளீட்டு அளவுடன் எடுக்கப்பட்ட நேரம் மடக்கை ரீதியாக அதிகரிக்கிறது. இது மிகவும் திறமையானது. எடுத்துக்காட்டுகள்: வரிசைப்படுத்தப்பட்ட வரிசையில் பைனரி தேடல். தேடல் இடத்தை மீண்டும் மீண்டும் பாதியாகக் குறைப்பதைப் பற்றி சிந்தியுங்கள்.
• O(n) - நேரியல் நேரம்: உள்ளீட்டு அளவுடன் எடுத்துக்கொள்ளும் நேரம் நேரியல் முறையில் அதிகரிக்கிறது. எடுத்துக்காட்டுகள்: ஒரு வரிசையின் வழியாக ஒரு முறை மீண்டும் மீண்டும் செய்வது, வரிசைப்படுத்தப்படாத வரிசையில் அதிகபட்ச உறுப்பைக் கண்டறிதல்.
• O(n log n) - நேரியல் நேரம்: நேரியல் மற்றும் மடக்கையின் கலவை. பெரும்பாலும் திறமையான வரிசையாக்க வழிமுறைகளில் காணப்படுகிறது. எடுத்துக்காட்டுகள்: ஒன்றிணைத்தல் வரிசைப்படுத்துதல், விரைவு வரிசைப்படுத்துதல் (சராசரியாக), குவியல் வரிசைப்படுத்துதல்.
• O(n²) - இருபடி நேரம்: எடுத்துக்கொள்ளும் நேரம் உள்ளீட்டு அளவின் வர்க்கத்திற்கு விகிதாசாரமாக அதிகரிக்கிறது. உள்ளீட்டு சுழல்களுடன் பொதுவானது. எடுத்துக்காட்டுகள்: குமிழி வரிசைப்படுத்துதல், செருகும் வரிசைப்படுத்துதல், தேர்வு வரிசைப்படுத்துதல்.
• O(n³) - கனசதுர நேரம்: உள்ளீட்டு அளவின் கனசதுரத்திற்கு விகிதாசாரமாக எடுத்துக்கொள்ளும் நேரம். மூன்று உள்ளீட்டு சுழல்கள் ஒரு பொதுவான மூலமாகும். O(2ⁿ) - அதிவேக நேரம்: உள்ளீட்டில் ஒவ்வொரு கூட்டலுடனும் எடுத்துக்கொள்ளும் நேரம் இரட்டிப்பாகிறது. இந்த வழிமுறைகள் மிக விரைவாக மிக மெதுவாக மாறும். எடுத்துக்காட்டுகள்: சுழல்நிலை ஃபைபோனச்சி (அப்பாவியாக செயல்படுத்தல்), ஒரு தொகுப்பின் அனைத்து துணைக்குழுக்களையும் கண்டறிதல்.
• O(n!) - காரணியாலான நேரம்: உள்ளீட்டு அளவைப் பொறுத்து எடுக்கும் நேரம் காரணியாலானதாக வளர்கிறது. இவை மிகச்சிறிய உள்ளீடுகளைத் தவிர வேறு எதற்கும் மிகவும் திறமையற்றவை. எடுத்துக்காட்டுகள்: ஒரு சரத்தின் அனைத்து வரிசைமாற்றங்களையும் கண்டறிதல்.

பெரிய O குறியீட்டை எவ்வாறு தீர்மானிப்பது (பொது விதிகள்)

குறியீட்டுத் துணுக்கின் பெரிய O குறியீட்டைத் தீர்மானிப்பதற்கான படிப்படியான அணுகுமுறை இங்கே:

1. உள்ளீட்டை அடையாளம் காணவும்: "உள்ளீட்டு அளவு" (பொதுவாக 'n' ஆல் குறிப்பிடப்படுகிறது) என்ன என்பதைத் தீர்மானிக்கவும். இது ஒரு வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை, ஒரு சரத்தின் நீளம், ஒரு தரவு கட்டமைப்பின் அளவு போன்றவற்றைக் கொண்டிருக்கலாம்.

2. சுழல்களை பகுப்பாய்வு செய்யுங்கள்: ஒற்றை வளையம்: உள்ளீட்டின் வழியாக மீண்டும் மீண்டும் செல்லும் ஒரு வளையம் பொதுவாக O(n) சிக்கலை பங்களிக்கிறது.

• நெஸ்டட் லூப்கள்: நெஸ்டட் லூப்கள் பொதுவாக சிக்கல்களைப் பெருக்குகின்றன. ஒரே உள்ளீட்டின் மீது மீண்டும் மீண்டும் வரும் இரண்டு நெஸ்டட் லூப்கள் O(n²) ஆகும். மூன்று நெஸ்டட் லூப்கள் O(n³) மற்றும் பல.
• மடக்கை நடத்தையுடன் கூடிய சுழற்சி: ஒரு வளையம் உள்ளீட்டு அளவை ஒரு நிலையான காரணியால் (எ.கா., பைனரி தேடல்) மீண்டும் மீண்டும் வகுத்தால், அது O(log n) சிக்கலை பங்களிக்கும்.

3. செயல்பாட்டு அழைப்புகளை பகுப்பாய்வு செய்யவும்: சுழல்நிலை அழைப்புகள்: சுழல்நிலை செயல்பாடுகளின் சிக்கலானது சுழல்நிலை அழைப்புகளின் எண்ணிக்கை மற்றும் ஒவ்வொரு அழைப்பிலும் செய்யப்படும் வேலையைப் பொறுத்தது. முதன்மை தேற்றம் போன்ற நுட்பங்கள் சுழல்நிலை செயல்பாடுகளை பகுப்பாய்வு செய்ய உதவும். எளிய சுழல்நிலை செயல்பாடுகள் அதிவேகமாக (O(2ⁿ)) அல்லது காரணியாலானதாக (O(n!)) இருக்கலாம்.

• பிற செயல்பாட்டு அழைப்புகள்: உங்கள் குறியீடு மற்ற செயல்பாடுகளை அழைத்தால், நீங்கள் அவற்றின் பெரிய O சிக்கல்களைக் கருத்தில் கொள்ள வேண்டும். நீங்கள் ஒரு O(n) வளையத்திற்குள் ஒரு O(n²) செயல்பாட்டை அழைத்தால், ஒட்டுமொத்த சிக்கலானது O(n³) ஆக மாறும்.

4. கான்ஸ்டன்ட்களை கைவிடவும்: நிலையான காரணிகளைப் புறக்கணிக்கவும். O(2n) மற்றும் O(n) இரண்டும் O(n) எனக் கருதப்படுகின்றன. பெரிய O என்பது வளர்ச்சி விகிதத்தைப் பற்றியது, துல்லியமான நேரத்தைப் பற்றியது அல்ல.

5. கீழ்-வரிசை சொற்களை விடுங்கள்: ஆதிக்கச் சொல்லை மட்டும் வைத்திருங்கள். எடுத்துக்காட்டாக, O(n² + n) என்பது O(n²) ஆக எளிமைப்படுத்தப்பட்டுள்ளது, ஏனெனில் n² n ஐ விட மிக வேகமாக வளர்கிறது.

6. சிறந்த, சராசரி மற்றும் மோசமான நிகழ்வு: மோசமான நிகழ்வு சிக்கலானது: மிகவும் பொதுவான மற்றும் பொதுவாக மிக முக்கியமான நிகழ்வு. இது வழிமுறையின் வள பயன்பாட்டில் ஒரு மேல் வரம்பை வழங்குகிறது. "பெரிய O" என்று நாம் கூறும்போது இதைத்தான் பொதுவாகக் குறிக்கிறோம்.

• சராசரி-வழக்கு சிக்கலானது: பல ரன்களில் எதிர்பார்க்கப்படும் செயல்திறனை விவரிக்கிறது. பெரும்பாலும் துல்லியமாக தீர்மானிக்க கடினமாக உள்ளது.
• சிறந்த நிகழ்வு சிக்கலானது: மிகவும் திறமையான சூழ்நிலையை விவரிக்கிறது. இது வழக்கமான செயல்திறனைக் குறிக்காததால், நடைமுறையில் குறைவான பயனுள்ளதாக இருக்கும்.

எடுத்துக்காட்டுகள்

சில குறியீடு துணுக்குகளை பகுப்பாய்வு செய்வோம்:

எடுத்துக்காட்டு 1: ஒரு வரிசை உறுப்பை அணுகுதல்

function getElement(arr, index) {
return arr[index];
}

• உள்ளீடு: வரிசை arr மற்றும் குறியீடு. வரிசையின் அளவு (arr.length) என்பது உள்ளீட்டு அளவு 'n' ஆகும்.
• பகுப்பாய்வு: வரிசையின் அளவைப் பொருட்படுத்தாமல், குறியீட்டின் மூலம் ஒரு வரிசை உறுப்பை அணுகுவதற்கு நிலையான நேரம் எடுக்கும். பெரிய O: O(1)

எடுத்துக்காட்டு 2: நேரியல் தேடல்

function linearSearch(arr, target) {
for (let i = 0; i <arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}

• உள்ளீடு: வரிசை arr மற்றும் இலக்கு. வரிசையின் அளவு (arr.length) 'n' ஆகும். *பகுப்பாய்வு: வளையம் அதிகபட்சம் 'n' நேரங்களில் (வரிசையின் நீளம்) மீண்டும் நிகழ்கிறது.
• பெரிய O: O(n)

எடுத்துக்காட்டு 3: உள்ளமைக்கப்பட்ட சுழல்கள் (குமிழி வரிசைப்படுத்துதல்)

function bubbleSort(arr) {
for (let i = 0; i <arr.length; i++) {
for (let j = 0; j <arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// கூறுகளை மாற்றவும்
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}

}
}

return arr;
}

• உள்ளீடு: வரிசை arr. வரிசையின் அளவு (arr.length) 'n'. *பகுப்பாய்வு: எங்களிடம் இரண்டு உள்ளமைக்கப்பட்ட சுழல்கள் உள்ளன. வெளிப்புற வளையம் 'n' முறை இயங்கும். உள் வளையம் தோராயமாக 'n' மடங்கு இயங்கும் (ஒவ்வொரு வெளிப்புற வளைய மறு செய்கையிலும் இது சிறிது குறைகிறது, ஆனால் இது நாம் புறக்கணிக்கக்கூடிய ஒரு கீழ்-வரிசை சொல்). எனவே, ஆதிக்க செயல்பாடு (ஒப்பீடு) தோராயமாக n * n = n² முறை செயல்படுத்தப்படுகிறது.
• பெரிய O: O(n²)

எடுத்துக்காட்டு 4: பைனரி தேடல்

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

• உள்ளீடு: வரிசைப்படுத்தப்பட்ட வரிசை arr மற்றும் இலக்கு. வரிசையின் அளவு (arr.length) 'n' ஆகும்.
• பகுப்பாய்வு: while வளையத்தின் ஒவ்வொரு மறு செய்கையிலும், தேடல் இடத்தை திறம்பட பாதியாகக் குறைக்கிறோம். இலக்கு கண்டுபிடிக்கப்படும் வரை அல்லது தேடல் இடம் காலியாக இருக்கும் வரை இந்தப் பாதியாகக் குறைப்பு தொடர்கிறது. 'n' ஐ எத்தனை முறை பாதியாகக் குறைக்க முடியும் என்பது log₂(n) (மடக்கை அடிப்படை 2).
• பெரிய O: O(log n)

எடுத்துக்காட்டு 5: சுழல்நிலை Fibonacci (Naive)

function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}

• உள்ளீடு: முழு எண் n.
• பகுப்பாய்வு: fibonacci(n) (இங்கு n > 1) என்ற ஒவ்வொரு அழைப்பிற்கும், நாம் இரண்டு கூடுதல் சுழல்நிலை அழைப்புகளைச் செய்கிறோம். இது ஒரு கிளைக்கும் அழைப்பு மரத்தை உருவாக்குகிறது. 'n' இல் ஒவ்வொரு அதிகரிப்பும் அழைப்புகளின் எண்ணிக்கை தோராயமாக இரட்டிப்பாகிறது. பெரிய O: O(2ⁿ) (இது ஒரு எளிமைப்படுத்தல். உண்மையான சிக்கலானது O(1.618ⁿ) க்கு அருகில் உள்ளது, ஆனால் ஆதிக்கம் செலுத்தும் சொல் அதிவேகமானது.)

எடுத்துக்காட்டு 6: ஒரு வளையத்திற்குள் செயல்பாட்டு அழைப்பு

function doSomething(arr) {
  for (let i = 0; i <arr.length; i++) {
    anotherFunction(arr[i]);
  }
}

function anotherFunction(value){
  for (let j=0; j<value; j++){
    console.log(j);
  }
}

• உள்ளீடு: arr, இங்கு n = arr.length பகுப்பாய்வு:
• doSomething என்பது n முறை மீண்டும் நிகழ்கிறது.
• anotherFunction, சுழற்சியின் உள்ளே, சிக்கலான O(m) ஐக் கொண்டுள்ளது, இங்கு m என்பது உள்ளீட்டு மதிப்பு இன் அளவு. மோசமான நிலையில், மதிப்பு n க்கு விகிதாசாரமாக இருக்கலாம். எனவே anotherFunction O(n) ஆகும்
• anotherFunction என்பது doSomething இன் வளையத்திற்குள் அழைக்கப்படுவதால், சிக்கல்கள் பெருகும்.
• பெரிய O: O(n * n) = O(n²)

முடிவு

பெரிய O குறியீட்டை தீர்மானிப்பது எந்தவொரு நிரலாளருக்கும் ஒரு முக்கியமான திறமையாகும். ஆதிக்க செயல்பாடுகளை அடையாளம் காண்பது, சுழல்கள் மற்றும் செயல்பாட்டு அழைப்புகளை பகுப்பாய்வு செய்வது மற்றும் வளர்ச்சி விகிதங்களில் கவனம் செலுத்துவது ஆகியவற்றின் அடிப்படைக் கொள்கைகளைப் புரிந்துகொள்வதன் மூலம், உங்கள் வழிமுறைகளின் செயல்திறனை திறம்பட மதிப்பீடு செய்து ஒப்பிட்டுப் பார்க்கலாம் மற்றும் தகவலறிந்த வடிவமைப்பு முடிவுகளை எடுக்கலாம். உங்கள் புரிதலை உறுதிப்படுத்த குறியீடு துணுக்குகளை பகுப்பாய்வு செய்வதைப் பயிற்சி செய்ய நினைவில் கொள்ளுங்கள்.