ในบทก่อนหน้า เราเห็นว่า Hansel และ Gretel แก้ปัญหาการเอาตัวรอดด้วยการคำนวณเพื่อกลับบ้าน การคำนวณนี้เปลี่ยนตำแหน่งของพวกเขาอย่างเป็นระบบทีละขั้น — จากจุดในป่าซึ่งหมายถึงอันตราย ไปยังตำแหน่งสุดท้ายที่บ้านซึ่งหมายถึงความปลอดภัย การคำนวณเพื่อกลับบ้านเป็นผลจากการรัน algorithm (อัลกอริทึม) ที่ตามรอยกรวด เมื่อ algorithm เริ่มทำงาน นั่นคือ computation (การคำนวณ) เกิดขึ้น。

แม้ตอนนี้เราจะมีภาพของสิ่งที่ computation (การคำนวณ) คือ อยู่บ้าง แต่เรายังเห็นเพียงด้านเดียวของสิ่งที่ computation จริงๆ ทำ — นั่นคือการเปลี่ยนแปลงของ representation (การแทน) ยังมีรายละเอียดเพิ่มเติมที่ควรสนใจ ดังนั้นเพื่อขยายความเข้าใจให้เลยไปจาก representation แบบ คงที่ ที่อธิบายโดย algorithm (อัลกอริทึม) ผมจะพูดถึงพฤติกรรมแบบ ไดนามิก ของการคำนวณ。

ข้อดีอย่างหนึ่งของ algorithm (อัลกอริทึม) คือมันถูกใช้ซ้ำเพื่อแก้ปัญหาต่างๆ นั่นทำงานอย่างไร? แล้วคำอธิบายของ algorithm ชุดเดียวที่คงที่สามารถสร้างการคำนวณที่ต่างกันได้อย่างไร? นอกจากนี้ เรากล่าวว่าการคำนวณเกิดจากการรัน algorithm แต่ใครหรืออะไรเป็นผู้รัน algorithm นั้น? ต้องมีทักษะอะไรในการรัน algorithm? ใครๆ ก็ทำได้หรือไม่? และสุดท้าย แม้ว่าการมี algorithm ในการแก้ปัญหาจะดี แต่เราต้องถามว่าแลกด้วยอะไร — เฉพาะเมื่อ algorithm สามารถให้คำตอบได้เร็วพอและใช้ทรัพยากรที่มีอยู่ มันจึงเป็นตัวเลือกที่ใช้งานได้จริง。

สร้างความหลากหลาย (Creating Variety)

กลับมาที่ Hansel และ Gretel เราเห็นว่า pebble-tracing algorithm (อัลกอริทึมที่ตามรอยกรวด) ของพวกเขาสามารถใช้ซ้ำได้ในสถานการณ์ต่างๆ มาดูให้ละเอียดขึ้นว่านี่ทำงานอย่างไร เนื่องจากคำอธิบายใน algorithm คงที่ จึงต้องมีส่วนหนึ่งของคำอธิบายที่รับผิดชอบความแปรผันของการคำนวณ ส่วนนี้เรียกว่า parameter (พารามิเตอร์) พารามิเตอร์ใน algorithm แทนค่าที่เป็นรูปธรรม และเมื่อรัน algorithm ค่ารูปธรรมต้องถูกแทนที่ในพารามิเตอร์ ค่าดังกล่าวเรียกว่า input value หรือเรียกสั้นๆ ว่า input สำหรับ algorithm。

ตัวอย่างเช่น อัลกอริทึมสำหรับชงกาแฟอาจมี parameter number เพื่อแทนจำนวนถ้วยที่จะชง ทำให้คำสั่งในอัลกอริทึมสามารถอ้างถึงพารามิเตอร์นี้ได้ นี่คือส่วนย่อจากอัลกอริทึมเช่นนี้:

เติมน้ำ number ถ้วย。

ใส่ผงกาแฟบดจำนวน 1.5 เท่าของ number ช้อนโต๊ะ。

ถ้าต้องการรันอัลกอริทึมนี้สำหรับกาแฟ 3 ถ้วย ให้แทนค่า input เป็น 3 แทน parameter number ในคำสั่งของอัลกอริทึม จะได้เวอร์ชันเฉพาะของอัลกอริทึมดังนี้:

เติมน้ำ 3 ถ้วย。

