അൽഗൊരിതങ്ങളുടെ വിശകലനം

ഒരൽഗൊരിതത്തിന്റെ പ്രവർത്തനത്തിലുള്ള മെച്ചം മനസ്സിലാക്കുന്നതിനും, ഒരു കാര്യം ചെയ്യുവാനനുയോജ്യമായ അൽഗൊരിതമേതെന്നു നിശ്ചയിക്കുന്നതിനും അവയെ വിശകലനം ചെയ്യേണ്ടത് അത്യാവശ്യമാണു. ചുവടെ കൊടുത്തിരിയ്ക്കുന്ന, രണ്ട് കാര്യങ്ങളാണിത്തരം വിശകലനങ്ങളിൽ കണക്കാക്കുന്നത്.

1. ഉദ്ദേശിച്ച കാര്യം ചെയ്തു തീർക്കുന്നതിനായി അൽഗൊരിതം എന്തുമാത്രം സമയം എടുക്കും
2. അത് ചെയ്യുവാനെന്തുമാത്രം സ്ഥലം (മെമ്മറി) എടുക്കും

ഡോക്ടർ ഡോണാൾഡ് കനൂത്ത് ആണു അൽഗൊരിത വിശകലനത്തിനു ഒരു ശാസ്ത്രീയ സമീപന രീതി ആദ്യമായി മുന്നോട്ട് വച്ചത്.

സമയ സങ്കീർണ്ണതയുടെ വിശകലനം

പലവിധത്തിലും ഇത് നടത്താവുന്നതാണു.

1. പ്രയോഗസിദ്ധമായ വിവരത്തിന്റെ അടിസ്ഥാനത്തിൽ
2. ഒരു ഗണിത മാതൃക സൃഷ്ടിച്ച്

പ്രയോഗസിദ്ധമായ വിവരത്തിന്റെ അടിസ്ഥാനത്തിലുള്ള വിശകലനം

അൽഗൊരിതത്തിൽ നിന്നും ഒരു കംബ്യൂട്ടർ പ്രോഗ്രാം ഉണ്ടാക്കുകയും, പല ഇൻപുട്ടുകൾക്ക് ഉത്തരം ലഭിക്കാനാവശ്യമായ സമയം കണക്കാക്കുകയും,അതിൽ നിന്നും ഒരു ഇൻപുട്ട്-അവശ്യസമയ ഗ്രാഫ് സൃഷ്ടിക്കുകയും, ഗ്രാഫിൽ നിന്നും സങ്കീർണ്ണതയെ കുറിക്കുന്ന ഒരു ഗണിത വാക്യം നിർദ്ധാരണം ചെയ്തെടുക്കയും ചെയ്യുന്ന രീതിയാണിത്.

ഗണിതമാതൃക സൃഷ്ടിച്ച് വിശകലനം

ഒരു അൽഗൊരിതത്തിന്റെ സമയ സങ്കീർണ്ണത, അതിലടങ്ങിയ വിവിദ്ധ ക്രിയകളുടെ എണ്ണവുമായും, അവ ഓരോന്നും ചെയ്യുന്നതിനാവശ്യമായ സമയവുമായിയും നേരിട്ട് ബന്ധപ്പെട്ടാണിരിയ്ക്കുന്നത്. ചുവടെ കൊടുത്ത സമവാക്യം അത്തന്മൊരു സമീപനരീതിയാണൂ കുറിയ്ക്കുന്നത്.

T_n = c1A + c2B + c3C + c4D + c5E

A = അറേ ഉപയോഗങ്ങളുടെ എണ്ണം. B = പൂർണ്ണ സംഖ്യകളുടെ കൂട്ടലുകളൂടെ എണ്ണം. C = താരതമ്യങ്ങളുടെ എണ്ണം. D = ഇങ്ക്രിമെന്റുകളുടെ എണ്ണം. E = താത്കാലിക മൂലകങ്ങളിൽ, മൂല്യം ഇടുന്ന ക്രിയകളുടെ എണ്ണം

c1,c2,c3,c4,c5 എന്നിവ ഇവ ഓരോന്നും ചെയ്യുന്നതിനാവശ്യമായ സമയം. ഇത് കമ്ബ്യൂട്ടറിനെയും, ഉപയോഗിയ്ക്കുന്ന ഭാഷയെയും, കംബൈലറിനെയുമൊക്കെ ബന്ധപ്പെട്ടിരിയ്ക്കുന്നു.

ഇപ്രകാരം ഓരോന്നും കൃത്യമായി കണക്കാക്കി ഒരു കൃത്യമായ ഗണിതമാതൃക സൃഷ്ടിക്കുന്നതിനു ചില പ്രായോഗിക ബുദ്ധിമുട്ടുകൾ ഉണ്ടെന്ന് മാത്രമല്ല, അത്ര കൃത്യമായ ഒരു വിശകലനം വഴി ലഭിയ്ക്കാവുന്ന നിരീക്ഷണത്തിനു അതിനായി ചിലവിടുന്ന ഊർജ്ജത്തിനനുസരിച്ചുള്ള വലിയ ഗുണം ഇല്ല എന്നതിനാലും, എളുപ്പം സമയ നിർദ്ധാരണം നടത്താവുന്ന രീതിയിൽ ചില ലളിതമാക്കലുകൾ നടത്താവുന്നതാണു.

1. സമയഗണനത്തെ കാര്യമായി ബാധിയ്ക്കുന്ന ചില പ്രധാന ക്രിയകളെ മാത്രം കണക്കിൽ പെടുത്തുക.(അല്ലാത്തവയെ അവഗണിയ്ക്കുക. ഉദാഹരണത്തിനു വസ്തുക്കളെ ഉൾകൊള്ളുന്ന അറേയുടെ/ ഡാറ്റാസ്ട്രകച്ചറന്മേലുള്ള മാറ്റങ്ങൾ)
2. സമയ സങ്കീർണ്ണത ഇൻപുട്ട് വസ്തുക്കളൂടെ വലുപ്പത്തിന്റെ(N) ധർമ്മമായി/ഫൺക്ഷനായി കണക്കാക്കുക. N ന്റെ ഉയർന്ന വർഗ്ഗത്തിനെ മാത്രം കണക്കാക്കുകയും, താഴ്ന്ന വർഗ്ഗങ്ങളെ അവഗണിയ്ക്കുകയും ചെയ്യുക.(വളരെ വലിയ N മൂല്യത്തിനു താഴ്ന്ന വർഗ്ഗങ്ങൾ കൊണ്ട് വരാവുന്ന സമയ സങ്കീർണ്ണതയിലുള്ള വ്യത്യാസം താരതമ്യേന തുച്ഛമാണെന്നതാണിതിന്റെ കാരണം. ഉദാഹരണത്തിനു ഒരു അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത ~ N²+N ആണെന്നിരിയ്ക്കട്ടെ. 105 എന്ന N നു, 10¹⁰ + 10⁵ എന്നതാണല്ലോ സങ്കീർണ്ണത. 10¹⁰ നോടുള്ള 10⁵ എന്ന കൂട്ടിചേർക്കൽ അത്ര ഗണനീയമല്ലല്ലോ.)

അവലംബം

http://algs4.cs.princeton.edu/14analysis/