ബിഗ് O സമയ സങ്കീർണ്ണത നിർണ്ണയിക്കുന്നതിനുള്ള ഓൺലൈൻ ജാവാസ്ക്രിപ്റ്റ് അനലൈസർ.
ബിഗ് ഒ നൊട്ടേഷൻ എന്നത് കമ്പ്യൂട്ടർ സയൻസിൽ ഒരു അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത അല്ലെങ്കിൽ സങ്കീർണ്ണത വിവരിക്കാൻ ഉപയോഗിക്കുന്ന ഒരു അടിസ്ഥാന ആശയമാണ്. ഇൻപുട്ട് വലുപ്പം വർദ്ധിക്കുന്നതിനനുസരിച്ച് ഒരു അൽഗോരിതത്തിന്റെ റിസോഴ്സ് ഉപയോഗത്തിന്റെ (സാധാരണയായി സമയം അല്ലെങ്കിൽ സ്ഥലം) വളർച്ചാ നിരക്കിൽ ഇത് ഒരു ഉയർന്ന പരിധി നൽകുന്നു. നിർണായകമായി, ബിഗ് ഒ റിസോഴ്സ് ഉപയോഗത്തെ പ്രതിനിധീകരിക്കുന്ന ഫംഗ്ഷന്റെ പ്രബലമായ പദത്തിൽ ശ്രദ്ധ കേന്ദ്രീകരിക്കുകയും സ്ഥിരമായ ഘടകങ്ങളെയും താഴ്ന്ന ഓർഡർ പദങ്ങളെയും അവഗണിക്കുകയും ചെയ്യുന്നു. ഇതിനർത്ഥം ഒരു പ്രത്യേക മെഷീനിൽ അതിന്റെ കൃത്യമായ നിർവ്വഹണ സമയത്തിലല്ല, വലിയ ഇൻപുട്ടുകൾ ഉപയോഗിച്ച് അൽഗോരിതം എങ്ങനെ സ്കെയിൽ ചെയ്യുന്നു എന്നതിലാണ് ഞങ്ങൾക്ക് താൽപ്പര്യമുള്ളത് എന്നാണ്.
ഏറ്റവും കാര്യക്ഷമത കുറഞ്ഞതിൽ നിന്ന് കാര്യക്ഷമത കുറഞ്ഞതിലേക്ക് ക്രമീകരിച്ചിരിക്കുന്ന പൊതുവായ ബിഗ് ഒ സങ്കീർണ്ണതകളുടെ ഒരു ലിസ്റ്റ് ഇതാ:
ഒരു കോഡ് സ്നിപ്പെറ്റിന്റെ ബിഗ് O നൊട്ടേഷൻ നിർണ്ണയിക്കുന്നതിനുള്ള ഒരു ഘട്ടം ഘട്ടമായുള്ള സമീപനം ഇതാ:
ഇൻപുട്ട് തിരിച്ചറിയുക: "ഇൻപുട്ട് വലുപ്പം" (സാധാരണയായി 'n' പ്രതിനിധീകരിക്കുന്നത്) എന്താണെന്ന് നിർണ്ണയിക്കുക. ഇത് ഒരു അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം, ഒരു സ്ട്രിംഗിന്റെ നീളം, ഒരു ഡാറ്റ ഘടനയുടെ വലുപ്പം മുതലായവ ആകാം.
ലൂപ്പുകൾ വിശകലനം ചെയ്യുക: സിംഗിൾ ലൂപ്പ്: ഇൻപുട്ടിലൂടെ ആവർത്തിക്കുന്ന ഒരു ലൂപ്പ് സാധാരണയായി O(n) സങ്കീർണ്ണതയ്ക്ക് കാരണമാകുന്നു.
ഡ്രോപ്പ് കോൺസ്റ്റന്റുകൾ: സ്ഥിരമായ ഘടകങ്ങൾ അവഗണിക്കുക. O(2n) ഉം O(n) ഉം O(n) ഉം O(n) ആയി കണക്കാക്കപ്പെടുന്നു. Big O എന്നത് വളർച്ചാ നിരക്കിനെക്കുറിച്ചാണ്, കൃത്യമായ സമയത്തെക്കുറിച്ചല്ല.
ലോവർ-ഓർഡർ പദങ്ങൾ കുറയ്ക്കുക: പ്രബലമായ പദം മാത്രം നിലനിർത്തുക. ഉദാഹരണത്തിന്, n² n നേക്കാൾ വളരെ വേഗത്തിൽ വളരുന്നതിനാൽ O(n² + n) O(n² ആയി ലളിതമാക്കിയിരിക്കുന്നു.
മികച്ചത്, ശരാശരി, മോശം കേസ്:
ചില കോഡ് സ്നിപ്പെറ്റുകൾ വിശകലനം ചെയ്യാം:
ഉദാഹരണം 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' തവണകളിൽ (അറേയുടെ നീളം) ആവർത്തിക്കുന്നു.ഉദാഹരണം 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).ഉദാഹരണം 5: റിക്കേഴ്സീവ് ഫിബൊനാച്ചി (Naive)
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
n.fibonacci(n) എന്നതിലേക്കുള്ള ഓരോ കോളിനും (ഇവിടെ n > 1), നമ്മൾ രണ്ട് കൂടുതൽ ആവർത്തന കോളുകൾ ചെയ്യുന്നു. ഇത് കോളുകളുടെ ഒരു ശാഖിതമായ വൃക്ഷം സൃഷ്ടിക്കുന്നു. 'n' ലെ ഓരോ വർദ്ധനവോടെയും കോളുകളുടെ എണ്ണം ഏകദേശം ഇരട്ടിയാകുന്നു.ഉദാഹരണം 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);
}
}
doSomething n തവണ ആവർത്തിക്കുന്നു.anotherFunction ന് സങ്കീർണ്ണത O(m) ഉണ്ട്, ഇവിടെ m എന്നത് ഇൻപുട്ട് മൂല്യം യുടെ വലുപ്പമാണ്. ഏറ്റവും മോശം സാഹചര്യത്തിൽ, value n ന് ആനുപാതികമായിരിക്കാം. അതിനാൽ anotherFunction O(n) ആണ്doSomething ന്റെ ലൂപ്പിനുള്ളിൽ anotherFunction എന്ന് വിളിക്കപ്പെടുന്നതിനാൽ, സങ്കീർണ്ണതകൾ വർദ്ധിക്കുന്നു.ബിഗ് O നൊട്ടേഷൻ നിർണ്ണയിക്കുന്നത് ഏതൊരു പ്രോഗ്രാമർക്കും ഒരു നിർണായക കഴിവാണ്. ആധിപത്യ പ്രവർത്തനങ്ങൾ തിരിച്ചറിയുന്നതിനുള്ള അടിസ്ഥാന തത്വങ്ങൾ മനസ്സിലാക്കുന്നതിലൂടെ, ലൂപ്പുകളും ഫംഗ്ഷൻ കോളുകളും വിശകലനം ചെയ്യുന്നതിലൂടെയും വളർച്ചാ നിരക്കുകളിൽ ശ്രദ്ധ കേന്ദ്രീകരിക്കുന്നതിലൂടെയും, നിങ്ങളുടെ അൽഗോരിതങ്ങളുടെ കാര്യക്ഷമത ഫലപ്രദമായി വിലയിരുത്താനും താരതമ്യം ചെയ്യാനും വിവരമുള്ള ഡിസൈൻ തീരുമാനങ്ങൾ എടുക്കാനും കഴിയും. നിങ്ങളുടെ ധാരണ ഉറപ്പിക്കുന്നതിന് കോഡ് സ്നിപ്പെറ്റുകൾ വിശകലനം ചെയ്യുന്നത് പരിശീലിക്കാൻ ഓർമ്മിക്കുക.