ใส่ผงกาแฟบดจำนวน 1.5 เท่าของ 3 ช้อนโต๊ะ。

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

อัลกอริทึมของ Hansel และ Gretel ใช้พารามิเตอร์สำหรับกรวดที่วางไว้ในป่า ก่อนหน้านี้ผมไม่ได้ระบุพารามิเตอร์ให้ชัดเจน เพราะคำสั่ง “Find a pebble not visited before” ชัดเจนว่าหมายถึงกรวดที่ Hansel วางไว้ พารามิเตอร์สามารถทำให้ชัดขึ้นได้ด้วยคำสั่งเช่น “Find a pebble from the pebbles-placed-by-Hansel not visited before.” ในการรันอัลกอริทึมแต่ละครั้ง พารามิเตอร์ pebbles-placed-by-Hansel จะถูกแทนที่ด้วยกรวดที่ Hansel ทิ้งไว้ — อย่างน้อยเราสามารถคิดแบบนั้นได้ เนื่องจากเราไม่สามารถวางกรวดจริงๆ ลงในคำอธิบายอัลกอริทึมได้ เราจึงถือพารามิเตอร์เป็นการอ้างอิงหรือ pointer (ตัวชี้) ไปยังค่า input; pointer คือกลไกที่ใช้เข้าถึงค่า input มันบอกเราว่าควรมองหาค่า input ที่ไหนเมื่ออัลกอริทึมต้องการ ในอัลกอริทึมค้นทาง ค่า input จะพบบนพื้นป่า ในอัลกอริทึมทำกาแฟ ค่า input อยู่ในความคิดของเรา และเมื่อพารามิเตอร์อ้างถึงมัน เราก็ดึงมันมาใช้ อย่างไรก็ตาม แนวคิดของการแทนค่านั้นเป็นอนาล็อกที่ช่วยให้ความสัมพันธ์ระหว่างอัลกอริทึมกับการคำนวณชัดเจนขึ้น。

โดยการเพิ่มพารามิเตอร์และใช้มันแทนค่าคงที่ เราสามารถทำให้อัลกอริทึมทั่วไปขึ้นเพื่อทำงานได้ในหลายสถานการณ์ ตัวอย่างเช่น ถ้าอัลกอริทึมการตื่นนอนมีคำสั่ง “Wake up at 6:30 a.m.” เราสามารถแทนค่าตัวเลขเวลาด้วยพารามิเตอร์ wake-up-time ซึ่งนำไปสู่คำสั่งทั่วไปว่า “Wake up at wake-up-time_” ในทำนองเดียวกัน ประสบการณ์การกินซีเรียลก็สามารถขยายได้โดยทำให้พารามิเตอร์ _fruit เป็นส่วนหนึ่งของอัลกอริทึมการเตรียม。

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

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

พารามิเตอร์เป็นส่วนสำคัญของอัลกอริทึม แต่คำถามว่าอัลกอริทึมควรทั่วไปหรือเฉพาะเจาะจงเพียงใดไม่มีคำตอบง่ายๆ หัวข้อนี้มีการพูดถึงใน chapter 15。

ใครเป็นผู้ปฏิบัติ? (Who Is Performing?)

อย่างที่เราเห็น การคำนวณเป็นผลจากการรันอัลกอริทึม นั่นจึงตั้งคำถามว่าใครหรืออะไรสามารถรันอัลกอริทึมได้ และอย่างไร ตัวอย่างที่ผ่านมาแสดงว่ามนุษย์สามารถรันอัลกอริทึมได้แน่นอน และ (electronic) computers ก็เช่นกัน มีความเป็นไปได้อื่นๆ หรือไม่? แล้วข้อกำหนดในการรันอัลกอริทึมคืออะไร?

Figure 2.1 การรันอัลกอริทึมสร้างการคำนวณ อัลกอริทึมบรรยายวิธีการที่ใช้ได้กับกลุ่มปัญหา และการรันทำงานบน representation ของปัญหาเฉพาะ การรันต้องดำเนินการโดย computer เช่น คนหรือเครื่องจักร ที่เข้าใจภาษาที่ใช้เขียนอัลกอริทึม。

คำว่า computer หมายถึงผู้ที่หรือสิ่งที่สามารถทำการคำนวณได้ ตามจริงความหมายดั้งเดิมของคำนี้หมายถึงคนที่ทำการคำนวณ[2] ต่อไปนี้ผู้เขียนจะใช้คำนี้ในความหมายทั่วไปที่หมายถึงเอเยนต์ทั้งธรรมชาติหรือเทียมซึ่งสามารถทำการคำนวณได้。

