സമയ സങ്കീർണ്ണത (കമ്പ്യൂട്ടർ ശാസ്ത്രം)

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Time_Complexity

കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിൽ ഒരു അൽഗോരിതം ഓടിയ്ക്കാനുള്ള സമയം കണക്കാക്കാൻ ഉപയോഗിയ്ക്കുന്ന ഒരു അളവാണ് സമയ സങ്കീർണ്ണത. സാധാരണയായി അൽഗോരിതത്തിലെ ഒരു പ്രാഥമിക വരി ഓടിച്ചു നോക്കാൻ ഒരു നിശ്ചിത സമയം വേണമെന്ന് സങ്കൽപ്പിയ്ക്കുന്നു. അതിനുശേഷം ഒരു അൽഗോരിതത്തിൽ എത്ര പ്രാഥമിക വരികൾ (elementary steps) ഉണ്ടെന്നു എണ്ണിനോക്കിയാണ് അതിനെ ഈ നിശ്ചിത സമയം കൊണ്ട് ഗുണിച്ചാണ്‌ സമയ സങ്കീർണ്ണതയുടെ മതിപ്പുവില (estimate) നിശ്ചയിയ്ക്കുന്നത്.

സാധാരണയായി ഒരു അൽഗോരിതത്തിലേക്കുള്ള ഇൻപുട്ടിന്റെ വിലകൾക്ക് പല വലിപ്പം ആകാം. അതിനാൽ ഈ വിലകളിലെ ഏറ്റവും വലിയ വലിപ്പമുള്ള വില കൊടുത്താൽ എന്തു സംഭവിയ്ക്കും എന്ന് നോക്കിയാണ് (worst case complexity അഥവാ ഉച്ച സങ്കീർണ്ണത ) അതിന്റെ പ്രകടനം വിലയിരുത്തുന്നത്. ചില അവസരങ്ങളിൽ അൽഗോരിതങ്ങളുടെ ശരാശരി സങ്കീർണ്ണത (average time complexity) യും കണക്കിലെടുക്കാറുണ്ട്.

രണ്ടവസ്ഥയിലും സമയ സങ്കീർണ്ണത ഇൻപുട്ട് വിലയുടെ വലിപ്പത്തിന്റെ (size of input) ഒരു ഫലനം (function) ആയാണ് എഴുതുന്നത്.^:226 എന്നാൽ ഈ ഫലനം എത്രയാണെന്ന് കൃത്യമായി ഗണിച്ചെടുക്കാൻ എളുപ്പമല്ല. അതിനാൽ ഇതിന്റെ സൂത്രവാക്യം കൃത്യമായി എഴുതുന്നതിനു പകരം ഇന്പുട് വിലകളുടെ വലിപ്പം കൂടുംതോറും അൽഗോരിതത്തിന്റെ ഓടുന്ന വരികളുടെ എണ്ണം എത്ര വേഗതയിൽ കൂടുന്നു എന്നുള്ള ഒരു മതിപ്പുവിലയാണ് സാധാരണയായി കണക്കാക്കാറുള്ളത്. ഇതിനെ സമയ സങ്കീർണ്ണതയുടെ അസംപാത സ്വഭാവം (asymptotic behavior, അഥവാ ട്രെൻഡ്) കണക്കാക്കുന്നു എന്നു പറയാം. ഉദാഹരണത്തിന് ഇൻപുട്ട് വിലകളുടെ വലിപ്പത്തിന്റെ വർഗത്തിനനുസരിച്ച് ഒരു അൽഗോരിതത്തിലെ ഓടുന്ന വരികളുടെ എണ്ണം കൂടുന്നുണ്ടെങ്കിൽ (proportional to the square) അതിന്റെ സമയ സങ്കീർണ്ണത ദ്വിമാനം ആണെന്ന് പറയുന്നു. ഇനി ഈ ഫലനത്തിന് ഏകമാനമായ ഒരു പദം കൂടി ഉണ്ടെങ്കിലും (ഉദാ : ${\displaystyle n^{2}+5n}$) ഏറ്റവും വലിയ മാനം മാത്രമേ കണക്കിലെടുക്കുന്നുള്ളൂ. ബാക്കിയെല്ലാം ഒഴിവാക്കും.

 സാധാരണയായി സമയ സങ്കീർണ്ണത "വലിയ ഓ പ്രതീകം" (big O notation) എന്ന സങ്കേതം ഉപയോഗിച്ചാണ് രേഖപ്പെടുത്തുന്നത്. നേരത്തെ കാണിച്ച ഒരു ഫലനത്തിലെ ഏറ്റവും വലിയ ഘാതം ഉൾകൊള്ളുന്ന പദം (അഥവാ ഏറ്റവും വലിയ പദം, ചിലപ്പോൾ ഫലനങ്ങൾ ബഹുപദം (polynomial) തന്നെ ആകണമെന്നില്ല. എക്സ്പോണെൻഷ്യൽ, ഫാക്ടോറിയൽ തുടങ്ങി അതിവേഗം വളരുന്ന പദങ്ങൾ ആകാം) മാത്രം ഉൾക്കൊള്ളിച്ചുള്ള ഒരു പ്രതീകമാണിത്. ഉദാഹരണം ഇൻപുട്ട് വിലകളുടെ വലിപ്പം ${\displaystyle n}$ (ഇൻപുട്ടിനെ രേഖപ്പെടുത്താൻ എത്ര ബിറ്റുകൾ വേണമെന്നുള്ളതിന്റെ കണക്ക്) ആണെങ്കിൽ സമയ സങ്കീർണ്ണത ${\displaystyle O(n),}$ ${\displaystyle O(n\log n),}$ ${\displaystyle O(n^{\alpha }),}$ ${\displaystyle O(2^{n}),}$ തുടങ്ങിയവ ആണെന്ന് എഴുതാം.

ചില സന്ദർഭങ്ങളിൽ സമയ സങ്കീർണ്ണതയെ പ്രതീകങ്ങളില്ലാതെ തന്നെ രേഖീയം(linear, ${\displaystyle O(n)}$), പോളിനോമിയൽ/ബഹുപദം( ${\displaystyle O(n^{\alpha })}$ for some constant ${\displaystyle \alpha \geq 1}$), എക്സ്പോണെൻഷ്യൽ (${\displaystyle O(2^{n})}$) എന്നൊക്കെയും വിശേഷിപ്പിയ്ക്കാറുണ്ട്.

താഴെ കൊടുത്തിരിയ്ക്കുന്ന പട്ടികയിൽ സാധാരണ കണ്ടുവരുന്ന സമയ സങ്കീർണ്ണതകൾ വിവരിച്ചിട്ടുണ്ട്. ഈ പട്ടികയിൽ താഴേയ്ക്ക് പോകുന്തോറും തന്നിരിയ്ക്കുന്ന ഒരു ഇന്പുട് വിലയുടെ വലിപ്പത്തിനനുസരിച്ചുള്ള സമയ സങ്കീർണ്ണതയുടെ അളവ് കൂടിക്കൊണ്ടിരിയ്ക്കും. മുകളിലെ ആരേഖവും ശ്രദ്ധിയ്ക്കുക. എക്സ്പോണെൻഷ്യൽ, ഫാക്ടോറിയൽ സമയ സങ്കീർണ്ണത എത്തുംതോറും സമയ സങ്കീർണ്ണതയുടെ അളവ് ഭയാനകമായ രീതിയിൽ കൂടും.