"ബൈനറി തിരയൽ" എന്ന താളിന്റെ പതിപ്പുകൾ തമ്മിലുള്ള വ്യത്യാസം

No edit summary
No edit summary
വരി 25:
==കാര്യക്ഷമത==
 
[[File:BinraryTree Malayalam.png|thumb|upright=3.0|ബൈനറി ട്രീ]]
ഈ അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത പരിശോധിയ്ക്കാനായി ഇതിനെ ഒരു [[ട്രീ((കമ്പ്യൂട്ടർ ശാസ്ത്രം)) | ട്രീയോട്]] ഉപമിയ്ക്കാം. മധ്യത്തിൽ ഉള്ള വില ആയിരിയ്ക്കും ട്രീയുടെ [[മൂലം(കമ്പ്യൂട്ടർ ശാസ്ത്രം) | മൂലം]]. ഈ വിലയേക്കാൾ കുറഞ്ഞ അംഗങ്ങൾ ഉള്ള അടുക്കിന്റെ പകുതി ഈ ട്രീയുടെ ഇടത്തെ സബ്-ട്രീയും മറ്റേ പകുതി വലത്തേ സബ്-ട്രീയും ആയി കണക്കാക്കാം. തുടർന്ന് അടുത്ത നിലയിൽ ഉള്ള സബ്-ട്രീകളിലേയ്ക്ക് പോകുമ്പോൾ ഓരോ പകുതിയിലെയും മദ്ധ്യ വില ആ സബ്-ട്രീയുടെ മൂലം ആയിരിയ്ക്കും. ഇങ്ങനെ കിട്ടുന്ന ഒരു ട്രീയെ [[ബൈനറി ട്രീ]] എന്ന് വിളിയ്ക്കുന്നു. ഉദാഹരണത്തിന് മുകളിൽ കാണിച്ചിട്ടുള്ള അടുക്കിനെ താഴെക്കാണുന്ന ഒരു ബൈനറി ട്രീ ആയി ചിത്രീകരിയ്ക്കാം.
ഈ അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത പരിശോധിയ്ക്കാനായി ഇതിനെ ഒരു [[ട്രീ((കമ്പ്യൂട്ടർ ശാസ്ത്രം)) | ട്രീയോട്]] ഉപമിയ്ക്കാം. മധ്യത്തിൽ ഉള്ള വില ആയിരിയ്ക്കും ട്രീയുടെ [[മൂലം(കമ്പ്യൂട്ടർ ശാസ്ത്രം) | മൂലം]]. ഈ വിലയേക്കാൾ കുറഞ്ഞ അംഗങ്ങൾ ഉള്ള അടുക്കിന്റെ പകുതി ഈ ട്രീയുടെ ഇടത്തെ സബ്-ട്രീയും മറ്റേ പകുതി വലത്തേ സബ്-ട്രീയും ആയി കണക്കാക്കാം. തുടർന്ന് അടുത്ത നിലയിൽ ഉള്ള സബ്-ട്രീകളിലേയ്ക്ക് പോകുമ്പോൾ ഓരോ പകുതിയിലെയും മദ്ധ്യ വില ആ സബ്-ട്രീയുടെ മൂലം ആയിരിയ്ക്കും. ഇങ്ങനെ കിട്ടുന്ന ഒരു ട്രീയെ [[ബൈനറി ട്രീ]] എന്ന് വിളിയ്ക്കുന്നു. ഉദാഹരണത്തിന് മുകളിൽ കാണിച്ചിട്ടുള്ള അടുക്കിനെ വലതുവശത്തു കാണുന്ന ഒരു ബൈനറി ട്രീ ആയി ചിത്രീകരിയ്ക്കാം. ഇനി നമ്മുടെ തിരയൽ എന്ന പ്രവൃത്തിയെ ട്രീയുടെ മൂലം മുതൽ ഉള്ള ഒരു നടത്തം ആയി കാണാം. ആദ്യം മൂലത്തിലുള്ള വിലയുമായി നമ്മുടെ തിരയുന്ന വിലയെ താരതമ്യപ്പെടുത്തുന്നു. അവ തമ്മിൽ തുല്യമാണെങ്കിൽ നമ്മുടെ തിരയൽ ഫലപ്രദമായി, ഇനി തിരയൽ അവസാനിപ്പിയ്ക്കാം. തുല്യമല്ലെങ്കിൽ പിന്നെ നമ്മൾ തിരയുന്ന വില മൂലത്തിലുള്ള വിലയേക്കാൾ കൂടുതൽ ആണോ എന്ന് നോക്കുക, അങ്ങനെ ആണെങ്കിൽ വലത്തേ സബ്-ട്രീയിലേക്കു പോകുക. അല്ലെങ്കിൽ ഇടത്തെ സബ്-ട്രീയിലേയ്ക്കും. ഇങ്ങനെ നോക്കുമ്പോൾ ഏതൊരു വിലയെ കണ്ടു പിടിയ്ക്കാനും ഏറ്റവും കൂടുതൽ നമ്മൾ ട്രീയുടെ അഗ്രം വരെ മാത്രമേ പോകേണ്ടതുള്ളൂ. അതായത് നമ്മൾ നടത്തേണ്ട പരമാവധി താരതമ്യങ്ങളുടെ എണ്ണം എന്ന് പറയുന്നത് ഈ ട്രീയുടെ ഉയരം എത്രയാണോ അതാണ്. <math display="inline">n</math> അംഗങ്ങളുള്ള ഒരു ബൈനറി ട്രീയുടെ ഉയരം <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> ആണ്.{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}. അതുകൊണ്ട് <math display="inline">\log_2</math> ആണ് ബൈനറി തിരയലിന്റെ സമയസങ്കീർണത എന്നു പറയാം.
 
 
 
 
 
 
 
 
 
 
== ഇതും കൂടി കാണുക ==
"https://ml.wikipedia.org/wiki/ബൈനറി_തിരയൽ" എന്ന താളിൽനിന്ന് ശേഖരിച്ചത്