เราสามารถแยกกรณีหลักสองแบบของการรันอัลกอริทึมตามความสามารถของ computer ที่ปฏิบัติ ในด้านหนึ่งมี universal computers เช่น คน แล็ปท็อป หรือสมาร์ทโฟน Universal computer สามารถในหลักการรันอัลกอริทึมใดๆ ก็ได้ตราบเท่าที่อัลกอริทึมถูกเขียนในภาษาที่ computer เข้าใจ Universal computers จัดตั้งความสัมพันธ์การรันระหว่างอัลกอริทึมและการคำนวณ เมื่อใดที่ computer รันอัลกอริทึมสำหรับปัญหาเฉพาะ มันจะทำขั้นตอนที่เปลี่ยน representation บางอย่าง (ดู figure 2.1)。

ในทางกลับกัน มีคอมพิวเตอร์ที่รันเพียงอัลกอริทึมเดียว (หรือชุดอัลกอริทึมที่กำหนดไว้) เช่น เครื่องคิดเลขพกพาที่มีวงจรอิเล็กทรอนิกส์ฝังไว้สำหรับการคำนวณเลข หรือนาฬิกาปลุกที่ทำเสียงในเวลาที่กำหนด ตัวอย่างที่น่าสนใจอีกอย่างพบได้ในชีววิทยาเซลล์。

ลองคิดถึงสิ่งที่เกิดขึ้นในเซลล์ของคุณเป็นล้านๆ ครั้งขณะที่คุณกำลังอ่านประโยคนี้ ไรโบโซมกำลังผลิตโปรตีนเพื่อสนับสนุนหน้าที่ของเซลล์ ไรโบโซมเป็นเครื่องจักรตัวเล็กๆ ที่ประกอบโปรตีนตามคำสั่งในโมเลกุล RNA ซึ่งเป็นลำดับของกรดอะมิโนที่บอกให้ไรโบโซมผลิตโปรตีนเฉพาะ คุณยังมีชีวิตเพราะการคำนวณที่เกิดจาก ribosomal computers ในเซลล์ของคุณที่รันอัลกอริทึมแปล RNA เป็นโปรตีนอย่างเชื่อถือได้ แม้ว่าอัลกอริทึมของไรโบโซมจะผลิตโปรตีนหลากหลายได้ แต่ก็เป็นอัลกอริทึมเดียวที่ไรโบโซมสามารถรันได้ แม้จะมีประโยชน์มาก แต่ไรโบโซมก็มีข้อจำกัด — มันไม่สามารถสวมเสื้อผ้าหรือหาทางออกจากป่าให้คุณได้。

ต่างจากคอมพิวเตอร์ที่มีอัลกอริทึมฝังอยู่ ข้อกำหนดสำคัญสำหรับ universal computers คือพวกมันต้องเข้าใจภาษาที่ใช้เขียนอัลกอริทึม หากคอมพิวเตอร์เป็นเครื่องจักร อัลกอริทึมดังกล่าวมักเรียกว่า program และภาษาที่ใช้เรียกว่า programming language.

หาก Hansel และ Gretel เขียนบันทึกความทรงจำและใส่คำอธิบายของอัลกอริทึมที่ช่วยชีวิตไว้ เด็กคนอื่นที่เข้าถึงหนังสือเล่มนั้นจะสามารถรันอัลกอริทึมได้ก็ต่อเมื่อพวกเขาเข้าใจภาษาที่หนังสือเขียนขึ้น ข้อกำหนดนี้ไม่ใช้กับคอมพิวเตอร์ที่ไม่เป็นสากลซึ่งทำแค่อัลกอริทึมที่ฝังไว้เท่านั้น。

ข้อกำหนดที่ใช้กับคอมพิวเตอร์ทุกรูปแบบคือความสามารถในการเข้าถึง representation ที่อัลกอริทึมใช้งาน โดยเฉพาะอย่างยิ่ง คอมพิวเตอร์ต้องสามารถทำการเปลี่ยนแปลงที่จำเป็นต่อ representation ได้ หาก Hansel และ Gretel ถูกผูกติดกับต้นไม้ อัลกอริทึมก็ไม่เป็นประโยชน์ เพราะพวกเขาจะไม่สามารถเปลี่ยนตำแหน่งได้ ซึ่งเป็นสิ่งที่การรันอัลกอริทึมการค้นทางต้องการ。

