Thursday, April 8, 2010

ඇල්ගොරිතම විශ්ලේෂණය( Analysis of Algorithms )

මොකක්ද මේ ඇල්ගොරිතම විශ්ලේෂණය කියන්නේ...

"To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity)."
- en.Wikipedia.org

ඒ කියන්නේ...

"පරිගණක වැඩසටහනක් විශ්ලේෂණය කිරීම් යනු, එම වැඩසටහන ක්‍රියාත්මක කිරීමට අවශ්‍ය වන, කාලය සහ මතකය (Time and Space) වැනි සම්පත් ප්‍රමණය නීර්ණය කිරීමයි. බොහෝමයක් ඇල්ගොරිතම නිර්මාණය කර ඇත්තේ අභිමත ප්‍රදාන ප්‍රමාණයක් සමඟ ක්‍රියා කිරීමටයි. සාමාන්‍යයෙන් ඇල්ගොරිතමයක කාර්යක්ෂමතාවය හෝ ක්‍රියාත්මක වන කාලය: ප්‍රදාන ප්‍රමාණය, පියවර ප්‍රමාණය හෝ මතක සන්චිත, පිලිබඳ වූ ශ්‍රිතයක් ලෙස දැක්වේ."

සරලව කිව්වොත්, අපි මොකක් හරි ඇල්ගොරිතමයක් ලිව්වම ඒ ඇල්ගොරිතමය සාමාන්‍යයෙන් කොච්චර දුරට ඒක කාර්‍යක්ෂම ද කියල බලාගන්න තමයි මේ විශ්ලේෂණය කරන්නෙ.

මේක කරන ක්‍රමය අපි උදාහරණයකින්ම බලමු..
හොඳයි, ඕනෑම සංඛ්‍යා පේලියක් ප්‍රදානය කලාම ඒක ආරොහණ පිළිවෙලට සැකසීම() සඳහා ඇල්ගොරිතමයක් ලියන ක්‍රමයක් සලකමු. දැනට මේ කාර්යය සඳහා ඇල්ගොරිතම (sorting algorithms) විවිධ තාරිකික ක්‍රම වලට නිර්මාණය කර තිබෙනවා.ඒවා විවිධ නම් වලින් හඳුන්වනවා. මොකද මේක ගොඩක් වෙලවට අවශ්‍ය වන ඇල්ගොරිතම වර්ගයක් නිසා.අපි මේකෙ තියෙන "බබල් සොර්ට්" (Bubble Sort) කියන ඇල්ගොරිතමය සලකමු. ඒක ගොඩක් සරල ඇල්ගොරිතමයක්. ඒක ක්‍රියා කරන ආකාරය සරලව කිව්වොත්..,

"මෙතනදි කරන්නෙ පිලිවෙළින් මුල සිටම එක ලඟ තියෙන සංඛ්‍යා දෙකෙන් දෙක අරගෙන මුල් සංඛ්‍යාව දෙවෙනි සංඛ්‍යාවට් වඩා විශාල නම්, ඒ දෙක මාරු කරනව. මේ කාර්යය දිගටම සංඛ්‍යා පේලියේ අන්තිම සංඛ්‍යා ජොඩුව දක්වාම කරගෙන යනව. මේ විදිහට ඒ ජොඩු ගණනට සමාන වාර ගණනක් මේක කරනව. එතකොට මුළු පේලියම පිළිවෙලට සැකසෙනව. මේක ගැන වැඩි විස්තර මෙන්න."

ඉතින් දැන් අපි මේ ඇල්ගොරිතමය විශ්ලේෂණයට භාජනය කරමු..,



බබල් සොර්ට් ඇල්ගොරිතමය





n ← array_length
for i ← n-1 to 1
for j ← 1 to i
if a[j] > a[j+1]
temp ← a[j]
a[j] ← a[j+1]
a[j+1] ← temp




