การวิเคราะห์การทำงานของโปรแกรมนั้นสามารถทำให้ผู้เขียนรู้เวลาคร่าวๆ ของโปรแกรมที่เขียน เช่น $O(n), O(n^2), O(nlog(n))$ ซึ่งในการวิเคราห์จะเทียบกับขนาดของ $n$ เป็นหลัก

ในการวิเคราะห์การทำงานของโปรแกรมมีอยู่ 5 สัญกรณ์ (Asymptotic Notation) ได้แก่

• Big-Theta หมายถึง เวลาในการทำงานเฉลี่ย
• Big-O หมายถึง ขอบบนของเวลาในการทำงาน
• Big-Omega หมายถึง ขอบล่างของเวลาในการทำงาน
• Small-O หมายถึง ขอบบนที่มากกว่าเวลาในการทำงาน
• Small-Omega หมายถึง ขอบล่างที่น้อยกว่าเวลาในการทำงาน

ในส่วนของการวิเคราะห์นั้นก็มีอยู่หลายรูปแบบ เช่น การวิเคราะห์แบบถัวเฉลี่ย (Amortized Analysis)

จากภาพนี้สักเกตได้ว่าเวลาในการทำงานจริงของโปรแกรมนั้นไม่เป็นเส้นตรงเสมอไป ในบางช่วงที่มีขนาดของ $n$ มากกว่าอาจจะใช้เวลาในการทำงานน้อยกว่าบางช่วงที่ $n$ น้อยกว่าก็ได้ ดังนั้นการทำงานของโปรแกรมจะต้องวัดกันเมื่อ $n$ มากพอ $(n > n_0)$

โดยใน blog ตอนนี้จะกล่าวถึงเพียงแค่ Big-O เท่านั้น
ในการวิเคราะห์โดยตรงนั้น จะสามารถดูจากโค้ดได้เลย! ยกตัวอย่างเช่น

for(int i=1; i<=n; ++i){
	printf("%d\n", i);
}

โค้ดนี้จะใช้เวลา $O(n)$ เนื่องจากการทำงานของโค้ดนี้จะแสดงค่าตั้งแต่ $1$ จนถึง $n$
ในขณะที่

printf("12");

ไม่ขึ้นอยู่กับขนาดของ $n$ ดังนั้นการทำงานของโค้ดส่วนนี้จะเป็น $O(1)$
$Q:$ แล้วถ้ามีหลายๆ ส่วนของโค้ดจะคิดเวลาในการทำงานรวมของโปรแกรมได้อย่างไร?
$A:$ เราสามารถคิดรวมได้เลยเช่น ถ้าในโค้ดมี 3 ส่วนได้แก่ ส่วนที่มีเวลาในการทำงาน $O(n), O(1)$ และ $O(n^2)$ เราจะคิดแค่ส่วนที่มากที่สุด
กล่าวคือ $O(n + 1 + n^2) = O(n^2)$
ตัวอย่างเช่น

for(int i=1; i<=n; ++i){
	printf("%d\n", i);
}
printf("Hello\n");
for(int i=1, x = 2; i<=n; ++i, ++x){
	for(int j=1; j<=n; ++j){
		printf("%d ", x * j);
	}
	printf("\n");
}

สักเกตว่าในโปรแกรมตัวอย่างนี้มี 3 ส่วน ได้แก่

for(int i=1; i<=n; ++i){
	printf("%d\n", i);
}

ในส่วนนี้จะมีเวลาในการทำงาน $O(n)$

printf("Hello\n");

ในส่วนนี้จะมีเวลาในการทำงาน $O(1)$

for(int i=1, x = 2; i<=n; ++i, ++x){
	for(int j=1; j<=n; ++j){
		printf("%d ", x * j);
	}
	printf("\n");
}

ในส่วนนี้จะมีเวลาในการทำงาน $O(n^2)$
เมื่อนำทั้ง 3 ส่วนมาคิดเวลารวม จะใช้เวลารวมเท่ากับ $O(n^2)$
$Q:$ แล้วในกรณีที่มีหลายส่วนที่มี Big-O เท่ากันจะคิดเวลาในการทำงานรวมของโปรแกรมได้อย่างไร?
$A:$ เราจะคิดแค่ส่วนเดียว เช่น

for(int i=1; i<=n; ++i){
	printf("%d\n", i);
}
for(int i=1; i<=n; ++i){
	printf("%d\n", 2 * i);
}

ในส่วนของโค้ดนี้มีการทำงาน $O(n)$ จำนวน 2 ครั้งทำให้สามารถยุบได้เหลือ $O(n)$ แทนที่จะเป็น $O(2n)$ เนื่องจากเราพิจารณาเมื่อ $n$ มากพอ $(n > n_0)$
จากตัวอย่างด้านบนจะสอดคล้องกับทฤษฎีที่ว่า $O(kn) = O(n)$ เมื่อ $k \in \mathbb{Z}$

IceBorworntat

author