สรุปแล้ว คอมพิวเตอร์ใดๆ ต้องสามารถอ่านและจัดการ representation ที่อัลกอริทึมทำงานอยู่ได้ นอกจากนี้ universal computer ต้องเข้าใจภาษาที่ใช้อธิบายอัลกอริทึม จากนี้ไป ผู้เขียนจะใช้คำว่า computer หมายถึง universal computer。

ต้นทุนของการมีชีวิตอยู่ (The Cost of Living)

คอมพิวเตอร์มีงานที่ต้องทำจริงๆ ซึ่งเป็นสิ่งที่คุณรู้สึกได้เมื่อแล็ปท็อปร้อนเพราะต้องเรนเดอร์กราฟิกสูงๆ ในเกม หรือเมื่อแบตสมาร์ทโฟลล์หมดเร็วเพราะแอปหลายตัวรันพื้นหลัง และเหตุผลที่คุณต้องตั้งนาฬิกาปลุกให้ตื่นก่อนเวลานัด คือการรันอัลกอริทึมการตื่นนอนนั้นต้องใช้เวลา。

การคิดอัลกอริทึมเพื่อแก้ปัญหาหนึ่งเป็นเรื่องหนึ่ง แต่การรับประกันว่า computation ที่เกิดจากอัลกอริทึมจะให้คำตอบได้เร็วพอเป็นเรื่องคนละเรื่อง อีกประเด็นที่เกี่ยวข้องคือคอมพิวเตอร์ที่ทำงานนั้นมีทรัพยากรเพียงพอหรือไม่ที่จะรันการคำนวณนั้นตั้งแต่แรก。

ตัวอย่างเช่น เมื่อ Hansel และ Gretel ตามรอยกรวดกลับบ้าน การคำนวณทั้งหมดใช้จำนวนก้าวเท่ากับจำนวนกรวดที่ Hansel ทิ้งไว้[3] โปรดสังเกตว่า 'step' ที่นี่หมายถึง “ขั้นตอนของอัลกอริทึม” ไม่ใช่ “ก้าวเดิน” โดยเฉพาะ อย่างใดก็ตาม หนึ่งขั้นของอัลกอริทึมโดยทั่วไปเทียบเท่ากับหลายก้าวเดินของ Hansel และ Gretel ดังนั้นจำนวนกรวดจึงเป็นมาตรวัดเวลาการรันอัลกอริทึม เพราะต้องใช้หนึ่งขั้นตอนของอัลกอริทึมต่อกรวดหนึ่งก้อน การคิดถึงจำนวนขั้นตอนที่อัลกอริทึมต้องใช้ในการทำงานคือการประเมิน _runtime complexity_。

ยิ่งไปกว่านั้น อัลกอริทึมจะใช้งานได้ก็ต่อเมื่อ Hansel และ Gretel มีกรวดเพียงพอในการปักตามเส้นทางจากบ้านไปยังจุดที่พ่อแม่ทิ้งไว้ ซึ่งเป็นตัวอย่างของข้อจำกัดด้านทรัพยากร การขาดแคลนกรวดอาจมาจากการมีกรวดไม่เพียงพอซึ่งเป็นข้อจำกัดของทรัพยากรภายนอก หรือมาจากพื้นที่จำกัดในกระเป๋าของ Hansel ซึ่งเป็นขีดจำกัดของคอมพิวเตอร์ การพิจารณา space complexity ของอัลกอริทึมคือการถามว่าคอมพิวเตอร์ต้องการพื้นที่เท่าใดในการรันอัลกอริทึม ในตัวอย่างนี้คือการถามว่าต้องใช้กรวดกี่ก้อนเพื่อหาทางเดินความยาวหนึ่ง และกระเป๋าของ Hansel จะพอเก็บกรวดทั้งหมดหรือไม่。