දැන් බලමු අපි මේ ඇල්ගොරිතමය විශ්ලේශණය කරන්නෙ කොහොමද කියලා..
මුලින්ම මෙම ඇල්ගොරිතමයේ පේලියෙන් පේලියට සිදුකරන කාර්යයන් බලමු,


1.) n ← array_length
. . . . . . . . . . . . . . . . . . . . - සංඛ්‍යා පේලියේ සංඛ්‍යා ගණන "n" ට ආදේශ කිරීම.

2.) for i ← n-1 to 1
. . . . . . . . . . . . . . . . . . . . - i ට ආරම්භක අගය වන (n-1) ලබා දීම හෝ i හි අගය 1 කින් අඩු කිරීම. ඉන් පසු, i හි අගය, දී ඇති පරාසය වන 1 ≤ i ≤ (n-1) ට ඇතුලත් දැයි පරික්ෂා කොට, එසේ ඇතුලත් නොවන්නේ නම් මෙම for loop එක අවසන් කිරීම.

3.) for j ← 1 to i
. . . . . . . . . . . . . . . . . . . . - j ට ආරම්භක අගය වන 1 ලබා දීම හෝ j හි අගය 1 කින් වැඩි කිරීම. ඉන් පසු, j හි අගය, දී ඇති පරාසය වන 1 ≤ j ≤ i ට ඇතුලත් දැයි පරික්ෂා කොට, එසේ ඇතුලත් නොවන්නේ නම් මෙම for loop එක අවසන් කිරීම.

4.) if a[j] > a[j+1]
. . . . . . . . . . . . . . . . . . . . - සලකන a[j] සහ a[j+1] සංඛ්‍යා දෙක ආරෝහණ පිලිවෙලට නැත්දැයි බැලීම.(මුල් සංඛ්‍යාව (a[j]) දෙවැනි සංඛ්‍යාවට (a[j+1]) වඩා විශාලදැයි බැලීම)

5.) temp ← a[j]
. . . . . . . . . . . . . . . . . . . . - තාවකාලිකව මුල් සංඛ්‍යාවේ (a[j]) අගය temp නම් විචල්‍යයක් තුළ ගබඩා කර තබා ගැනීම.

6.) a[j] ← a[j+1]
. . . . . . . . . . . . . . . . . . . . - දෙවැනි සංඛ්‍යාව(a[j+1]) පෙර සංඛ්‍යාවට (a[j]) ආදේශ කිරීම.

7.) a[j+1] ← temp
. . . . . . . . . . . . . . . . . . . . - තාවකාලිකව ගබඩා කරගත් a[j] හි තිබූ අගය a[j+1] ට ලබාදීම.


මුලින්ම අපි මේක උදාහරණයක් එක්ක බලමු...
අපි හිතමු මේ සංඛ්‍යා පේලිය තියෙන්නෙ 4 3 2 1 කියල. ඒ කියන්නෙ මෙතනදි,
a = { 4, 3, 2, 1 } සහ n = 4 වෙනව.

පහත වගුවක ආකාරයෙන් දැක්වෙන්නේ මෙම ඇල්ගොරිතමය ඉහත උදාහරණය සඳහා ක්‍රියාත්මක කිරීමේදී සිදුවන කර්යයන් සංක්ෂිප්තව, පියවර වශයෙනි.
(සංක්ෂිප්ත වුවද මෙහි සියලුම පියවරයන් පිළිවෙලින් සම්පූර්ණ වශයෙන් දක්වා ඇති අතර මෙහිදී සංක්ෂිප්ත යැයි කීවේ පේලි කීපයක ප්‍රතිඵල එකවර ගෙන දක්වා අති බැවිනි. )






