Big-O Notation

Big-O Notation ဟာ program တစ္ခုဟာ ဘယ္ေလာက္ ထိ ထိေရာက္မႈရိွလဲ။ Data မ်ားလာေလေလ ဘယ္ေလာက္ ထိ အဆင္ေျပႏိုင္မလဲ ဆိုတာကို ေဖာ္ျပေပးဖို့ အတြက္ အသံုးျပဳၾကပါတယ္။ ျပီးခဲ့တဲ့ program ၂ ခုမွာ ဆိုရင္ေတာ့ ပထမ program ဟာ n ရဲ႕ size ေပၚမွာ မူတည္ျပီးေတာ့္ ၾကာျမင့္ပါတယ္။

import time def sum_of_n_loop(n): the_sum = 0 for i in range(1,n+1): the_sum = the_sum + i return the_sum def sum_of_n_eq(n): return n * (n+1) / 2 start = time.time() for i in range(100000,100100): sum_of_n_loop(i) end = time.time() print("Time is %.7f second" % (end-start)) start = time.time() for i in range(100000,100500): sum_of_n_eq(i) end = time.time() print("Time is %.7f second" % (end-start))

function ၂ ခု ကို ယွဥ္ၾကည့္ရင္ သိသိသာသာ ကြာျခားတာကို ေတြ႕ႏိုင္ပါတယ္။

ပထမ function ဟာ 1 ကေန ျပီးေတာ့ n ထိ သြားပါတယ္။ တနည္းေျပာရင္ အၾကိမ္အေရ အတြက္ n ထိ အလုပ္လုပ္ရတယ္။ array ၁၀၀ ရိွရင္ အၾကိမ္ ၁၀၀ အလုပ္လုပ္ရတယ္။ ဒီေတာ့ ကၽြန္ေတာ္တို႕O(n) လို႕ သတ္မွတ္ပါမယ္။

ဒုတိယ function ကေတာ့ ၁ ၾကိမ္သာ အလုပ္လုပ္တယ္။ n က 1000 ျဖစ္ေနလည္း ၁ ၾကိမ္သာ အလုပ္လုပ္တယ္။ အျမဲတန္း constant ပဲ။ n ရဲ႕ တန္ဖိုးေပၚလိုက္ျပီး ေပါင္းလဲမႈမရိွဘူး။ ဒါေၾကာင့္ O(1) လုိ႕ ဆိုပါတယ္။

ကၽြန္ေတာ္တုိ့ အေနနဲ႕ graph ဆြဲၾကည့္လိုက္ရင္ အထက္ပါ ပံု အတိုင္း ျမင္ရပါလိမ့္မယ္။

Big-O Notation မွာ ေအာက္ပါ function ေတြ ရိွပါတယ္။

f(n) Name
1 Constant
log(n) Logarithmic
n Linear
n log(n) Log Linear
n ^ 2 Quadratic
n ^ 3 Cubic
2 ^ n Exponential

graph အေနနဲ႕ ၾကည့္မယ္ ဆိုရင္ ေအာက္ပါ ပံုအတိုင္း ေတြ႕ႏိုင္ပါတယ္။

1 ႏွင့္ log(n) က အေကာင္းဆံုး algorithm ေတြပါ။ n ကေတာ့ ပံုမွန္ ေပါ့။ n log(n) ဟာ အစ ပိုင္းမွာ n ထက္ ျမန္ႏိုင္ေပမယ့္ data မ်ားလာရင္ ေႏွးလာပါလိမ့္မယ္။ n ^ 2 ႏွင့္ 2 ^ n ဟာ အစပိုင္းမွာ မကြာေပမယ့္ ေနာက္ပိုင္း data မ်ားလာေလေလ ကြာလာေလေလ ကို ေတြ႕ႏိုင္ပါတယ္။ n ^ 3 ကေတာ့ အေႏွးဆံုးလို႕ ဆိုရပါမယ္။

Function

Big O မွာ ဘယ္ function ေတြ ဟာ ဘာအတြက္လဲဆိုတာကို ေလ့လာရေအာင္။

Constant

Constant ကေတာ့ ရွင္းပါတယ္။

a = b + 1

looping ေတြ ပါဝင္မေနပါဘူး။ processing ကို တစ္ေၾကာင္းတည္းႏွင့္ အလုပ္လုပ္ပါတယ္။

Logarithmic

array ကို တဝက္ပိုင္းျပီး loop ပတ္သည့္ algorithm ေတြကို log(n) ႏွင့္ သတ္မွတ္ပါတယ္။ ဥပမာ binary search ပါ။

while (n > 1):
    n = n // 2

Linear

Looping တစ္ခုတည္းပါရင္ေတာ့ linear ပါ။

for i in range(len(array)):
    print(i)

ဒါမ်ဳိးဟာ O(n) ျဖစ္ျပီးေတာ့ linear ျဖစ္ပါတယ္။

