ബിഗ് ഒ നൊട്ടേഷൻ മനസ്സിലാക്കലും നിർണ്ണയിക്കലും

ബിഗ് ഒ നൊട്ടേഷൻ എന്നത് കമ്പ്യൂട്ടർ സയൻസിൽ ഒരു അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത അല്ലെങ്കിൽ സങ്കീർണ്ണത വിവരിക്കാൻ ഉപയോഗിക്കുന്ന ഒരു അടിസ്ഥാന ആശയമാണ്. ഇൻപുട്ട് വലുപ്പം വർദ്ധിക്കുന്നതിനനുസരിച്ച് ഒരു അൽഗോരിതത്തിന്റെ റിസോഴ്‌സ് ഉപയോഗത്തിന്റെ (സാധാരണയായി സമയം അല്ലെങ്കിൽ സ്ഥലം) വളർച്ചാ നിരക്കിൽ ഇത് ഒരു ഉയർന്ന പരിധി നൽകുന്നു. നിർണായകമായി, ബിഗ് ഒ റിസോഴ്‌സ് ഉപയോഗത്തെ പ്രതിനിധീകരിക്കുന്ന ഫംഗ്‌ഷന്റെ പ്രബലമായ പദത്തിൽ ശ്രദ്ധ കേന്ദ്രീകരിക്കുകയും സ്ഥിരമായ ഘടകങ്ങളെയും താഴ്ന്ന ഓർഡർ പദങ്ങളെയും അവഗണിക്കുകയും ചെയ്യുന്നു. ഇതിനർത്ഥം ഒരു പ്രത്യേക മെഷീനിൽ അതിന്റെ കൃത്യമായ നിർവ്വഹണ സമയത്തിലല്ല, വലിയ ഇൻപുട്ടുകൾ ഉപയോഗിച്ച് അൽഗോരിതം എങ്ങനെ സ്കെയിൽ ചെയ്യുന്നു എന്നതിലാണ് ഞങ്ങൾക്ക് താൽപ്പര്യമുള്ളത് എന്നാണ്.

ബിഗ് ഒ എന്തുകൊണ്ട് പ്രധാനമാണ്?

അൽഗോരിതം താരതമ്യം: ഒരേ പ്രശ്നം പരിഹരിക്കുന്ന വ്യത്യസ്ത അൽഗോരിതങ്ങളുടെ കാര്യക്ഷമത താരതമ്യം ചെയ്യാൻ ബിഗ് ഒ നമ്മെ അനുവദിക്കുന്നു. O(n) അൽഗോരിതത്തിന് വലിയ സ്ഥിരാങ്ക ഘടകം ഉണ്ടെങ്കിലും, വലിയ ഇൻപുട്ടുകൾക്ക് O(n²) ഉള്ളതിനേക്കാൾ O(n) ഉള്ള ഒരു അൽഗോരിതം പൊതുവെ മികച്ചതാണ്.
സ്കേലബിലിറ്റി പ്രവചനം: ഇൻപുട്ട് വലുപ്പം വളരുന്നതിനനുസരിച്ച് ഒരു അൽഗോരിതം എങ്ങനെ പ്രവർത്തിക്കുമെന്ന് പ്രവചിക്കാൻ ബിഗ് ഒ മനസ്സിലാക്കുന്നത് സഹായിക്കുന്നു. വലിയ അളവിലുള്ള ഡാറ്റ കൈകാര്യം ചെയ്യാൻ കഴിയുന്ന സിസ്റ്റങ്ങൾ രൂപകൽപ്പന ചെയ്യുന്നതിന് ഇത് നിർണായകമാണ്.
ബോട്ടിൽനെക്ക് ഐഡന്റിഫിക്കേഷൻ: ഒപ്റ്റിമൈസേഷൻ ശ്രമങ്ങളെ നയിക്കുന്ന ഒരു പ്രോഗ്രാമിന്റെ ഏറ്റവും റിസോഴ്‌സ്-ഇന്റൻസീവ് ഭാഗങ്ങൾ കൃത്യമായി കണ്ടെത്താൻ ബിഗ് ഒ വിശകലനം സഹായിക്കും.
സ്റ്റാൻഡേർഡൈസ്ഡ് ലാംഗ്വേജ്: അൽഗോരിതമിക് പ്രകടനം ചർച്ച ചെയ്യുന്നതിന് ബിഗ് ഒ ഒരു പൊതുവായ, മെഷീൻ-സ്വതന്ത്ര ഭാഷ നൽകുന്നു.

