ความซับซ้อนของปัญหา (problem complexity)

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

ในการใช้คอมพิวเตอร์คิดคำนวณแก้ปัญหา จำเป็นต้องมีรูปแบบการคำนวณที่ชัดเจน เพราะคอมพิวเตอร์ทำงานตามโปรแกรม แบบการคำนวณเรียกว่า อัลกอริทึม (algorithm) นักคณิตศาสตร์และนักคอมพิวเตอร์สมัยใหม่ได้ค้นคิดอัลกอริทึมสำหรับการคำนวนและแก้ปัญหาต่าง ๆ ไว้มากมาย

แบบคำนวณที่ดีจะต้องตรงกับความต้องการของการแก้ปัญหา มีโครงสร้างของแบบคำนวนที่ชัดเจนเพื่อจะได้ใช้คอมพิวเตอร์ทำงานได้ทั้งนี้เพราะจะต้องแทนแบบคำนวณด้วยโปรแกรมคอมพิวเตอร์แบบคำนวณที่ดีต้องมีประสิทธิภาพในเชิงคำนวณโดยเฉพาะอย่างยิ่งในเรื่องการคำนวณที่เป็นไปได้ใช้เวลาเร็วและใช้พื้นที่หน่วยความจำคอมพิวเตอร์ไม่มากแต่ในทางปฏิบัติเราจำกัดความสามารถของรูปแบบการคำนวณด้วยอัตราการเจริญเติบโต(growth rate) ของเวลาหรือของพื้นที่ที่ใช้โดยหาว่าขนาดของปัญหาของเรามีขนาดเพิ่มขึ้น ขนาดของปัญหาจะขัดกันด้วยขนาดจำนวนของข้อมูลที่ป้อนให้เป็นอินพุตสำหรับการคำนวณ

ตัวอย่างรูปแบบการคำนวณการค้นหาค่าสูงสุดของลำดับตัวเลขข้อมูลชุดหนึ่ง สมมติว่ามีข้อมูลจำนวน n ตัวข้อมูลแต่ละตัวคือ D(1),D(2) ,D(3)...,D(N) และเมื่อได้ค่าสูงสุดจะใส่ไว้ในตัวแปรที่ชื่อว่า MAX

ลำดับขั้นตอนของรูปแบบการคำนวณประกอบด้วย กำหนดค่าเริ่มต้น ให้ I := 1 และ MAX := D(1)   (I คือตัวชี้บอกตำแหน่งสมาชิกลำดับที่ตรวจสอบโดย I จะแบ่งค่าได้จาก 1 ถึง N) ตรวจสอบข้อมูลถ้า D(I) > MAX จะได้ MAX := D(I) ( ถ้าพบค่าใหญ่กว่าก็จับมาใส่แทน MAX เดิม) ตรวจสอบข้อมูลทุกตัวแล้วถ้า I = n จะหยุดการทำงาน ค่าสูงสุดอยู่ใน MAX ค้นหาต่อไปโดยกำหนดให้ I := I+1 แล้วกลับไปขั้นที่ 2 ใหม่ หมายเหตุ เครื่องหมาย := หมายถึงการกำหนดค่าให้ โดยนำค่าจากทางขวามาใส่มาตัวแปรทางซ้าย

รูปแบบการคำนวณเขียนเป็นผังงานสำหรับการคำนวณด้านคอมพิวเตอร์ได้

ความซับซ้อนของปัญหาของรูปแบบการคำนวณจึงอยู่ที่ว่าใช่เวลาการคำนวณเท่าไรถ้าขนาดของข้อมูลเพิ่มขึ้นหรือขึ้นกับค่า n นั่นเอง

พิจารณารูปแบบการคำนวณโดยการจัดเรียงข้อมูลชุดหนึ่ง

การจัดเรียงลำดับจากน้อยมาหามากหรือมากมาหาน้อยมีหลายวิธี เช่น วิธีการหยิบมาสอดไว้ (Insertion sort) โดยทำการสลับไปที่พบเห็นว่าต่างกันอย่างไรลองดูลำดับขั้นตอนการเรียงจากน้อยไปหามากของข้อมูลชุดหนึ่งคือ 5 2 4 6 1 3

เมื่อเรียงลำดับขั้นตอนการคำนวณได้ดังนี้ ..... กำหนดข้อมูล N ตัว เริ่มจาก A[1] … A[N]