Log Linear

log linear ဟာ merge sort, quick sort လိုမ်ဳိး sorting ေတြမွာ ေတြ႕ရပါမယ္။

Quadratic

ဒါကေတာ့ looping ၂ ထပ္ အတြက္ပါ။

for i in range(len(array)):
    for k in range(len(array)):
        print(k)

looping ၂ ထပ္ ကိစၥေတြဟာ O(n^2) ႏွင့္ တူညီပါတယ္။

Cubic

ဒါကေတာ့ looping ၃ ထပ္ ကိစၥေတြေပါ့။

for i in range(len(array)):
    for k in range(len(array)):
        for w in range(len(array)):
            print(i+k+w)

Exponential

ဒါကေတာ့ ေတြ႕ရတာ ရွားပါတယ္။ password ေတြကို ျဖစ္ႏိုင္သည့္ combinations ေတြ ေပါင္းျပီး generate လုပ္သည့္ algorithm ေတြမွာ ေတြ႕ရတတ္ပါတယ္။

Big-O Notiation ကို ဘယ္လို တြက္မလဲ

အခု ကၽြန္ေတာ္တုိ႕ Big-O Notiation အေၾကာင္း အနည္းငယ္ သိပါျပီ။ ကၽြန္ေတာ္တုိ႕ အေနနဲ႕ ဘယ္လို တြက္ရမလဲ ဆိုတာကို သိဖို႕လိုပါတယ္။

1. Diffrent steps get added

အကယ္၍ algorithm မွာ မတူညီသည့္ အဆင့္ေတြ ပါလာခဲ့ရင္ Big O ကို ေပါင္းေပးရပါတယ္။

doStep1() #O(a)
doStep2() #O(b)

အဲဒါဆိုရင္ O(a+b) ျဖစ္ပါတယ္။

2. Drop constanst

Big O မွာ constant တန္ဖိုးေတြပါဝင္ခဲ့ရင္ ျဖဳတ္လိုက္ဖို႕ လိုက္ပါတယ္။

def minmax1(array):
    min = 0
    max = 0
    for k in array:
        min = MIN(k,min)
    for k in array:
        max = MAX(k,max)
def minmax2(array):
    min = 0
    max = 0
    for k in array:
        min = MIN(k,min)
        max = MAX(k,max)

ဒီ function ၂ ခုကို ယွဥ္လိုက္ရင္ ပထမ function ဟာ O(n+n) ႏွင့္ ဒုတိယကေတာ့ O(n) လို႕ ဆိုႏိုင္ပါတယ္။ O(n+n) = O(2n) ျဖစ္ပါတယ္။ သုိ့ေပမယ့္ Big O Nototation တြက္သည့္ အခါမွာ constant တန္ဖိုးေတြကို ျဖဳတ္ခ်ခဲ့ရပါတယ္။ ဒါေၾကာင့္ program ၂ ခုလံုးဟာ O(n) လို႕ပဲ သတ္မွတ္ပါတယ္။

3. Different Input, different variable

for c in array1:
    for h in array2:
        x = x + 1

ဒီ code ေလးကို ၾကည့္လိုက္ရင္ array ရိွသေလာက္သြားတယ္။ looping ၂ ခု ဆိုေတာ့ n ^ 2 ျဖစ္မယ္လို႕ထင္စရာ ျဖစ္ပါတယ္။ တကယ္တန္းေတာ့ O(a*b) ပါ။ a ကေတာ့ array1 ရဲ႕ size ျဖစ္ျပီး b ကေတာ့ array2 ရဲ႕ size ပါ။ အကယ္၍ variable တူခဲ့ရင္ေတာ့ n ^ 2 ျဖစ္ပါမယ္။

for c in array1:
    for h in array1:
        x = x + 1

ဒီ code ဆိုရင္ looping ရဲ႕ variable တူပါတယ္။ ဒီ array size ကိုပဲ ၂ ထပ္ ပတ္ရတာကို ေတြ႕ႏိုင္ပါတယ္။ ဒါေၾကာင့္ (n*n) ျဖစ္သည့္အတြက္ေၾကာင့္ O(n^2) ျဖစ္ပါတယ္။

4. Drop non-dominate terms

အကယ္၍ n ေတြဟာ တစ္ခု ထက္မက ပါခဲ့ရင္ တန္ဖိုး တစ္ခုကိုပဲ ယူပါတယ္။ ဥပမာ။

min = 0
for c in array1:
    min = MIN(c,min)

for c in array1:
    for h in array1:
        print(c,h)

ဒီ code မွာ ပထမ loop က O(n) ျဖစ္ပါတယ္။ ဒုတိယ loop ကေတ့ O(n^2) ျဖစ္ပါတယ္။ ဒီေတာ့ ၂ ခုေပါင္းေတာ့ O(n+n^2) ရပါတယ္။