ดังนั้น แม้อัลกอริทึมอาจใช้งานได้ในทางทฤษฎีสำหรับตำแหน่งใดๆ ในป่า แต่ไม่อาจรู้ล่วงหน้าว่าการคำนวณจะสำเร็จในทางปฏิบัติหรือไม่ เพราะอาจใช้เวลามากเกินไปหรือต้องใช้ทรัพยากรเกินที่มี ก่อนจะลงรายละเอียดเรื่องทรัพยากรการคำนวณ ผมจะอธิบายสมมติฐานสำคัญสองประการเกี่ยวกับการวัดต้นทุนการคำนวณที่ทำให้การวิเคราะห์ประเภทนี้เป็นไปได้ ในบทต่อไป ผมเน้นที่ด้าน runtime แต่การอภิปรายยังใช้กับเรื่อง space resources ได้ด้วย。

ภาพรวมของต้นทุน (The Big Picture of Costs)

อัลกอริทึมสามารถมองได้ว่าเป็นการทำให้ทั่วไปของการคำนวณหลายๆ แบบ ตามที่อธิบายก่อนหน้านี้ ความแตกต่างของการคำนวณต่างๆ ถูกจับไว้ในคำอธิบายอัลกอริทึมด้วยพารามิเตอร์ และการคำนวณแต่ละแบบที่เฉพาะเจาะจงเกิดจากการรันอัลกอริทึมโดยแทนค่าพารามิเตอร์ด้วยค่า input ที่กำหนด เช่นเดียวกัน เราอยากได้คำอธิบายทั่วไปของความต้องการทรัพยากรของอัลกอริทึม — คำอธิบายที่ไม่ใช่แค่กับการคำนวณเฉพาะ แต่จับภาพการคำนวณทั้งหมด กล่าวคือ เราต้องการการทำให้ทั่วไปของคำอธิบายต้นทุน ซึ่งทำได้โดยใช้พารามิเตอร์ที่ทำให้จำนวนขั้นตอนที่ต้องใช้ขึ้นกับขนาดของ input ดังนั้น runtime complexity คือฟังก์ชันที่ให้จำนวนขั้นตอนในการคำนวณสำหรับ input ที่มีขนาดหนึ่ง。

ตัวอย่างเช่น จำนวนขั้นตอนของการคำนวณ และดังนั้นเวลาที่ต้องใช้ในการรันอัลกอริทึมตามรอยกรวดนั้นประมาณเท่ากับจำนวนกรวดที่ทิ้งไว้ เนื่องจากเส้นทางไปยังจุดต่างๆ ในป่ามักมีจำนวนกรวดต่างกัน การคำนวณสำหรับเส้นทางเหล่านี้จึงต้องการจำนวนขั้นตอนต่างกัน ข้อนี้สะท้อนในรูปการแสดง runtime complexity เป็นฟังก์ชันของขนาดของ input สำหรับอัลกอริทึมตามรอยกรวด การวัดจำนวนขั้นตอนสำหรับแต่ละการคำนวณค่อนข้างตรงไปตรงมา เพราะจำนวนขั้นตอนดูเหมือนจะมีความสัมพันธ์แบบหนึ่งต่อหนึ่งกับจำนวนกรวด เช่น สำหรับเส้นทางที่มี 87 กรวด การคำนวณต้องการ 87 ขั้นตอน。

อย่างไรก็ตาม นี่ไม่ได้เป็นจริงเสมอไป ลองดูเส้นทางที่ปรากฏใน figure 1.3 ตัวอย่างนั้นเคยใช้เพื่อแสดงว่าอัลกอริทึมอาจติดอยู่ แต่เรายังสามารถใช้มันเพื่อแสดงว่าอัลกอริทึมอาจผลิตการคำนวณที่ต้องการขั้นตอนน้อยกว่าจำนวนกรวด เพราะ B และ C มองเห็นได้จาก D เราจึงเลือก B ได้ และเพราะทั้ง A และ C มองเห็นได้จาก B เราจึงสามารถเลือก A ต่อไปได้ คือเส้นทาง D, B, A ถูกต้อง และเนื่องจากเส้นทางนี้ข้าม C การคำนวณจึงมีขั้นตอนน้อยกว่าจำนวนกรวดในเส้นทางอย่างน้อยหนึ่งขั้น。

