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

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

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

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

അൽഗൊരിതങ്ങളുടെ വിശകലനനത്തിന്റെ മറ്റൊരു പ്രധാന ഉപയോഗം, ഒരു പ്രശ്നത്തിന്റെ പരിഹാരത്തിനു ലഭിയ്ക്കാവുന്ന മികച്ച സങ്കീർണ്ണതയേതെന്ന് മനസ്സിലാക്കുകയും, അതിനനുസരിച്ച് പുതിയ അൽഗൊരിതങ്ങൾ വികസിപ്പിച്ചെടുക്കുന്നതിനുള്ള ശ്രമങ്ങൾ നടത്തുകയും ചെയ്യുക എന്നതാണു. (സങ്കീർണ്ണതയുടെ ലോവർബൗണ്ട് - താഴെ തട്ട് - മനസ്സിലാക്കി, സങ്കീർണ്ണതയുടെ മേൽ തട്ട് കുറച്ച് കൊണ്ട് വരുന്ന രീതി)

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

ചുവടെ കൊടുത്തിരിയ്ക്കുന്ന,രണ്ട് കാര്യങ്ങളാണിത്തരം വിശകലനങ്ങളിൽ കണക്കാക്കുന്നത്.

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 ആണെന്നിരിയ്ക്കട്ടെ. 10⁵ എന്ന N നു, 10¹⁰ + 10⁵ എന്നതാണല്ലോ സങ്കീർണ്ണത. 10¹⁰ നോടുള്ള 10⁵ എന്ന കൂട്ടിചേർക്കൽ അത്ര ഗണനീയമല്ലല്ലോ.

വളർച്ചാനിരക്കിലുള്ള ക്രമവ്യത്യാസമനുസരിച്ച് വർഗ്ഗീകരണം

അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണതയെത്രയെന്ന്(സമയ/മെമ്മറി) മനസ്സിലാക്കിയാൽ അൽഗരിതങ്ങളെ വിവിദ്ധ ഗണങ്ങളായി വർഗ്ഗീകരിക്കാവുന്നതാണു.അപ്രകാരം, ഇൻപുട്ടിനുള്ള എണ്ണത്തിന്റെ ഫൺക്ഷൻ അനുസരിച്ച് അൽഗൊരിതങ്ങളുടെ സങ്കീർണ്ണതയെ വർഗ്ഗീകരണം ചെയ്താൽ പ്രധാനമായും,1, lgN, N, NlgN, N^2, N3,2N തുടങ്ങിയ പല സങ്കീർണ്ണതകളും ഉണ്ട്. അവയെ യഥാക്രമം കോൺസ്റ്റന്റ്, ലോഗരിതമിക്ക്, ലീനിയർ, ലീനിയരിത്മെറ്റിക്ക് ,ക്വാഡ്രാറ്റിക്ക്, ക്യൂബിക്ക്, എക്സ്പോണൻഷ്യൽ എന്നിങ്ങനെ വിളിയ്ക്കുന്നു.

മേൽക്കൊടുത്ത വർഗ്ഗീകരണം അവയുടെ സങ്കീർണ്ണതയുടെ ആരോഹണക്രമത്തിൽ ക്രമപ്പെടുത്തി ആണെഴുതിയിരിക്കുന്നത്. ഇത്തരം വർഗ്ഗീകരണം വഴി ഒരു അൽഗൊരിതം എന്തു മാത്രം സമയം അല്ലെങ്കിൽ, മെമ്മറി എടുക്കാനിടയുണ്ടെന്ന് മനസ്സിലാക്കാനും, പ്രശ്നത്തിനനുസരിച്ച് മറ്റ് അൽഗൊരിതങ്ങൾ എടുക്കണമോയെന്ന് തീരുമാനമെടുക്കാനും പ്രോഗ്രാമ്മറെ സഹായിക്കുന്നു.

ഉദാഹരണത്തിനു സെലക്ഷൻ സോർട്ടിന്റെ സമയ സങ്കീർണ്ണത N² ആണു. വലിയ സംഖ്യകൾ ഉള്ള ലിസ്റ്റിൽ സെലക്ഷൻ സോർട്ട് മിക്കവാറും പ്രായോഗികമല്ല എന്നറിവിലേയ്ക്ക് ഈ ദ്വിമാന സങ്കീർണ്ണത പ്രോഗ്രാമറിനെ നയിക്കുകയും, അത്തരം പ്രശ്നങ്ങളിൽ മറ്റ് അൽഗരിതങ്ങൾ ഉദാഹരണത്തിനു സങ്കീർണ്ണത NlgN ഉള്ള മെർജ് സോർട്ട് ഉപയോഗിക്കുകയും ചെയ്യുന്നു.

അവലംബം

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