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

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

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) അതിന്റെ സമയ സങ്കീർണ്ണത ദ്വിമാനം ആണെന്ന് പറയുന്നു. ഇനി ഈ ഫലനത്തിന് ഏകമാനമായ ഒരു പദം കൂടി ഉണ്ടെങ്കിലും (ഉദാ : $n^{2}+5n$ ) ഏറ്റവും വലിയ മാനം മാത്രമേ കണക്കിലെടുക്കുന്നുള്ളൂ. ബാക്കിയെല്ലാം ഒഴിവാക്കും.

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

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

സാധാരണ കണ്ടുവരുന്ന സമയ സങ്കീർണ്ണതകളുടെ പട്ടിക

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

പേര്	സങ്കീർണ്ണതാ ക്ലാസ്	സമയ സങ്കീർണ്ണത (T(n))	ഉദാഹരണം	ഈ സങ്കീർണ്ണതയുള്ള അൽഗോരിതങ്ങളുടെ ഉദാഹരണങ്ങൾ
സ്ഥിരസമയം (constant time)		O(1)	10	ഒരു സംഖ്യ ഒറ്റയാണോ ഇരട്ടയാണോ എന്നു നിശ്ചയിയ്ക്കാനുള്ള അൽഗോരിതം. എത്ര വലിയ സംഖ്യ ഇന്പുട് ആയി കൊടുത്താലും ഇത് ഒരൊറ്റ ചെക്ക് ഉപയോഗിച്ച് കണ്ടു പിടിയ്ക്കാം (എത്ര വലിയ സംഖ്യയാണെങ്കിലും ആ സംഖ്യയുടെ അവസാന ബിറ്റ് 1 ആണെങ്കിൽ ഒറ്റ, അല്ലെങ്കിൽ ഇരട്ട)
inverse Ackermann time		O(α(n))		Amortized time per operation using a disjoint set
iterated logarithmic time		O(log* n)		Distributed coloring of cycles
ലോഗ്- ലോഗരിതമിക് സമയം		O(log log n)		Amortized time per operation using a bounded priority queue^[1]
ലോഗരിതമിക് സമയം	DLOGTIME	O(log n)	log n, log(n²)	ബൈനറി തിരയൽ
പോളി ലോഗരിതമിക് സമയം		poly(log n)	(log n)²
fractional power		$O (n c)$ where $0 < c < 1$	n^1/2, n^2/3	ഒരു kd ട്രീയിൽ തിരയാനുള്ള അൽഗോരിതം
രേഖീയ സമയം		O(n)	n	ക്രമരഹിതമായ ഒരു അടുക്കിലെ ഏറ്റവും വലിയ അംഗത്തെ തിരയുന്ന അൽഗോരിതം. ഇവിടെ ഏറ്റവും കൂടിയ അവസ്ഥയിൽ എല്ലാ അംഗങ്ങളെയും ഓരോ പ്രാവശ്യം സന്ദർശിച്ച് അത് ഇതുവരെയുള്ള വലിയ സംഖ്യയേക്കാൾ വലുതാണോ എന്ന് നോക്കണം. അതായത് n അംഗങ്ങൾ ഉണ്ടെങ്കിൽ ആ നമ്പറിന് ആനുപാതികമാണ് എത്ര പ്രാവശ്യം ചെക്ക് ചെയ്യണം എന്നത്.
"n log star n" time		O(n log* n)		Seidel's polygon triangulation algorithm.
അവാസ്തവ രേഖീയ സമയം		O(n log n)	n log n, log n!	സംഖ്യകളെ പരസ്പരം താരതമ്യം ചെയ്തു ചെയ്യാവുന്ന ക്രമീകരണ അൽഗോരിതങ്ങളിൽ (sorting algorithms) എത്താവുന്ന പരമാവധി വേഗത . ഡിസ്ക്രീറ്റ് ഫ്യൂറിയേ ട്രാൻസ്‌ഫോം എന്ന വളരെ പ്രധാനപ്പെട്ട അൽഗോരിതത്തിനും ഇതേ സങ്കീർണ്ണതയാണ്.
ദ്വിമാന സമയം		O(n²)	n²	ബബ്ബിൾ ക്രമീകരണം, ഒരു കൂട്ടം ഇടകലർന്ന സോക്‌സുകളെ തമ്മിൽ തമ്മിൽ ജോഡി ചേർക്കൽ തുടങ്ങിയവ. 10 വ്യത്യസ്ത ജോഡി കളറുകൾ ഉള്ള സോക്‌സുകൾ ഇടകലർത്തി ഇട്ടിരിയ്ക്കുന്ന ഒരു സഞ്ചിയിൽ നിന്നും എല്ലാ സോക്‌സുകളെയും എങ്ങനെ ജോഡി ആക്കും? ആദ്യം ഏതെങ്കിലും ഒരു സോക്സ്‌ എടുക്കുക. അതിനുശേഷം സഞ്ചിയിൽ നിന്നും അതിനു പറ്റിയ മറ്റേ സോക്സ്‌ കണ്ടു പിടിയ്ക്കുക. അതായത് ഓരോ സോക്‌സിനും അതിനു പറ്റിയ മറ്റേ സോക്സ്‌ കണ്ടെത്താൻ ഏറ്റവും മോശം അവസ്ഥയിൽ 10 പ്രാവശ്യം സഞ്ചിയിൽ നോക്കണം. ആയിരക്കണക്കിന് സോക്‌സുകൾ ഉള്ള അവസ്ഥയിൽ ഇതിന്റെ അസിംപാത സ്വഭാവം ദ്വിമാനം O(n²) ആകുന്നു. എന്നാൽ ഈ സോക്‌സുകൾ കളറിന്റെ അടിസ്ഥാനത്തിൽ ആദ്യം ക്രമീകരിച്ചാൽ അത് ഇതിലും വേഗത്തിൽ ചെയ്യാം. ക്രമീകരണത്തിന്റെ ഏറ്റവും മികച്ച സമയ സങ്കീർണ്ണത O(n log n) ആണ്. അതിന് ശേഷം O(n) സങ്കീർണ്ണതയോടെ ഓരോരോ ജോഡി ആയി പുറത്തെടുക്കാം. അതായത് സങ്കീർണ്ണതയുടെ ഫലനം O(n log n + n). ഇതിലെ വില കുറഞ്ഞ പദം ഒഴിവാക്കാം. അതായത് സോക്സ്‌ പുറത്തെടുക്കാനുള്ള ഏറ്റവും മികച്ച അൽഗോരിതത്തിന്റെ സങ്കീർണ്ണത O(n log n) ആണ്.
ത്രിമാന സമയം		O(n³)	n³	രണ്ടു ചതുരമൂശകളെ പരസ്പരം ഗുണിയ്ക്കുന്ന അൽഗോരിതം.
ബഹുപദ സമയം അഥവാ പോളിനോമിയൽ സമയം (polynomial time)	P	2^O(log n) = poly(n)	n, n log n, n¹⁰	രേഖീയ ഉത്തമീകരണം (linear programming) പരിഹരിയ്ക്കാനുള്ള കർമാകറിന്റെ അൽഗോരിതം; എ.കെ.എസ്. അഭാജ്യതാപരിശോധന
അവാസ്തവ ബഹുപദ സമയം അഥവാ അവാസ്തവ പോളിനോമിയൽ സമയം quasi-polynomial time	QP	2^poly(log n)	n^log log n, n^log n	Best-known O(log² n)-approximation algorithm for the directed Steiner tree problem.
sub-exponential time (first definition)	SUBEXP	O(2^{n^ε}) for all ε > 0	O(2^{log n^{log log n}})	Assuming complexity theoretic conjectures, BPP is contained in SUBEXP.
sub-exponential time (second definition)		2^o(n)	2^{n^1/3}	ഒരു സംഖ്യയെ ഘടകക്രിയ ചെയ്തു അതിന്റെ ഘടകങ്ങൾ കണ്ടു പിടിയ്ക്കാനുള്ള ഏറ്റവും മികച്ച അൽഗോരിതം, രണ്ടു ഗ്രാഫുകൾ ഒന്ന് തന്നെയാണോ എന്ന് കണ്ടുപിടിയ്ക്കാനുള്ള ഏറ്റവും മികച്ച അൽഗോരിതം
exponential time (with linear exponent)	E	2^O(n)	1.1ⁿ, 10ⁿ	ട്രാവലിങ് സേൽസ്‌മാൻ അൽഗോരിതം(traveling salesman problem) ഡൈനാമിക് പ്രോഗ്രാമിങ്(dynamic programming) ഉപയോഗിച്ച് പരിഹരിയ്ക്കാനുള്ള സമയം
എക്സ്പോണെൻഷ്യൽ സമയം	EXPTIME	2^poly(n)	2ⁿ, 2^n²	ഒരു ഗണത്തിന്റെ എല്ലാ ഉപഗണങ്ങളും കണ്ടു പിടിയ്ക്കാനുള്ള അൽഗോരിതം
ഫാക്ടോറിയൽ സമയം		O(n!)	n!	ട്രാവലിങ് സേൽസ്‌മാൻ അൽഗോരിതം(traveling salesman problem) ഏറ്റവും കഷ്ടമേറിയ രീതിയിൽ (brute force method) ഉപയോഗിച്ച് പരിഹരിയ്ക്കാനുള്ള സമയം
double exponential time	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	Deciding the truth of a given statement in Presburger arithmetic

അവലംബങ്ങൾ

↑ Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in O(log log N) time and O(n) space". Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.

[1] Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in O(log log N) time and O(n) space". Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.

[1]