ความสำคัญของ Algorithm

บริษัทชั้นนำของโลกอย่าง Google หรือ Facebook จะเริ่มต้นสัมภาษณ์งานด้วยคำถามที่เข้าใจง่ายก่อน เพื่อลองเชิงดูว่าเรามีความสามารถขนาดไหน บางคนไม่เข้าใจ ไปตอบคำถามสั้นๆ เพราะนึกว่าง่าย แท้จริงแล้วคำถามพวกนี้กลับซ่อนคำตอบที่ลึกลับซับซ้อน เกินกว่าที่จะคาดคิด ลองไปดูกันว่ามันเป็นยังไง? บทความนี้ขอเริ่มต้นด้วยปัญหาง่ายๆก่อน นั่นคือ

มีเลขจำนวนเต็มอยู่ใน array ให้เขียน function หาว่าถ้าหยิบมา 2 ตัว จะมีผลบวกเป็นเลขคี่กี่ชุด

ตัวอย่างเช่น มี array {2, 3, 1, 4} จะมีชุดที่มีผลบวกเป็นเลขคี่คือ

2+3   3+4   1+4
2+1

บางคนอาจจะคิดว่า 2+3 กับ 3+2 ควรจะแตกต่างกัน คิดแบบนี้ก็ได้เหมือนกัน แต่ตอนนี้ขอข้ามไปก่อน โดยไม่เสียนัยสำคัญ

ภาษาคอมพิวเตอร์ส่วนใหญ่จะเริ่มนับ index ของ array ที่เลข 0 นั่นคือ

ช่องที่ 0 มี ค่า 2
ช่องที่ 1 มี ค่า 3
ช่องที่ 2 มี ค่า 1
ช่องที่ 3 มี ค่า 4

ใน array นี้มีสมาชิก 4 ตัว มีตั้งแต่ตัวที่ 0 ถึง 3 มีค่า 2,3,1,4 ตามลำดับ หรืออาจจะเขียนให้มองง่ายกว่าเดิมคือ

ช่อง   0  1  2  3
ค่า    2  3  1  4

ปัญหานี้ให้หาว่ามีชุดที่รวมกันได้เลขคี่กี่ชุด (ชุดละ 2 ตัว) นั่นคือต้องใช้ index สองตัว ให้เป็น i และ j โดยที่ i มีค่าตั้งแต่ 0 ถึง 3 เช่น

int n = 4;
for (int i = 0; i < n; i++) {
.
.
.
}

และ j ก็เริ่มนับจากตัวถัดไปของ i เขียนเป็น j = i + 1 เช่น

int n = 4;
for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
	.
	.
	.
	}
}

อย่าลืมว่า i และ j เป็น index หรือ หรือหมายเลขของช่อง ถ้าต้องการอ่านค่าที่เก็บอยู่ในช่องนั้น ต้องเขียนเป็น a[i] หรือ a[j] แทน (ในภาษา C จะเขียนเป็น a[i] หรือ i[a] ก็ได้เหมือนกัน เพราะ [ ] เป็น operator ที่สลับที่ได้)

คราวนี้ถึงตอนที่จะตรวจสอบว่าผลรวมเป็นเลขคู่หรือคี่ ก็ใช้เครื่องหมาย % หรือ เศษของการหาร เช่น 5 % 3 ได้ 2 หรือ 5 % 2 ได้ 1 นั่นคือ 5 เป็นเลขคี่

int r = ( a[i] + a[j] ) % 2;

จากนั้นค่อยดูว่า r เป็นเลขคู่หรือเลขคี่ ตัวอย่าง function ในภาษา C

int count(int a[], int n) {
	int c = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int r = (a[i] + a[j]) % 2;
			if (r != 0) {
				c++;
			}
		}
	}
	return c;
}

ตัวอย่าง function ข้างบนนี้เป็นคำตอบที่ดี แต่ยังดีไม่พอ ถ้ามองในมุมของ algorithm คือมันใช้เวลาเป็น O(n^2) นั่นคือถ้ามีตัวเลข 1 ล้านตัว function ข้างบนนี้ต้องทำงาน 1 ล้านล้านครั้ง ถ้าใช้เวลา 1 ใน ล้านวินาที เพื่อเข้าถึงข้อมูลแต่ละครั้ง ดังนั้นต้องใช้เวลาทั้งหมด 1 ล้านวินาทีในการทำงาน เวลา 1 ล้านวินาทีที่ว่านี้จริงๆแล้วมากกว่า 10 วัน

แทนที่จะใช้เวลารอคำตอบ 10 วัน ลองคิดวิธีที่ดีกว่านี้ในการแก้ปัญหา สิ่งที่น่าสนใจคือ ปัญหาด้านคอมพิวเตอร์มักจะถูกแก้ได้โดยการคิดจากข้อมูลจำนวนไม่มาก เช่น มี 1 – 5 ตัว เพื่อหาว่า pattern มันจะเป็นยังไง วิธีนี้คือ Mathematical Induction นั่นเอง เช่น ถ้ามีเลขแค่ 2 ตัว อย่าง {1,1} {1,2} {2,1} หรือ {2,2} จะเป็นยังไง

{1,1} ไม่มีผลรวมเป็นเลขคี่
{1,2} มี 1 ชุดที่มีผลรวมเป็นเลขคี่
{2,1} มี 1 ชุดที่มีผลรวมเป็นเลขคี่
{2,2} ไม่มีผลรวมเป็นเลขคี่

คำถามตอนนี้คือ เลขคี่ มาจากไหน? ก็มาจาก เลขคี่ + เลขคู่ หรือ เลขคู่ + เลขคี่ ดังนั้นถ้านับว่าใน array มีเลขคี่กี่ตัว เลขคู่กี่ตัว แล้วนำมาคูณกัน จะได้คำตอบทันที เพราะเมื่อหยิบเลขคี่มา 1 ตัว จะมีเลขคู่ให้รวมกับมัน ตามจำนวนที่นับได้นั่นเอง ตัวอย่าง function ในภาษา C

int count2(int a[], int n) {
	int o = 0;
	int e = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] % 2 == 0) {
			e++;
		} else {
			o++;
		}
	}
	return o * e;
}

คำถามเพิ่มเติม

– ให้เขียน function รับ array ของจำนวนเต็มเข้ามานับว่ามีกี่คู่ที่รวมกันได้เลขคู่

– ให้เขียน function รับ array ของจำนวนเต็มเข้ามานับว่ามีกี่คู่ที่รวมกันแล้วหารด้วย 10 ลงตัว

นี่คือ code ทั้งหมดของบทความนี้ ลองเรียกใช้งาน count() แบบแรกจะเห็นข้อแตกต่าง

#include <stdio.h>
#define MAX 1000000
int a[1000000];
// a basic version
int count(int a[], int n) {
	int c = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int r = (a[i] + a[j]) % 2;
			if (r != 0) {
				c++;
			}
		}
	}
	return c;
}
// an improved version
int count2(int a[], int n) {
	int o = 0;
	int e = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] % 2 == 0) {
			e++;
		} else {
			o++;
		}
	}
	return o * e;
}
// starting point
int main(void) {
	for (int i = 0; i < MAX; i++) {
		a[i] = 0;
	}
	a[0] = 1;
	int c = count2(a, MAX);
	printf("%d\n", c);
	return 0;
}


Credit : https://article.land/beer/%E0%B8%84%E0%B8%A7%E0%B8%B2%E0%B8%A1%E0%B8%AA%E0%B8%B3%E0%B8%84%E0%B8%B1%E0%B8%8D%E0%B8%82%E0%B8%AD%E0%B8%87-algorithm

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *