Asymptotic analysis/ big O , Omega, Theta notations/(සිංහලෙන්)

ඔයාල algorithms ගැන ඉගනගන්නවනම්  big O , Omega, Theta notations කියන්නෙ ඉතාම වැදගත් වන දේවල් ටිකක්.අපි අද බලමු මොනවද මේ  big O , Omega, Theta කියන්නෙ කියල , ඒ වගේම ඒවගෙන ගණන් දුන්නම හදන්නෙ කොහොමද කියල. 

Running Time

ඕනෑම algorithm එකක හෝ  programme  එකක efficiency එක මනින්නෙ running time  එක මගින්.මේ running time එක කියන එකට හරියටම නිශ්චිතවම එක අගයක් කියන්න අමාරුයි.ඒක input size  එක මත රඳා පවතින ශ්‍රිතයක්. එකම   programme එකේ උනත් input එක වෙනස් වෙනකොට running time එක වෙනස් වෙනව. අපි මේක චූටි උදාහරණයකින් පැහැදිලිකරගනිමු.

                   

මේ array එකේ  items  6 ක් තියනව. අපි හිතමු අපිට මේකෙ 0 වෙනි index එකේ තියන item එක, ඒ කියන්නෙ 5 හොයන්න ඕනෙ කියල, අපි මේ arraynඑකේ තියන item  එක , එක පිළිවෙලට search  කරල බලනව අපිට ඕන එක තියනවද කියල.මේකෙ මුලින්ම තියෙන්නෙ 5 නිසා බලපු ගමන්ම 5 අහු වෙනව එහිදී running time  එක  1ක් වෙනව. අපිට 23 හොයාගන්න ඕන උනොත් අපිට 5 වෙනි එකට වෙනකම් searchකර කර යන්න වෙනව. එහිදී 6ක් searchකරල බලපු නිසා running time  එක 6ක් වෙනව.

          මෙන්න මේ array  එක search කරන එක සැලකුවහම, ඒකට අපිට ගන්න පුළුවන් අඩුම අගය තමයි 1. ඒක මෙකෙ bsest case එක කියල හඳුන්වනව.එන්න පුළුවන් වැඩිම අගය තමයි 6 ඒක මේකෙ worst case එක කියල හඳුන්වනව. මේ අනුව item n ගානක් තියන array  එකක් සැලකුවහම best case  එක 1ත් worst case එක nත් වෙනව. මේ දෙකේ මධ්‍යනය average case  එක කියල හඳුන්වනව ඒක n/2 ක් වෙනව. මේ අනුව running time  එකක එකට best case එක හා worst case එක අතර ඕනෑම අගයක් එන්න පුළුවන්. අපිට ඒක හරියටම කියන්න බැහැ ඒකෙ running time අගය input size එක මත රඳා පවතිනව.

             Best Case ≤ Running Time ≤ Worst Case

මේ best case එක lower bound එක ලෙසත් worst case එක upper bound එක ලෙසත් හඳුන්වනව. එවිට

          Lower Bound ≤ RunningTime≤ Upper Bound

Asymptotic Notations

අපි දැන් බලමු asymptotic notation කියන්නෙ මොකද්ද කියල.අපිට දක්නට ලැබෙන running times ප්‍රධාන වශයෙන් කොටස් තුනකට බෙදනව,

Big O notation (O)

Omega ( Ω)

Theta (θ)

        මෙතනදි අපි input size  එක ශ්‍රිතයක් ආකාරයෙන් වෙනස් කරල ඊට අදාළව running time එක ප්‍රස්ථාරගත කරනව. input size එක n නම්,

      input size එකේ ශ්‍රිතය = g(n), 

      running time එකේ ශ්‍රිතය = f(n),

ලෙස  ගනිමු.

Big O notation (O)(Worste Case)

මෙහිදී c යනු ඕනෑම නියතයක් නම් n₀ යන යම්කිසි input size එකකට ඉහළ තියන ඕනෑම input එකකදි  input size ශ්‍රිතය c වලින් ගුණ කලවිට ලැබෙන අගය[c g(n) ] running time එකේ ශ්‍රිතයට [f(n)]වඩා වැඩි නම්. එනම්,

                f(n) ≤ c g(n)  for all n ≥  n₀

මෙවැනි running time එකක්  O(n) ආකාරයේ running time එකක් ලෙස හැඳින්වෙයි. නමුත් running time එකක් රිණ විය නොහැකි නිසා,

              0 ≤ f(n) ≤ c g(n) for all  n ≥ n₀

Omega ( Ω) (Best Case)

මෙහිදී c යනු ඕනෑම නියතයක් නම් n₀ යන යම්කිසි input size එකකට ඉහළ තියන ඕනෑම input එකකදි  input size ශ්‍රිතය c වලින් ගුණ කලවිට ලැබෙන අගය[c g(n) ] running time එකේ ශ්‍රිතයට [f(n)]වඩා අඩු නම්. එනම්,

               0  ≤  c g(n)  ≤ f(n)    for all  n ≥ n₀

   මෙවැනි running time එකක් Ω(n) ආකාරයේ එකක් ලෙස හඳුන්වයි.