പൊതുവായ ബിഗ് ഒ നൊട്ടേഷനുകൾ (മികച്ചതിൽ നിന്ന് മോശം വരെ):

ഏറ്റവും കാര്യക്ഷമത കുറഞ്ഞതിൽ നിന്ന് കാര്യക്ഷമത കുറഞ്ഞതിലേക്ക് ക്രമീകരിച്ചിരിക്കുന്ന പൊതുവായ ബിഗ് ഒ സങ്കീർണ്ണതകളുടെ ഒരു ലിസ്റ്റ് ഇതാ:

O(1) - സ്ഥിരമായ സമയം: ഇൻപുട്ട് വലുപ്പം പരിഗണിക്കാതെ തന്നെ അൽഗോരിതം ഒരേ സമയം എടുക്കുന്നു. ഉദാഹരണങ്ങൾ: ഒരു അറേയിലെ ഒരു എലമെന്റിനെ അതിന്റെ സൂചിക ഉപയോഗിച്ച് ആക്‌സസ് ചെയ്യുന്നു, ലളിതമായ ഗണിത പ്രവർത്തനങ്ങൾ.
O(log n) - ലോഗരിഥമിക് സമയം: ഇൻപുട്ട് വലുപ്പത്തിനനുസരിച്ച് എടുക്കുന്ന സമയം ലോഗരിതമിക് ആയി വർദ്ധിക്കുന്നു. ഇത് വളരെ കാര്യക്ഷമമാണ്. ഉദാഹരണങ്ങൾ: അടുക്കിയ അറേയിലെ ബൈനറി തിരയൽ. തിരയൽ സ്ഥലം ആവർത്തിച്ച് പകുതിയാക്കുന്നതിനെക്കുറിച്ച് ചിന്തിക്കുക.
O(n) - ലീനിയർ സമയം: ഇൻപുട്ട് വലുപ്പത്തിനനുസരിച്ച് എടുക്കുന്ന സമയം രേഖീയമായി വർദ്ധിക്കുന്നു. ഉദാഹരണങ്ങൾ: ഒരു അറേയിലൂടെ ഒരിക്കൽ ആവർത്തിക്കുക, അടുക്കാത്ത അറേയിലെ പരമാവധി ഘടകം കണ്ടെത്തുക.
O(n log n) - ലീനിയറിഥമിക് സമയം: ലീനിയറിന്റെയും ലോഗരിഥമിക്യുടെയും സംയോജനം. പലപ്പോഴും കാര്യക്ഷമമായ സോർട്ടിംഗ് അൽഗോരിതങ്ങളിൽ കാണപ്പെടുന്നു. ഉദാഹരണങ്ങൾ: ലയിപ്പിക്കൽ അടുക്കൽ, ദ്രുതക്രമീകരണം (ശരാശരി), ഹീപ്പ് സോർട്ട്.
O(n²) - ക്വാഡ്രാറ്റിക് സമയം: എടുക്കുന്ന സമയം ഇൻപുട്ട് വലുപ്പത്തിന്റെ വർഗ്ഗത്തിന് ആനുപാതികമായി വർദ്ധിക്കുന്നു. നെസ്റ്റഡ് ലൂപ്പുകളിൽ സാധാരണമാണ്. ഉദാഹരണങ്ങൾ: ബബിൾ അടുക്കൽ, ഉൾപ്പെടുത്തൽ അടുക്കൽ, തിരഞ്ഞെടുക്കൽ അടുക്കൽ.
O(n³) - ക്യൂബിക് സമയം: ഇൻപുട്ട് വലുപ്പത്തിന്റെ ക്യൂബിന് ആനുപാതികമായി എടുക്കുന്ന സമയം വർദ്ധിക്കുന്നു. ട്രിപ്പിൾ നെസ്റ്റഡ് ലൂപ്പുകൾ ഒരു പൊതു ഉറവിടമാണ്. O(2ⁿ) - എക്സ്പോണൻഷ്യൽ സമയം: ഇൻപുട്ടിലേക്ക് ഓരോ കൂട്ടിച്ചേർക്കലിലും എടുക്കുന്ന സമയം ഇരട്ടിയാകുന്നു. ഈ അൽഗോരിതങ്ങൾ വളരെ വേഗത്തിൽ വളരെ മന്ദഗതിയിലാകുന്നു. ഉദാഹരണങ്ങൾ: ആവർത്തന ഫിബൊനാച്ചി (നൈവ് ഇംപ്ലിമെന്റേഷൻ), ഒരു സെറ്റിന്റെ എല്ലാ ഉപസെറ്റുകളും കണ്ടെത്തൽ.
O(n!) - ഫാക്റ്റോറിയൽ സമയം: ഇൻപുട്ട് വലുപ്പത്തിനനുസരിച്ച് എടുക്കുന്ന സമയം ഫാക്റ്റോറിയൽ ആയി വർദ്ധിക്കുന്നു. ഏറ്റവും ചെറിയ ഇൻപുട്ടുകൾക്ക് ഒഴികെ മറ്റെന്തിനും ഇവ വളരെ കാര്യക്ഷമമല്ല. ഉദാഹരണങ്ങൾ: ഒരു സ്ട്രിംഗിന്റെ എല്ലാ ക്രമമാറ്റങ്ങളും കണ്ടെത്തൽ.

