"സമയ സങ്കീർണ്ണത (കമ്പ്യൂട്ടർ ശാസ്ത്രം)" എന്ന താളിന്റെ പതിപ്പുകൾ തമ്മിലുള്ള വ്യത്യാസം

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

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

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

| ഒരു സംഖ്യ ഒറ്റയാണോ ഇരട്ടയാണോ എന്നു നിശ്ചയിയ്ക്കാനുള്ള അൽഗോരിതം. എത്ര വലിയ സംഖ്യ ഇന്പുട് ആയി കൊടുത്താലും ഇത് ഒരൊറ്റ ചെക്ക് ഉപയോഗിച്ച് കണ്ടു പിടിയ്ക്കാം (അവസാന ബിറ്റ് 1 ആണെങ്കിൽ ഒറ്റ, അല്ലെങ്കിൽ ഇരട്ട)