*"ක්‍රියාත්මක වන ඇල්ගොරිතමයේ පේලි" යනු, ඉහත විස්තර කළ ඇල්ගොරිතම පේලි වේ. එම අවස්ථවේ ක්‍රියත්මක වන පේලි වල අංක පිළිවෙලින් මෙහි දක්වා ඇත.
*"(e)" ලෙස දක්වා ඇත්තේ එම විචල්‍යය (i හෝ j) එම අදාළ loop එකෙහි පරාසය ඉක්මවා ඇති අවස්ථාවයි. එනම් එම අවස්ථාවේදී ඒම අදාළ loop එක අවසන් (exit) වේ.
*රතු වර්ණයෙන් පෙන්වනු ලබන්නේ එම අවස්ථාවේදී සලකනු ලබන සංඛ්‍යා යුගලයයි. ( මෙම යුගලය තෝරාගැනීම සිදුවනු ලබන්නේ i හා j වල අගයයන් මගිනි. )
*නිල් වර්ණයෙන් පෙන්වනු ලබන්නේ එම සංඛ්‍යා යුගලය සැකැස්වීමෙන් පසු අවස්ථාවයි.
*කොළ වර්ණයෙන් පෙන්වනු ලබන්නේ සැකසී අවසන් වු සංඛ්‍යා වේ.( එනම් එම සංඛ්‍යා loop එකේ ඇති iහා j විචල්‍ය වල කලාපයෙන් ඉවත් වී ඇත.)

බබල් සෝර්ට් ඇල්ගොරිතමය මගින්, ඉහත පහළට පිළිවෙලින් දක්වා ඇති ආකාරයට ක්‍රමයෙන් සංඛ්‍යා පේලිය ආරොහණ පිළිවෙලට සැකසේ.
මේ අනුව ඉහත වගුවේ ක්‍රියාත්මක වන ඇල්ගොරිතමයේ පේලි යන තීරුවෙන් මෙම අවස්ථාවේදී, ඇල්ගොරිතමයේ එක් එක් පේලිය ක්‍රියාත්මක වූ වාර ගණන ලබා ගත හැක. නමුත් එම වාර ගණන මෙම ඇල්ගොරිතමයට ලබා දෙන ප්‍රදානය මත රඳා පවතී. එ කෙසේද යත්, ප්‍රදානයේ සංඛ්‍යා ගණන හා එම සංඛ්‍යා තිබෙන පිළිවෙල මත මෙම ඇල්ගොරිතමයේ යම් පේලියක් ක්‍රියාත්මක වන වාර ගණන වෙනස් වේ.නමුත් ඇල්ගොරිතමයකට ලබාදෙන ප්‍රදාන සංඛ්‍යාව(n) ආශ්‍රයෙන් ඇල්ගොරිතමයේ යම් පේලියක් ක්‍රියාත්මක වන වාර ගණන සඳහා ප්‍රකාශණයක් ගොඩ නැගිය හැක. එය ධාවන කාල විශ්ලේෂණය (run-time analysis) ලෙස හැඳින්වේ.

"Run-time analysis is a theoretical classification that estimates and anticipates the increase in running time (or run-time) of an algorithm as its input size (usually denoted as n) increases. Run-time efficiency is a topic of great interest in Computer Science: A program can take seconds, hours or even years to finish executing, depending on which algorithm it implements."
- en.Wikipedia.org

ඒ කියන්නේ...

"ධාවන කාලය විශ්ලේෂණය යනු, ඇල්ගොරිතමයක ප්‍රදානයේ විශාලත්වය (n) වැඩි වීමේදී ඇතිවන ධාවන කාලයේ වැඩි වීම නිමානය කිරීමේ සිද්ධාන්තයකි. ධාවන කාලයේ කාර්යක්ෂමතාවය යනු පරිගණක විද්‍යාව තුළ ඇති ඉතා සැලකිය යුතු විෂයක්ෂේත්‍රයකි. පරිගණක ක්‍රමලේඛනයක්( වැඩසටහනක් ) ක්‍රියා කර අවසන් වීම සඳහා එය ගොඩනගා ඇති ඇල්ගොරිතමයට මත රඳා පවතිමින්, තත්පර, පැය හෝ අවුරුදු කීපයක් වූව ද ගත විය හැක."