ബിഗ് O നൊട്ടേഷൻ എങ്ങനെ നിർണ്ണയിക്കാം (പൊതു നിയമങ്ങൾ)

ഒരു കോഡ് സ്നിപ്പെറ്റിന്റെ ബിഗ് O നൊട്ടേഷൻ നിർണ്ണയിക്കുന്നതിനുള്ള ഒരു ഘട്ടം ഘട്ടമായുള്ള സമീപനം ഇതാ:

ഇൻപുട്ട് തിരിച്ചറിയുക: "ഇൻപുട്ട് വലുപ്പം" (സാധാരണയായി 'n' പ്രതിനിധീകരിക്കുന്നത്) എന്താണെന്ന് നിർണ്ണയിക്കുക. ഇത് ഒരു അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം, ഒരു സ്ട്രിംഗിന്റെ നീളം, ഒരു ഡാറ്റ ഘടനയുടെ വലുപ്പം മുതലായവ ആകാം.
ലൂപ്പുകൾ വിശകലനം ചെയ്യുക: സിംഗിൾ ലൂപ്പ്: ഇൻപുട്ടിലൂടെ ആവർത്തിക്കുന്ന ഒരു ലൂപ്പ് സാധാരണയായി O(n) സങ്കീർണ്ണതയ്ക്ക് കാരണമാകുന്നു.

നെസ്റ്റഡ് ലൂപ്പുകൾ: നെസ്റ്റഡ് ലൂപ്പുകൾ സാധാരണയായി സങ്കീർണ്ണതകളെ ഗുണിക്കുന്നു. ഒരേ ഇൻപുട്ടിൽ ആവർത്തിക്കുന്ന രണ്ട് നെസ്റ്റഡ് ലൂപ്പുകൾ O(n²) ആണ്. മൂന്ന് നെസ്റ്റഡ് ലൂപ്പുകൾ O(n³) ആണ്, മുതലായവ.
ലോഗരിഥമിക് ബിഹേവിയർ ഉപയോഗിച്ച് ലൂപ്പ് ചെയ്യുക: ഒരു ലൂപ്പ് ഇൻപുട്ട് വലുപ്പത്തെ ഒരു സ്ഥിരമായ ഘടകം കൊണ്ട് ആവർത്തിച്ച് ഹരിച്ചാൽ (ഉദാ. ബൈനറി തിരയൽ), അത് O(log n) സങ്കീർണ്ണതയ്ക്ക് കാരണമാകും.

