Home › Blogs › winter_snow's blog

การหา Big-O เบื้องต้น (Introduction to Big-O Notation)

8 October, 2009 - 16:32 — winter_snow

พูดง่ายๆแล้ว Big-O Notation หรือ สัญกรณ์โอใหญ่ คืออะไรที่ช่วยเราประมาณ ว่าเวลาในการรันอัลกอริธึม(ส่วนใหญ่จะคิดในกรณีที่แย่ที่สุด หรือ worst-case) จะเป็นประมาณเท่าไหร่ หรือ จะใช้ประมาณเมมโมรี่ที่ใช้ก็ได้

ในบล็อกโพสต์นี้ จะขออธิบายการหา Big-O คร่าวๆก่อน (มีภาคต่อภายหลัง)

ตัวอย่างแรก

สมมติว่ามีโปรแกรมนี้อยู่

for(i=0;i<N;i++)
    a+=i;

จะสังเกตได้ว่า โปรแกรมนี้จะทำงาน
- บรรทัดแรก ครั้งแรกตอนกำหนด $ i=0 $
- บรรทัดแรก อีกประมาณ $ 2N +1 $ รอบเวลาเช็คว่าผิดเงื่อนไขหรือยัง และตอนเพิ่มค่าที่ i
- และทำงานบรรทัดที่สอง $ N $ รอบ
ดังนั้น โปรแกรมนี้ทำงานประมาณ $ 3N+2 $ คำสั่งด้วยกัน

ถ้า $ N $ มีค่าเท่ากับ 10 จะทำงานประมาณ 32 คำสั่ง
ถ้า $ N $ มีค่าเท่ากับ 20 จะทำงานประมาณ 62 คำสั่ง
ถ้า $ N $ มีค่าเท่ากับ 100 จะทำงานประมาณ 302 คำสั่ง

หมายเหตุ: เพราะเป็นการประมาณ จึงถือว่าคำสั่งทุกคำสั่งใช้เวลาเท่าๆกัน (ใช้เวลาคงที่)

$ N $ เพิ่มไปกี่เท่า จำนวนคำสั่ง(เวลาที่ใช้)ก็จะเพิ่มไปเท่านั้นโดยประมาณ
แบบนี้เรียกว่า โปรแกรมนี้รันในเวลา $ O(N) $
คิดจากการ นำจำนวนคำสั่งมา $ O(3N + 2) $ เลือกพจน์ที่มีเลขชี้กำลังสูงสุด(สำหรับกรณีนี้คือ $ O(3N) $) ตัดสัมประสิทธ์ออก เหลือ $ O(N) $

ลองเทียบกับโปรแกรม $ O(N^2) $ ที่รัน $ N^2+N $ คำสั่งดู
ถ้า $ N $ มีค่าเท่ากับ 10 จะทำงานประมาณ 110 คำสั่ง
ถ้า $ N $ มีค่าเท่ากับ 20 จะทำงานประมาณ 420 คำสั่ง
ถ้า $ N $ มีค่าเท่ากับ 100 จะทำงานประมาณ 10100 คำสั่ง

เวลาที่ใช้จะเพิ่มขึ้นอย่างรวดเร็ว

ถ้านำกรณีแรกไปวาดกราฟ จะได้กราฟเส้นตรง
ถ้านำกรณีที่สองไปวาดกราฟ จะได้กราฟพาราโบลา

ตัวอย่างอื่นๆ

จะไม่คิดจำนวนครั้งอย่างละเอียดเหมือนในตัวอย่างข้างบนแล้ว แต่จะคิดอย่างคร่าวๆแทน
กำหนด string เป็นอาเรย์ของ char ความยาว $ N $

if(string[0]=='a')
    printf("yes\n");
else
    printf("no\n");
printf("%d\n", N*(N+1));

ในตัวอย่างนี้ ไม่ว่า $ N $ จะมีค่าเท่าไหร่ แต่ว่าจำนวนคำสั่ง(เวลา)ในการรันก็เท่าเดิม
ดังนั้น โปรแกรมนี้รันในเวลาคงตัว (constant) หรือเขียนได้ว่า $ O(1) $