එනම්, ධාවන කාලය විශ්ලේෂණය නිවැරදිව නොකරමින් යම් ක්‍රමලේඛයක් ලිවහොත් එය කාර්යක්ෂමතාවය අතින් ඉතා බාල විය හැක. එමනිසා මෙම ධාවන කාල විශ්ලේෂණය ඇල්ගොරිතම සඳහා ඉතා වැදගත් අංගයකි.

අප දැන් ඉහත ඇල්ගොරිතමයේ පේලියෙන් පේලිය ගෙන එසේ ප්‍රකාශණ ගොඩනගමු.
(පහත වාක්‍ය වල, ඉදිරියෙන් දැක්වෙන්නේ අදාල පේලියේ අංකයයි.)

( 1 ) - මෙය ඇල්ගොරිතමයට ලබාදෙන ප්‍රදානයෙන් ස්වායක්ත ව 1ක් වරක් පමණක් ක්‍රියා කරයි.

( 2 ) - මෙම පේලිය i = (n-1) සිට i = 1 දක්වා ද අන්තිමේදී i = 0 දී loop එක අවසන් කිරීම(exit) සඳහා ද ක්‍රියා කරයි. එනම් මෙම පේලිය n වාරයක් ක්‍රියත්මක වේ.

( 3 ) - මෙම පේලිය i හි යම් අගයකදී 1 සිට i දක්වා ක්‍රියාකර i+1 අගයේ දී loop එක අවසන් විම සඳහා ක්‍රියා කරයි. එම නිසා මෙය i හි යම් අගයක දී i+1 වාර ගණනක් ක්‍රියාකරයි.(නමුත් i = 0 විට ක්‍රියා නොකරයි.)∴ මෙය sigma notation වාරයක් ක්‍රියා කරයි.
summention

( 4 ) - මෙම පේලිය i හි යම් අගයකදී 1 සිට i දක්වා ක්‍රියා කරයි. එම නිසා මෙය i හි යම් අගයක දී i වාර ගණනක් ක්‍රියාකරයි.(නමුත් i = 0 විට ක්‍රියා නොකරයි. තවද, j = i+1 විට ද ක්‍රියා නොකරයි.)∴ මෙය sigma notation2 වාරයක් ක්‍රියා කරයි.
summention2

( 5 ),( 6 ),( 7 ) - මෙම පේලි තුන ක්‍රියා කරන වාර ගණන එකම වේ. මෙම පේලි තුන ක්‍රියාකරන ආකාරය ( වාර ගණන ) නිශ්චිතව කිව නොහැක. එය ප්‍රදානය කරන සංඛ්‍යා පේළියේ පිලිවෙල අනුව විචලනය වේ. නමුත් මෙහි උපරිම හා අවම අගයක් ඇත. මෙම අගයන් උපරිම හා අවම වන අවස්ථාවන් පිළිවෙලින් Worst Case හා Best Case ලෙස හැඳින්වෙන අතර ඊට අතරමැදි ඔනෑම අවස්ථාවක් Avarage Case ලෙස හැඳින්වේ.
*මෙම ඇල්ගොරිතමයේ Best Case අවස්ථාව වන්නේ ප්‍රදානයේ සංඛ්‍යා ආරෝහණ පිළිවෙලින් ඇති විටයි. එවිට, 5,6,7 පේලි ක්‍රියාත්මක නොවේ. එනම් 5,6,7 පේලි ක්‍රියාත්මක විය හැකි අවම වාර ගණන 0 ( බිංදුව ) වේ.
*මෙහි Worst Case අවස්ථාව වන්නේ ප්‍රදානයේ සංඛ්‍යා අවරෝහණ පිළිවෙලින් ඇති විටයි. එවිට, 5,6,7 පේලි ද 4 වන පේලිය ක්‍රියා කරන වාර ගණනට සමාන වාර ගණනක් ක්‍රියාත්මක වේ. එය 5,6,7 පේලි වලට ක්‍රියත්මක විය හැකි උපරිම වාර ගණන වේ.
*මේ අනුව සාමාන්‍ය(Average Case) අවස්ථාවකදී, ඉහත සඳහන් උපරිමයත් අවමයත් අතර ප්‍රමාණයක් 5,6,7 පෙලි ක්‍රියත්මක වේ.
*යම් ' අගයකදී 5,6,7 පේලි ක්‍රියා කරන වාර ගණන α යැයි ගෙන මෙම පේලියක් ක්‍රියා කරන මුලු වාර ගණන Σαi ලෙස ලිවිය හැක.

