การหา 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]);

ลองทำเอง

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

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) }

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) }

Comments

4 September, 2010 - 06:40 — Anonymous

Designer Shoes | Cheap Shoes | Casual Shoes| GoldkeyEshop

Designer Shoes strained left knee ligament could sideline him for most or all of the first month of the season, leaving the Steelers with only two healthy quarterbacks — Dennis Dixon and Charlie Batch — for their Sept. 12 opener against Atlanta. Cheap Shoes end Sean McHugh, who missed last season with a knee injury, was the most prominent player cut. Also let go were tight end Eugene Bright, guard Dorian Brooks, offensive tackle Kyle Jolly, wide receiver Brandon London, defensive tackle Scott Paxson, long snapper Matt Stewart, safety Justin Thornton, running back Justin Vincent and linebacker Casual Shoes .

4 September, 2010 - 06:09 — Anonymous