ഫംഗ്ഷൻ കോളുകൾ വിശകലനം ചെയ്യുക: ആവർത്തന കോളുകൾ: ആവർത്തന ഫംഗ്ഷനുകളുടെ സങ്കീർണ്ണത ആവർത്തന ഫംഗ്ഷനുകളുടെ എണ്ണത്തെയും ഓരോ കോളിലും ചെയ്യുന്ന ജോലിയെയും ആശ്രയിച്ചിരിക്കുന്നു. മാസ്റ്റർ സിദ്ധാന്തം പോലുള്ള സാങ്കേതിക വിദ്യകൾ ആവർത്തന ഫംഗ്ഷനുകൾ വിശകലനം ചെയ്യാൻ സഹായിക്കും. ലളിതമായ ആവർത്തന ഫംഗ്ഷനുകൾ എക്സ്പോണൻഷ്യൽ (O(2ⁿ)) അല്ലെങ്കിൽ ഫാക്റ്റോറിയൽ (O(n!)) ആകാം.

മറ്റ് ഫംഗ്ഷൻ കോളുകൾ: നിങ്ങളുടെ കോഡ് മറ്റ് ഫംഗ്ഷനുകളെ വിളിക്കുകയാണെങ്കിൽ, നിങ്ങൾ അവയുടെ വലിയ O സങ്കീർണ്ണതകൾ പരിഗണിക്കേണ്ടതുണ്ട്. നിങ്ങൾ ഒരു O(n) ലൂപ്പിനുള്ളിൽ ഒരു O(n²) ഫംഗ്ഷൻ വിളിക്കുകയാണെങ്കിൽ, മൊത്തത്തിലുള്ള സങ്കീർണ്ണത O(n³) ആയി മാറുന്നു.