โปรดสังเกตว่าในกรณีนี้จำนวนขั้นตอนของการคำนวณจริงๆ ต่ำกว่าที่วัดโดยอัลกอริทึม ซึ่งหมายความว่าต้นทุนของการคำนวณถูกประเมินสูงเกินไป ดังนั้น runtime complexity จะรายงานความซับซ้อนที่การคำนวณอาจมีใน กรณีที่แย่ที่สุด ซึ่งช่วยให้เราตัดสินใจว่าจะรันอัลกอริทึมหรือไม่สำหรับ input ใด ๆ หากค่าประมาณ runtime ยอมรับได้ ก็สามารถรันอัลกอริทึมได้ หากการคำนวณทำงานได้เร็วกว่าและต้องขั้นตอนน้อยกว่า ก็เป็นเรื่องดี แต่ความซับซ้อนในกรณีที่แย่ที่สุดให้การรับประกันว่าอัลกอริทึมจะไม่ใช้เวลามากกว่านี้ ในกรณีการตื่น เวลาประเมินแบบกรณีที่แย่ที่สุดสำหรับการอาบน้ำของคุณอาจเป็น 5 นาที ซึ่งรวมเวลาน้ำอุ่นไว้ด้วย เวลาจริงของคุณอาจสั้นกว่าได้หากมีคนอาบน้ำก่อนหน้าคุณ。

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

สมมติฐานอีกข้อสำหรับ runtime complexity คือหนึ่งขั้นของอัลกอริทึมโดยทั่วไปสอดคล้องกับหลายก้าวที่ผู้ปฏิบัติอัลกอริทึมต้องทำ นี่ชัดเจนในตัวอย่าง กรวดคงไม่ได้วางห่างกันหนึ่งก้าวเท่านั้น ดังนั้น Hansel และ Gretel จะต้องเดินหลายก้าวเพื่อไปจากกรวดหนึ่งไปยังกรวดถัดไป อย่างไรก็ตาม แต่ละขั้นของอัลกอริทึมต้องไม่ก่อให้เกิดจำนวนก้าวของคอมพิวเตอร์ที่มากเกินไป ตัวเลขนี้ต้องคงที่และค่อนข้างเล็กเมื่อเทียบกับจำนวนขั้นตอนของอัลกอริทึม มิฉะนั้นข้อมูลเกี่ยวกับ runtime ของอัลกอริทึมจะไร้ความหมาย: จำนวนขั้นตอนของอัลกอริทึมจะไม่ใช่มาตรวัดที่แม่นยำสำหรับ runtime ที่แท้จริง ปัจจัยที่เกี่ยวข้องอีกอย่างคือคอมพิวเตอร์แต่ละเครื่องมีลักษณะการทำงานต่างกัน ในตัวอย่าง Hansel อาจมีก้าวยาวกว่า Gretel และจึงต้องใช้ก้าวเดินน้อยกว่า แต่ Gretel อาจเดินเร็วกว่า Hansel ทำให้ใช้เวลาเดินเท่าเดิมน้อยกว่า ปัจจัยเหล่านี้ทั้งหมดสามารถละเลยได้โดยมุ่งที่ runtime ของอัลกอริทึม。

การเติบโตของต้นทุน (Cost Growth)

เนื่องจากข้อมูลเกี่ยวกับ runtime complexity ของอัลกอริทึมถูกให้เป็นฟังก์ชัน มันจึงสามารถจับความแตกต่างของ runtime สำหรับการคำนวณที่ต่างกันได้ วิธีนี้สะท้อนว่าปกติแล้วอัลกอริทึมต้องการเวลามากขึ้นสำหรับ input ที่ใหญ่ขึ้น。

ความซับซ้อนของอัลกอริทึมของ Hansel และ Gretel สามารถอธิบายได้ด้วยกฎว่า “Runtime แปรผันตามจำนวนกรวด” ซึ่งหมายความว่าอัตราส่วนของจำนวนก้าวเดินต่อกรวดเป็นค่าคงที่ กล่าวคือ หากเส้นทางยาวขึ้นเป็นสองเท่าและมีกรวดสองเท่า เวลาการรันก็จะเพิ่มเป็นสองเท่าเช่นกัน โปรดสังเกตว่านี่ไม่ได้หมายความว่าจำนวนก้าวเดินจะ เท่ากัน กับจำนวนกรวด เพียงแต่ว่ามันเพิ่มหรือหดตัวในแบบเดียวกับ input。

ความสัมพันธ์นี้เรียกว่า linear และปรากฏเป็นเส้นตรงในกราฟที่พล็อตจำนวนก้าวเดินที่ต้องใช้สำหรับจำนวนกรวดใดๆ ในกรณีแบบนี้เรากล่าวว่าอัลกอริทึมมี runtime complexity แบบ linear บางครั้งเราก็กล่าวสั้นๆ ว่าอัลกอริทึม is linear.