Theta (θ)(Avarage Case)
මෙහිදී අපිට  c₁ හා  c₂ කියන නියතයන් දෙකක් ගන්න වෙනව එවිට,
               0 ≤  c₁  g(n) ≤  f(n) ≤ c₂ g(n)  for all  n ≥ n₀
වනපරිදි c₁  හා c₂  නියත දෙකක් තිබේනම් මෙවැනි running time එකක් θ (n)    ආකාරයේ running time   එකක් ලෙස හඳුන්වයි.

මේ අවස්ථා තුන සලකල බැලුවහම O(n) වලදි නිතරම input size එකට වඩා running time එක අඩුවෙන නිසා efficiency එක වැඩියි.  Ω (n) වලදි  input size එකට වඩා running time එක වැඩිවෙන නිසා efficiency  එක අඩුයි. θ(n) වලදි running time එක යම්කිසි අගයන් දෙකක් අතර සාමාන්‍ය මට්ටමක පවත්වාගන්නවා.
Problems
අපි දැන් runnin time function එක දුන්නහම ඒක මොන ආකාරයේද කියල ඔප්පු කරන විදිය බලමු.
(1)Show that 30n+8 is O(n).
මෙවැනි ගණනකදී නිතරම O() එක ඇතුලෙ දෙන function එක input function එක වන අතර එලියෙන් දෙන function එක running time function එකයි.එමනිසා,
  f(n) = 30n + 8
  g(n) = n
අප පෙන්විය යුත්තේ
        30n + 8   ≤  cn    for all  n ≥ n_{0
මෙහි c ට හා}  n₀ ට ගැලපෙන අගයන් දෙකක සොයාගත යුතුය.
      30n + 8 ≤  30n + 8n = 38n for all  n ≥ 1
       30n + 8 ≤ 38 n
        c = 38 , n₀ = 1
මෙතනදී එක එක අයට වෙනස් පිළිතුරු ලැබිය හැක. නමුත් ඕනෑම එක c අගයක් සඳහා පැවතිය හැක්කේ එක් n₀ අගයක් පමණි. ඒ කියන්නෙ c = 38 වෙලා  n₀ =  2 වෙන්න බැහැ කියල. නමුත් c වලට හා n₀ වලට ගන්න පුලුවන් අගයන් වෙනස් වෙමින් මෙයට ගැලපෙන පිළිතුරු {c,n₀} කුලක කිහිපයක් තිබිය හැක.
         Let c = 31 , 30n + 8 ≤  31n = 30n + n
          then when n ≥ 8
          cn = 31n = 30n + n > 30n+8,
           so 30n+8 ≤  cn when c= 31 , n₀  = 8.
මෙම පිළිතුරද නිවැරදි වෙයි.
(2)Prove that 100n + 5 = O(n²)
–100n + 5 ≤ 100n + n = 101n ≤ 101n²
for all n ≥ 5
n₀ = 5 and c = 101 is a solution
or
–100n + 5 ≤ 100n + 5n = 105n ≤ 105n² for all n ≥ 1

n₀= 1 and c = 105 is also a solution

(3)5n² = Ω(n)

 cn ≤ 5n²
 c = 1 and n₀ = 1
එමෙන්ම යම්කිසි ශ්‍රිතයක් දුන්විට අදාල notation එකට අසමානයැයි පෙන්වීමටද හැකි විය යුතුය.
(4)100n + 5 ≠ Ω(n²)
ඔප්පු කළ යුත්ත: 0 ≤ cn² ≤ 100n + 5
මෙය නිවැරදි ලෙස ගෙන ගණන සාදයි.
    100n + 5 ≤ 100n + 5n (for all  n ≥  1) = 105n
    cn² ≤  105n
    n(cn – 105) ≤ 0
    Since n is positive
     cn – 105 ≤  0
      n ≤  105/c
නමුත් මෙහි n කියන්නේ input size  එක ඒකට අපිට n₀ සිට අනන්තය දක්වා ඕනෑම අගයක් ගතහැකි විය යුතුයි. අපි මෙහිදී  nහි n₀ වල සිට අනන්තය  දක්වා ඕනැම අගයකට මෙය සත්‍ය වන බව ඔප්පු කළ යුතුයි.නමුත් මෙතන  n ≤  105/c ලෙස ලැබිල තියනව. n කිසියම් අගයකට වඩා කුඩා වෙන්න බැහැ. එමනිසා මෙය contradiction එකකි.
100n + 5 ≠ Ω(n²)
මන් හිතනව ඔයාලට මේ පාඩම ටිකක් හරි තේරෙන්න ඇති කියල. ඔයාලට මේ post එකෙන් පොඩි හරි උදව්වක් උනානම් comment එකක් දාල යන්න අමතක කරන්න එපා.