ഡ്രോപ്പ് കോൺസ്റ്റന്റുകൾ: സ്ഥിരമായ ഘടകങ്ങൾ അവഗണിക്കുക. O(2n) ഉം O(n) ഉം O(n) ഉം O(n) ആയി കണക്കാക്കപ്പെടുന്നു. Big O എന്നത് വളർച്ചാ നിരക്കിനെക്കുറിച്ചാണ്, കൃത്യമായ സമയത്തെക്കുറിച്ചല്ല.
ലോവർ-ഓർഡർ പദങ്ങൾ കുറയ്ക്കുക: പ്രബലമായ പദം മാത്രം നിലനിർത്തുക. ഉദാഹരണത്തിന്, n² n നേക്കാൾ വളരെ വേഗത്തിൽ വളരുന്നതിനാൽ O(n² + n) O(n² ആയി ലളിതമാക്കിയിരിക്കുന്നു.
മികച്ചത്, ശരാശരി, മോശം കേസ്:

ഏറ്റവും മോശം കേസ് സങ്കീർണ്ണത: ഏറ്റവും സാധാരണവും പൊതുവെ ഏറ്റവും പ്രധാനപ്പെട്ടതുമായ കേസ്. അൽഗോരിതത്തിന്റെ റിസോഴ്‌സ് ഉപയോഗത്തിൽ ഇത് ഒരു ഉയർന്ന പരിധി നൽകുന്നു. "ബിഗ് O" എന്ന് പറയുമ്പോൾ നമ്മൾ സാധാരണയായി ഉദ്ദേശിക്കുന്നത് ഇതാണ്.
ശരാശരി-കേസ് സങ്കീർണ്ണത: പല റണ്ണുകളിലും പ്രതീക്ഷിക്കുന്ന പ്രകടനം വിവരിക്കുന്നു. പലപ്പോഴും കൃത്യമായി നിർണ്ണയിക്കാൻ പ്രയാസമാണ്.
മികച്ച കേസ് സങ്കീർണ്ണത: ഏറ്റവും കാര്യക്ഷമമായ സാഹചര്യം വിവരിക്കുന്നു. സാധാരണ പ്രകടനത്തെ പ്രതിനിധീകരിക്കാത്തതിനാൽ പ്രായോഗികമായി ഉപയോഗപ്രദമല്ല.

ഉദാഹരണങ്ങൾ

ചില കോഡ് സ്‌നിപ്പെറ്റുകൾ വിശകലനം ചെയ്യാം:

ഉദാഹരണം 1: ഒരു അറേ എലമെന്റ് ആക്‌സസ് ചെയ്യുന്നു

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

ഇൻപുട്ട്: arr എന്ന അറേയും സൂചിക എന്ന അറേയും. അറേയുടെ വലുപ്പം (arr.length) ഇൻപുട്ട് വലുപ്പം 'n' ആണ്. * വിശകലനം: അറേയുടെ വലുപ്പം പരിഗണിക്കാതെ, സൂചിക ഉപയോഗിച്ച് ഒരു അറേ എലമെന്റിലേക്ക് പ്രവേശിക്കുന്നതിന് സ്ഥിരമായ സമയം എടുക്കും. ബിഗ് O: O(1)

ഉദാഹരണം 2: ലീനിയർ തിരയൽ

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

ഇൻപുട്ട്: arr എന്ന അറേയും target എന്ന അറേയും. അറേയുടെ വലുപ്പം (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]) {
        // Swap elements
        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 ഉം target ഉം. അറേയുടെ (arr.length) വലുപ്പം 'n' ആണ്.
വിശകലനം: while ലൂപ്പിന്റെ ഓരോ ആവർത്തനത്തിലും, ഞങ്ങൾ തിരയൽ ഇടം ഫലപ്രദമായി പകുതിയാക്കുന്നു. ലക്ഷ്യം കണ്ടെത്തുന്നതുവരെയോ തിരയൽ ഇടം ശൂന്യമാകുന്നതുവരെയോ ഈ പകുതിയാക്കൽ തുടരുന്നു. നമുക്ക് 'n' എത്ര തവണ പകുതിയാക്കാൻ കഴിയും എന്നത് log₂(n) ആണ് (ലോഗരിതം ബേസ് 2).
ബിഗ് O: O(log n)

ഉദാഹരണം 5: റിക്കേഴ്സീവ് ഫിബൊനാച്ചി (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 എന്നത് ഇൻപുട്ട് മൂല്യം യുടെ വലുപ്പമാണ്. ഏറ്റവും മോശം സാഹചര്യത്തിൽ, value n ന് ആനുപാതികമായിരിക്കാം. അതിനാൽ anotherFunction O(n) ആണ്
doSomething ന്റെ ലൂപ്പിനുള്ളിൽ anotherFunction എന്ന് വിളിക്കപ്പെടുന്നതിനാൽ, സങ്കീർണ്ണതകൾ വർദ്ധിക്കുന്നു.
Big O: O(n * n) = O(n²)

ഉപസംഹാരം

ബിഗ് O നൊട്ടേഷൻ നിർണ്ണയിക്കുന്നത് ഏതൊരു പ്രോഗ്രാമർക്കും ഒരു നിർണായക കഴിവാണ്. ആധിപത്യ പ്രവർത്തനങ്ങൾ തിരിച്ചറിയുന്നതിനുള്ള അടിസ്ഥാന തത്വങ്ങൾ മനസ്സിലാക്കുന്നതിലൂടെ, ലൂപ്പുകളും ഫംഗ്ഷൻ കോളുകളും വിശകലനം ചെയ്യുന്നതിലൂടെയും വളർച്ചാ നിരക്കുകളിൽ ശ്രദ്ധ കേന്ദ്രീകരിക്കുന്നതിലൂടെയും, നിങ്ങളുടെ അൽഗോരിതങ്ങളുടെ കാര്യക്ഷമത ഫലപ്രദമായി വിലയിരുത്താനും താരതമ്യം ചെയ്യാനും വിവരമുള്ള ഡിസൈൻ തീരുമാനങ്ങൾ എടുക്കാനും കഴിയും. നിങ്ങളുടെ ധാരണ ഉറപ്പിക്കുന്നതിന് കോഡ് സ്‌നിപ്പെറ്റുകൾ വിശകലനം ചെയ്യുന്നത് പരിശീലിക്കാൻ ഓർമ്മിക്കുക.

ജാവാസ്ക്രിപ്റ്റ് ബിഗ് ഒ നൊട്ടേഷൻ അനലൈസർ