อัลกอริทึมแบบ linear ดีมาก และในหลายกรณีเป็นสิ่งที่ดีที่สุดที่คาดหวังได้ เพื่อดูตัวอย่างของความซับซ้อนเวลาแบบอื่น ให้พิจารณาอัลกอริทึมที่ Hansel ใช้เมื่อทิ้งกรวด ในเวอร์ชันดั้งเดิมของเรื่องเขามีกรวดทั้งหมดในกระเป๋าและสามารถทิ้งได้ขณะที่เดินเข้าไปในป่า นี่ชัดเจนว่าเป็นอัลกอริทึมแบบ linear (เทียบกับจำนวนกรวด) เพราะ Hansel ต้องเดินจำนวนก้าวคงที่เพื่อไปยังตำแหน่งสำหรับทิ้งกรวดถัดไป。

แต่ตอนนี้สมมติว่า Hansel ไม่มีวิธีเก็บหรือซ่อนกรวด ในกรณีนั้นเขาต้องกลับบ้านแล้วเอากรวดใหม่สำหรับแต่ละกรวดที่เขาต้องการทิ้ง ซึ่งต้องใช้เวลาประมาณสองเท่าของจำนวนก้าวที่ต้องไปถึงกรวดนั้น จำนวนก้าวรวมจึงเป็นผลรวมของก้าวที่ต้องการสำหรับกรวดแต่ละก้อน เพราะระยะทางจากบ้านเพิ่มขึ้นตามจำนวนกรวดที่ทิ้ง จำนวนก้าวรวมจึงเป็นสัดส่วนกับผลรวม 1 + 2 + 3 + 4 + 5 + ⋯ ซึ่งเป็นสัดส่วนกับกำลังสองของจำนวนกรวดที่วาง。

ความสัมพันธ์นี้สามารถอธิบายได้โดยพิจารณาระยะทางที่ Hansel ต้องเดิน วัดเป็นจำนวนกรวด สำหรับการทิ้งสองกรวด Hansel ต้องไปยังจุดที่จะทิ้งกรวดแรก กลับบ้านเพื่อเอากรวดอีกก้อน แล้วไปทางผ่านกรวดก้อนแรกไปยังตำแหน่งที่จะทิ้งกรวดที่สอง ทำให้เขาเดินรวมเป็นระยะทางสี่กรวด สำหรับการทิ้งสามกรวด Hansel ต้องเดินระยะทางที่ต้องใช้สำหรับทิ้งสองกรวด ซึ่งเราทราบแล้วว่าเป็นสี่ จากนั้นเขาต้องกลับบ้านเพื่อนำกรวดที่สาม ซึ่งหมายถึงเดินระยะทางสองกรวด แล้วเพื่อวางกรวดที่สามเขาต้องเดินอีกสามกรวด รวมเป็น 4 + 2 + 3 = 9 กรวด。

พิจารณากรณีที่สี่ สำหรับกรวดก้อนที่สี่ Hansel ได้เดินระยะทางเพื่อทิ้งสามกรวดแล้ว กลับบ้าน (สามกรวด) แล้วต้องเดินอีกสี่กรวดเพื่อไปยังตำแหน่งทิ้งกรวดที่สี่ รวมเป็นระยะทางทั้งหมด 9 + 3 + 4 = 16 กรวด ในทำนองเดียวกัน เราสามารถคำนวณระยะทางสำหรับการทิ้งกรวดห้ากรวด (16 + 4 + 5 = 25), หกกรวด (25 + 5 + 6 = 36) และต่อไปเรื่อยๆ。

เราจะเห็นรูปแบบหนึ่งชัดเจนขึ้น คือจำนวนขั้นตอนที่ Hansel ต้องใช้เป็นสัดส่วนกับกำลังสองของจำนวนกรวดที่วาง อัลกอริทึมที่มีรูปแบบความซับซ้อนเช่นนี้เรียกว่า quadratic runtime หรือกล่าวสั้นๆ ว่า be quadratic runtime ของอัลกอริทึมแบบ quadratic เติบโตเร็วกว่าอัลกอริทึมแบบ linear มาก ตัวอย่างเช่น สำหรับกรวดสิบก้อน อัลกอริทึมแบบ linear ใช้ 10 ขั้น แต่ quadratic ต้องใช้ 100 ขั้น สำหรับ 100 กรวด อัลกอริทึม linear ต้องการ 100 ขั้น ในขณะที่ quadratic ต้องการ 10,000 ขั้น。

