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

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

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

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

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

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

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

เติมผงกาแฟ 1.5 เท่าของ number ช้อนโต๊ะ

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

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

เติมผงกาแฟ 1.5 เท่าของ 3 ช้อนโต๊ะ

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

อัลกอริทึมของ Hansel กับ Gretel ใช้ parameter สำหรับก้อนกรวดที่วางไว้ในป่า ผมไม่ได้ระบุ parameter ให้ชัดเจนก่อนหน้านี้เพราะคำสั่ง "หาก้อนกรวดที่ยังไม่เคยเดินผ่าน" อ้างถึงก้อนกรวดที่ Hansel วางไว้อย่างชัดเจนอยู่แล้ว parameter สามารถทำให้ชัดเจนขึ้นได้โดยใช้คำสั่งต่อไปนี้แทน: "หาก้อนกรวดจาก pebbles-placed-by-Hansel ที่ยังไม่เคยเดินผ่าน" สำหรับการดำเนินการแต่ละครั้งของอัลกอริทึม parameter pebbles-placed-by-Hansel จะถูกแทนที่ด้วยก้อนกรวดที่ Hansel ได้วางไว้ — อย่างน้อยเราก็คิดแบบนั้นได้ เนื่องจากเราไม่สามารถวางก้อนกรวดจริงลงในคำอธิบายอัลกอริทึมได้ เราจึงถือว่า parameter เป็นการอ้างอิงหรือ pointer ไปยังค่า input pointer คือกลไกในการเข้าถึงค่า input มันบอกเราว่าต้องไปหาค่า input ที่ไหนเมื่ออัลกอริทึมต้องการ ในอัลกอริทึมหาทาง ค่า input จะอยู่บนพื้นป่า ในอัลกอริทึมชงกาแฟ เรามีค่า input อยู่ในใจ และเมื่อใดก็ตามที่ parameter อ้างถึงมัน เราก็จะดึงมันออกมา อย่างไรก็ตาม แนวคิดเรื่องการแทนที่ก็เป็นอุปมาที่มีประโยชน์ที่ช่วยทำให้ความสัมพันธ์ระหว่างอัลกอริทึมและการคำนวณเป็นรูปธรรม

ด้วยการแนะนำ parameter และใช้มันเพื่อแทนที่ค่าที่เป็นรูปธรรม เราสามารถทำให้อัลกอริทึมเป็นแบบทั่วไปเพื่อทำงานในหลายสถานการณ์ได้ ตัวอย่างเช่น หากอัลกอริทึมการตื่นนอนเฉพาะอันหนึ่งมีคำสั่งว่า "ตื่นนอนตอน 6:30 น." เราสามารถแทนที่ค่าเวลาเฉพาะนั้นด้วย parameter wake-up-time ซึ่งนำไปสู่คำสั่งทั่วไป "ตื่นนอนตอน wake-up-time" ในทำนองเดียวกัน ประสบการณ์การกินซีเรียลสามารถขยายได้โดยการทำให้ parameter fruit เป็นส่วนหนึ่งของอัลกอริทึมการเตรียมอาหาร

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

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

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

Who Is Performing? (ใครเป็นผู้ดำเนินการ?)

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

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

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

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

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

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

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

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

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

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

The Cost of Living (ต้นทุนของการดำรงอยู่)

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

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

ตัวอย่างเช่น เมื่อ Hansel กับ Gretel เดินตามรอยก้อนกรวดกลับบ้าน การคำนวณทั้งหมดใช้จำนวนขั้นตอนเท่ากับจำนวนก้อนกรวดที่ Hansel วางไว้ 3 สังเกตว่าขั้นตอนในที่นี้หมายถึง "ขั้นตอนของอัลกอริทึม" ไม่ใช่ "ก้าวย่างในการเดิน" โดยเฉพาะอย่างยิ่ง หนึ่งขั้นตอนของอัลกอริทึมโดยทั่วไปสอดคล้องกับหลายก้าวที่ Hansel กับ Gretel เดินผ่านป่า ดังนั้นจำนวนก้อนกรวดจึงเป็นตัววัดเวลาในการดำเนินการของอัลกอริทึม เนื่องจากต้องใช้หนึ่งขั้นตอนของอัลกอริทึมต่อก้อนกรวดหนึ่งก้อน การคิดถึงจำนวนขั้นตอนที่อัลกอริทึมต้องใช้ในการทำงานคือการตัดสิน runtime complexity (ความซับซ้อนด้านเวลาทำงาน) ของมัน

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

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

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

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

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

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

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

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

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

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

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

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

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

อัลกอริทึมเชิงเส้นนั้นดีมาก และในหลายกรณีก็ดีที่สุดเท่าที่จะหวังได้ เพื่อดูตัวอย่างของ runtime complexity ที่แตกต่างกัน ลองพิจารณาอัลกอริทึมที่ Hansel ดำเนินการเมื่อวางก้อนกรวด ในเวอร์ชันดั้งเดิมของเรื่อง เขามีก้อนกรวดทั้งหมดอยู่ในกระเป๋าและสามารถวางพวกมันได้ขณะเดินเข้าไปในป่า นี่เป็นอัลกอริทึมเชิงเส้นอย่างชัดเจน (เทียบกับจำนวนก้อนกรวด) เพราะ 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 (กำลังสอง) หรือเรียกสั้นๆ ว่า เป็น quadratic เวลาทำงานของอัลกอริทึมแบบ quadratic เติบโตเร็วกว่าแบบ linear มาก ตัวอย่างเช่น สำหรับก้อนกรวดสิบก้อน อัลกอริทึมแบบ linear ใช้สิบขั้นตอน ในขณะที่อัลกอริทึมแบบ quadratic ต้องการ 100 ขั้นตอน สำหรับ 100 ก้อนกรวด อัลกอริทึมแบบ linear ต้องการ 100 ขั้นตอน ในขณะที่อัลกอริทึมแบบ quadratic ต้องการ 10,000 ขั้นตอนแล้ว

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

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

พ่อของเขาพูดว่า: "Hansel เจ้ามองอะไรอยู่ตรงนั้นแล้วยังตามหลังอยู่อีก ตั้งใจฟัง และอย่าลืมวิธีการใช้ขาของเจ้า"

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

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

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