สำหรับวนรอบ จาก J:= 2 ไปจนถึง n ทำการคำนวณ key := A[ j ] (ทำการ insert A[ j ] ลงในตำแหน่งลำดับ A(1, ,j-1) i := j - 1 ขณะที่ i > 0 และA[ I ] > key ให้ทำ A[ i+1] := A[ i ] i := i-1 A[ i+1] := key

จากขั้นตอนการปฏิบัติงานนี้ เขียนลำดับขั้นตอนเป็นตาราง เพื่อเปรียบเทียบขั้นตอนการทำงานและเวลาที่ใช้ในแต่ละบรรทัดได้ดังนี้

หากพิจารณาให้ n มีค่าเพิ่มขึ้น พบว่าจำนวนรอบของการคำนวณจาก 1 ถึง 7 จะแปรตามค่า n นั้น คือฟังก์ชันการคำนวณหรือความซับซ้อนแปรตามค่า n

คราวนี้ลองตัวอย่างสิ่งของจำนวน n ชิ้นที่รวมกันเป็นเซต เราสามารแบ่งเป็นเซตย่อยได้เท่าไร

กรณี n = 1 เช่น {A}	แบ่งเป็นเซตย่อยได้ { } และ { A}
กรณี n =2 เช่น {A,B}	แบ่งเป็นเซตย่อยได้ { } ,{A} ,{B},{A,B}
กรณี n =3 เช่น {A,B,C}	แบ่งเป็นเซตย่อยได้ { } ,{ A} ,{ B},{C} ,{A,B},{B,C},{A,C},{A,B,C}

จะเห็นได้ว่าเมื่อมีของ n สิ่ง สามารถจัดเป็นเซตย่อยได้ถึง 2ⁿ เซตย่อย

ดังนั้นถ้าสมมุติว่าในเซตของสิ่งของ n ชิ้น ซึ่งประกอบด้วยสิ่งของหลายสี เราสามารถหาดูว่ามีเซตย่อยอะไรบ้างที่มีสิ่งของสีแดงอย่างน้อยหนึ่งชิ้น

การหาคำตอบในกรณีนี้ต้องคำนวณหาจากเซตย่อยทุกเซตที่เป็นไปได้ ซึ่งต้องคำนวณในความซับซ้อนถึง 2n และถ้าให้ n มีค่าสูง จะไม่สามารถคำนวณได้เพราะจะมีความซับซ้อนเชิงเวลาในการคำนวณสูงมาก

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

รูปแบบการคำนวณ	ฟังก์ชันความซับซ้อนเวลา
A1	n
A2	n log n
A3	n2
A4	n3
A5	2n

ลองคิดดูว่าถ้ากำหนดเวลาคงที่แต่ละรูปแบบจะสามารถแก้ปัญหาได้ขนาดใหญ่เพียงไร โดยให้การคำนวณแต่ละคำสั่งใช้เวลา 1 มิลลิวินาที

รูปแบบ การคำนวณ	ฟังก์ชัน ความซับซ้อนเวลา	ขนาดของ n ที่จะคำนวณได้ในเวลา
		1 วินาที	1 นาที	1 ชั่วโมง
A1	n	1000	6 x 104	3.6 x 106
A2	n log n		4893	2.0 x 105
A3	n2		244	1897
A4	n3		39	153
A5	2n		15	21

การคำนวณแต่ละรูปแบบจึงขึ้นกับขนาดของ n ถ้า เป็นแบบ 2n จะคำนวณได้เพียงค่า n ไม่มากนัก หาก n มีค่ามากจะไม่สามารถคำนวณได้ ถึงแม้ว่าเครื่องคอมพิวเตอร์จะคำนวณไม่ได้

ฟังก์ชันเหล่านี้เมื่อพล็อต เป็นรูปกราฟที่แปรค่ากับ n ผลลัพธ์ที่ได้เป็นดังนี้

ดังนั้นการคิดหารูปแบบการคำนวณที่ดีจึงเป็นวิธีทีดีกว่าการเพิ่มความเร็วการคำนวณด้วยคอมพิวเตอร์ เช่นถ้าปรับปรุงวิธีการแก้ปัญหาจาก n² ให้เหลือ n log n จะทำให้ลดเวลาการคำนวณได้มาก

 

---

ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์