"അൽഗൊരിതങ്ങളുടെ വിശകലനം" എന്ന താളിന്റെ പതിപ്പുകൾ തമ്മിലുള്ള വ്യത്യാസം

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
No edit summary
വരി 37: വരി 37:


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


==അവലംബം==
* http://algs4.cs.princeton.edu/14analysis/
[[വർഗ്ഗം:അൽഗൊരിതങ്ങൾ]]
[[വർഗ്ഗം:അൽഗൊരിതങ്ങൾ]]
[[en:Analysis of algorithms]]
[[en:Analysis of algorithms]]

20:35, 19 ഫെബ്രുവരി 2013-നു നിലവിലുണ്ടായിരുന്ന രൂപം

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

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

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

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

പലവിധത്തിലും ഒരൽഗൊരിതത്തിന്റെ സമയ സങ്കീർണ്ണത കണക്ക് കൂട്ടാവുന്നതാണു.

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

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

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

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

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

Tn = c1A + c2B + c3C + c4D + c5E

A = അറേ ഉപയോഗങ്ങളുടെ എണ്ണം.

B = പൂർണ്ണ സംഖ്യകളുടെ കൂട്ടലുകളൂടെ എണ്ണം.

C = താരതമ്യങ്ങളുടെ എണ്ണം.

D = ഇങ്ക്രിമെന്റുകളുടെ എണ്ണം.

E = താത്കാലിക മൂലകങ്ങളിൽ, മൂല്യം ഇടുന്ന ക്രിയകളുടെ എണ്ണം

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

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

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

അവലംബം