Big O notation ဟာ upper bound ျဖစ္သည့္ အတြက္ n ႏွင့္ n^2 မွာ တန္ဖိုး ပိုၾကီးသည့္ n^2 ကိုသာယူပါတယ္။ ဒါေၾကာင့္ program ရဲ႕ Big O Notation ဟာ O(n^2) ျဖစ္ပါတယ္။

Array Sorting Algorithm

ကၽြန္ေတာ္တုိ့ ျပီးခဲ့တဲ့ အခန္းေတြမွာ array ကို sorting လုပ္ခဲ့ပါတယ္။ Array sorting Big O Notation ကို ေအာက္ပါ ဇယားမွာ ေတြ႕ႏိုင္ပါတယ္။

Name Big O Notation
Bubble Sort O(n^2)
Selection Sort O(n^2)
Insertion Sort O(n^2)
Shell Sort O(n*log(n)) သည္ အေကာင္းဆံုး ရႏိုင္ေျချဖစ္ျပီး O(n ^ 1.25) သည္ ျဖစ္ႏိုင္ေျခရိွသည့္ ပ်မ္းမွ် တန္ဖိုးျဖစ္သည္
Merge Sort O(n log(n))
Quick Sort O(n log(n))

အခု sorting algorithm အခ်ဳိ႕ကို Big O နဲ႕ ထုတ္ၾကည့္ရေအာင္။

Bubble Sort

Bubble sort algorithm ကို ျပန္ၾကည့္ရေအာင္။

def bubble_sort(array):
    for num in range(len(array) - 1,0,-1):
        for i in range(num):
            if array[i] > array[i+1]:
                temp = array[i]
                array[i] = array[i+1]
                array[i+1] = temp
    return array

Bubble sort ဟာ array ကို ပထမ အၾကိမ္မွာ array အခန္း တစ္ခု ေလ်ာ့ပတ္တယ္။ ဒုတိယ အၾကိမ္ ၂ ခုေလ်ာ့ပတ္တယ္။ ေနာက္ဆံုး 0 ေရာက္သည့္ အထိ loop ပတ္တယ္။ တနည္းေျပာရရင္

(n-1) + (n-2) + ... + 1 + 0 

လို႕ဆိုႏိုင္ပါတယ္။ အဲဒါဟာ n(n-1)/2 ႏွင့္ တူပါတယ္။ တနည္းဆုိရင္ 1/2(n^2-n) ႏွင့္ တူတယ္လို႕ ဆိုႏိုင္ပါတယ္။ ဒါေၾကာင့္ O(1/2(n^2-n)) ျဖစ္ပါတယ္။ constant ျဖုတ္ခ် ဖို႕လိုသည့္ အတြက္ O(n^2-n) ျဖစ္ပါတယ္။ n^2 က n ထက္ ပိုၾကီးသည့္အတြက္ bubble sort ဟာ O(n^2) ျဖစ္ပါတယ္။

Merge Sort

Merge sort ဟာ အျခား sorting algorithm ေတြထက္ ပိုျမန္ပါတယ္။ သူက O(nlogn) ျဖစ္သည့္ အတြက္ေၾကာင့္ပါ။ Merge sort algorithm ကို ျပန္ၾကည့္ ရေအာင္။

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
    while left_idx < len(left) and right_idx < len(right):

        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    if left_idx < len(left):
        result.extend(left[left_idx:])
    if right_idx < len(right):
        result.extend(right[right_idx:])
    return result

def mergesort(w):

    if len(w)<2:
        return w
    else:    
        mid=len(w)//2
        return merge(mergesort(w[:mid]), mergesort(w[mid:]))

recursive လုပ္ထားတယ္။ တနည္းအားျဖင့္ array size အတိုင္း ပထမ အဆင့္ loop ပတ္ေနတာကို ေတြ႕ႏိုင္ပါတယ္။ သုိ့ေပမယ့္ ဒုတိယ loop မွာ array size ကို တဝက္ခ်ဳိးလိုက္တာကို ေတြ႕ရပါလိမ့္မယ္။ array size တစ္ဝက္ ခ်ဳိးလိုက္သည္မ်ားကို log(n) ဟု ဆိုခဲ့ပါတယ္။ log(n) ေတြဟာ array size အၾကိမ္ အေရ အတြက္ အလုပ္လုပ္ရပါတယ္။ ဒါေၾကာင့္ n log(n) ျဖစ္ပါတယ္။ Big O အရ ဆိုရင္ O(n log(n) ) ျဖစ္ပါတယ္။

အခုဆိုရင္ေတာ့ Big O notation အေၾကာင္း အနည္းငယ္ တီးမိ ေခါက္မိပါျပီ။ ကၽြန္ေတာ္ အခု ေဖာ္ျပထားသည္မွာ Big O notation ၏ အေၾကာင္းအရာ အနည္းငယ္မွ် သာ ျဖစ္ပါတယ္။

results matching ""

    No results matching ""