โปรดสังเกตว่าจำนวนขั้นตอนจริงอาจสูงกว่าได้ ดังที่กล่าวไว้แล้ว อัลกอริทึมแบบ linear อาจใช้จำนวนขั้นตอนคงที่ต่อกรวด เช่น 2 หรือ 3 หรือแม้แต่ 14 ดังนั้นสำหรับเส้นทางที่มี 10 กรวด อาจต้องใช้ 20 หรือ 30 หรือ 140 ขั้นได้ เช่นเดียวกับอัลกอริทึม quadratic ซึ่งจำนวนขั้นตอนอาจคูณด้วยปัจจัยอีกค่า นี่ชี้ให้เห็นว่าอัลกอริทึมแบบ linear ไม่จำเป็นต้องเร็วกว่าควอดราติกในทุกกรณี หากมีปัจจัยคงที่ขนาดใหญ่ อาจต้องใช้ขั้นตอนมากกว่าอัลกอริทึม quadratic ที่มีปัจจัยเล็ก โดยเฉพาะสำหรับ input ขนาดเล็ก อย่างไรก็ตามเมื่อ input ขนาดโตขึ้น ผลกระทบของปัจจัยคงที่จะลดลงและการเติบโตของอัลกอริทึม quadratic จะเด่นขึ้น เช่น สำหรับ 100 กรวด อัลกอริทึม linear นี้ใช้ 1,400 ขั้น ขณะที่ quadratic ใช้ 10,000 ขั้น。

ในเรื่องราวนั้น อัลกอริทึม quadratic เป็นไปไม่ได้และจะไม่สำเร็จ ลองคิดถึงเวลาที่จะใช้ในการวางกรวดก้อนสุดท้าย Hansel ต้องเดินกลับบ้านแล้วกลับเข้าป่าอีกครั้ง กล่าวคือโดยพื้นฐานแล้วเขาต้องเดินเข้าไปในป่าสามครั้ง พ่อแม่ก็คงไม่อดทนพอเมื่อเขากำลังวางกรวดด้วยวิธี linear อยู่แล้ว。

พ่อของเขาพูดว่า: “ฮันเซล แกมองอะไรอยู่และช้าทำไม? ตั้งใจสิ และอย่าลืมใช้ขาของตัวเอง.”

พวกเขาคงไม่รอให้ Hansel กลับบ้านทุกครั้งที่ต้องการกรวดใหม่ ดังนั้น runtime ของอัลกอริทึมจึงมีความสำคัญจริง ๆ หากอัลกอริทึมช้ามาก มันอาจกลายเป็นไร้ประโยชน์ในทางปฏิบัติ (ดู chapter 7)。

ตัวอย่างนี้ยังแสดงให้เห็นว่าประสิทธิภาพด้านเวลาและพื้นที่มักเกี่ยวข้องกัน ในกรณีนี้เราสามารถปรับปรุงประสิทธิภาพ runtime จาก quadratic เป็น linear โดยแลกกับความจุในการจัดเก็บ นั่นคือ ใช้พื้นที่จัดเก็บแบบเชิงเส้น สมมติว่ากระเป๋าของ Hansel สามารถเก็บกรวดทั้งหมดได้。

เมื่อสองอัลกอริทึมแก้ปัญหาเดียวกัน แต่หนึ่งมี runtime complexity ต่ำกว่าอีก อัลกอริทึมที่เร็วกว่าถูกเรียกว่า more efficient (ในแง่ runtime) เช่นเดียวกัน หากอัลกอริทึมหนึ่งใช้หน่วยความจำน้อยกว่าอีก ตัวนั้นถูกเรียกว่า more space efficient ในตัวอย่าง อัลกอริทึมแบบวางกรวดเชิงเส้นมีประสิทธิภาพด้าน runtime มากกว่าอัลกอริทึมแบบกำลังสอง แต่มีประสิทธิภาพด้านพื้นที่น้อยกว่าเพราะมันทำให้กระเป๋าของ Hansel เต็มไปด้วยกรวด。