මෙම එක් එක් පේලිය ක්‍රියා කිරීම සඳහා ගතවන කාලයන් එකිනෙකට වෙනස් වේ. එම පේලියක් එක් වරක් ක්‍රියා කිරීමට ගතවන කාලය පහත වගුවේ 'කාලය' නම් තීරුවේ දැක්වේ.
එම කාලයෙන්, අදාළ පේලිය ක්‍රියා කරන වාර ගණන ගුණ කළ විට, එම පේලිය සඳහා පමණක් ගතවන 'මුළු කාලය' ලැබේ.
මෙම කාලයන් එම පරිගණකයේ තත්වයන් මත( මෘදුකාංගමය හා දෘඩාංගමය යන දෙකම ) වෙනස් වේ. එනම් යම් කාර්යයක් කිරීම සඳහා ගතවන කාලය සාමාන්‍ය කාල ඒකක( මිලි තත්පර / තත්පර / දින ) වලින් කිව නොහැක. එය එකම යන්ත්‍රයේ වූවද අවස්ථාවන් දෙකක දී වෙනස් කාලයන් දෙකක් ගත හැක. එමනිසා මෙහිදී නිරපේක්ෂ වශයෙන් කාලයක් මැනිය නොහැක. නමුත් ඇල්ගොරිතම දෙකක් සැසඳීම සඳහා සාපේක්ෂ වශයෙන් යම් ක්‍රමයක් ගොඩනගා ගත හැක.







*එමනිසා ඉහත C1,C2,C3,C4,C5,C6,C7 යන්ත්‍රය මත රඳාපවතින සාධක වේ.


එම නිසා මෙම ඇල්ගොරිතමය සඳහා මුළු ධාවන කාලය(Run time) ඉහත මුළු කාර්යයන් වල එකතුවෙන් ලැබේ,

Run time =
12345678910

පොදු සාධක ගැනීමෙන්,


දැන් පහසුව තකා ඉහත n2 , n , Σαi , n0(නියත පදය) යන ඒවායේ සංගුණකයන් පිළිවෙලින් A , B , C , D වේ යැයි ගනිමු.
එමනිසා,


මෙම A,B,C,D යනු C1,C2,C3,C4,C5,C6,C7යන නියත වලින් සැදි නියතයන් වේ. එමනිසා, ඒවා යන්ත්‍රය( පරිගණකය ) මත රඳා පවතී. එමනිසා, යම් ඇල්ගොරිතම දෙකක් සැසඳීම සඳහා මෙය නුසුදුසුය. එබැවින් මෙහිදී යන්ත්‍රයෙන් ස්වායක්ත ලෙස(machine indipendently) , ධාවන කාල ශ්‍රිතය(run time complexity) මෙසේ f(n) ලෙස දක්වනු ලැබේ,

1234567891011

මෙසේ ලබාගන්නා 'ධාවන කාල ශ්‍රිතය' ඇල්ගොරිතම වල ඇති ඉතා වැදගත් සැලකිය යුතු අංගයක් වන අතර ඇල්ගොරිතම දෙකක් සැසඳීම සඳහා මෙය බෙහෙවින් ඉවහල් වේ.