for(i=0;i<N;i++)
    if(string[i]=='a')
    {
        printf("yes\n");
        break;
    }
 
if(i==N)
    printf("no\n");

ในตัวอย่างนี้ เราอาจจะเจอตัว ‘a’ ตัวแรก ตั้งแต่อาเรย์ช่องแรกๆ หรืออาจจะไม่เจอเลยก็ได้
อาจจะต้องวิ่งในลูป 1 รอบ 2 รอบ หรือ กรณีที่แย่ที่สุด $ N $ รอบ
เพราะเราคำนวณกรณีที่แย่ที่สุด ดังนั้นโปรแกรมนี้รันในเวลา $ O(N) $

for(i=0;i<N;i++)
    a = a+2;
for(i=0;i<N;i++)
    b = b+a;

ในตัวอย่างนี้ เราทำลูปแรก $ O(N) $ ครั้ง ลูปที่สอง $ O(N) $ ครั้ง
รวมเป็น $ O(2N) $ ซึ่งเท่ากับ $ O(N) $ นั่นเอง

for(i=0;i<N;i++)
    for(j=0;j<M:j++)
        a+=i*j;

โปรแกรมนี้รันในเวลา $ O(NM) $ สังเกตว่ามีตัวแปร 2 ตัวใน Big-O ได้

for(i=0;i<N;i++)
    k++;
for(j=0;j<M;j++)
    k++;

โปรแกรมนี้ รันใน $ O(N+M) $
ถึงทั้ง N และ M จะมีเลขชี้กำลังเป็น 1 เท่ากัน
แต่ว่า N และ M เป็นตัวแปรทั้งคู่ และไม่ขึ้นต่อกัน

for(i=0;i<N;i++)
    for(j=i;j<N;j++)
        printf("*");
    printf("\n");

ในตัวอย่างนี้ ลูปในไม่ได้วน $ N $ ครั้งทุกรอบ
รอบแรกวน 1 ครั้ง รอบที่สองวน 2 ครั้ง … รอบที่ $ N $ วน $ N $ ครั้ง
ดังนั้น เมื่อไม่คิดสัมประสิทธิ์ ทำงานทั้งหมดประมาณ $ 1+2+3+\cdots+N = \frac{N(N+1)}{2} $
นั่นคือ $ \frac{1}{2}N^2+\frac{1}{2}N $
เวลาคิด big O พิจาณาพจน์ที่เลขชี้กำลังสูงสุด $ \frac{1}{2}N^2 $
ตัดสัมประสิทธิ์ จะได้ $ O(N^2) $

for(i=0;i<strlen(string);i++)
    printf("%c", string[i]);

ตัวอย่างนี้ ดูเผินๆ เหมือนจะเป็นโปรแกรมที่รันใน $ O(N) $
แต่ว่า! เนื่องจาก ในการวนลูป โปรแกรมจะต้องเรียก strlen(string) ใหม่ทุกรอบ
ซึ่งการหา strlen แต่ละครั้งนั้นใช้เวลา $ O(N) $
ดังนั้นโปรแกรมนี้จึงใช้เวลา $ O(N^2) $
หากแก้ไขให้ใช้เวลา $ O(N) $ อาจทำเช่นนี้

int k = strlen(string);
for(i=0;i<k;i++)
    printf("%c", string[i]);

ลองทำเอง

(โปรดแรเงาเพื่อดูเฉลย)

1.

for(i=0;i<N;i++)
    k++;
for(j=0;j<M;j++)
    k++;
for(i=0;i<M;i++)
    for(j=0;j<M;j++)
        k++;
for(i=0;i<10;i++)
    k++;

เฉลย: { O(N+M^2) }

2.

for(i=0;i<N;i++)
    for(j=5;j<N-2;j++)
        for(k=0;k<N/2;k++)
            printf("a");

เฉลย: { O(N^3) }

3.
กำหนด myFunc()

myFunc()
{
    int i;
    for(i=0;i<M;i++)
        a[i]++;
    return a[0];
}

หา Big-O ของโปรแกรมด้านล่าง
for(i=0;i<5;i++)
    for(j=0;j<N;j++)
        for(k=j;k<N;k++)
            printf("%d", myFunc());

เฉลย: { O(N^2*M) }