คำอธิบายเกี่ยวกับความซับซ้อนเชิงเวลาและความซับซ้อนเชิงพื้นที่ของอัลกอริทึม
ลองนึกภาพโปรแกรมสองโปรแกรมที่ทำงานเหมือนกันทุกประการ ป้อนข้อมูลพันรายการให้แต่ละโปรแกรม คุณจะไม่สามารถแยกแยะความแตกต่างได้ แต่ถ้าป้อนข้อมูลพันล้านรายการ โปรแกรมหนึ่งจะทำงานเสร็จก่อนที่คุณจะปล่อยปุ่ม Enter ในขณะที่อีกโปรแกรมหนึ่งยังคงทำงานต่อไปจนถึงวันอังคารหน้า
แล็ปท็อปเครื่องเดียวกัน ข้อมูลเหมือนกัน สิ่งที่แตกต่างกันคือความซับซ้อนเชิงเวลา ซึ่งเป็นเพียงชื่อที่ใช้เรียกความเร็วที่ภาระงานของอัลกอริทึมเพิ่มขึ้นเมื่อคุณป้อนข้อมูลเข้าไปมากขึ้น
เราจะมาดูกันว่าคำนี้หมายความว่าอย่างไร รูปแบบการเขียน Big O notation เป็นอย่างไร วิธีคำนวณจากโค้ดจริง และความซับซ้อนของพื้นที่จัดเก็บข้อมูลเข้ามาเกี่ยวข้องอย่างไร และสุดท้าย เราจะมาดูจุดที่ทุกอย่างจะไม่ใช่แค่การบ้านอีกต่อไป แต่จะเริ่มมีค่าใช้จ่ายจริง ๆ นั่นก็คือ สัญญาอัจฉริยะ
ความซับซ้อนเชิงเวลาของอัลกอริทึมคืออะไร?
ลองลืมเรื่องวินาทีไปก่อนสักครู่ ความซับซ้อนของเวลาจะนับจำนวนขั้นตอน การเปรียบเทียบ การกำหนดค่า การคำนวณเลขคณิตเล็กน้อย และคุณสามารถเขียนผลรวมออกมาเป็นฟังก์ชันของ n ซึ่งก็คือขนาดของข้อมูลนำเข้า
นี่คือฟังก์ชันที่น่าเบื่อที่สุดเท่าที่จะนึกออก:
python def print_all(items): for item in items: print(item)
สิบชิ้น? วนรอบสิบครั้ง หมื่นชิ้น? วนรอบหมื่นครั้ง
การทำงานจะเพิ่มขึ้นเป็นเส้นตรงตามอินพุต ดังนั้นเราจึงเรียกว่า O(n)
ทีนี้ บางทีการเดินทางแต่ละครั้งอาจต้องใช้การดำเนินการเล็กๆ สามครั้งแทนที่จะเป็นครั้งเดียวก็ได้ เอาล่ะ นั่นก็คือ 3n เอาจริงๆ แล้วไม่มีใครสนใจหรอก เพราะการเพิ่มรายการเป็นสองเท่าก็ทำให้งานเพิ่มขึ้นเป็นสองเท่าอยู่ดี และเส้นกราฟการเติบโตนั่นแหละคือส่วนที่เราต้องการ ตัวเลขที่แน่นอนถูกละทิ้งไปโดยเจตนา
นั่นเป็นเหตุผลว่าทำไมหลักสูตร DSA ทุกหลักสูตรและครึ่งหนึ่งของการสัมภาษณ์งานด้านการเขียนโค้ดจึงเน้นย้ำเรื่องความซับซ้อนเชิงเวลา หากคุณสามารถอ่านความซับซ้อนของอัลกอริทึมได้เพียงแค่ดูมัน คุณก็สามารถเดาได้ว่ามันจะทำงานอย่างไรกับข้อมูลอินพุตที่คุณไม่เคยได้ทดสอบ ซึ่งในสภาพแวดล้อมการใช้งานจริงนั้นก็คือข้อมูลส่วนใหญ่
เหตุใดเวลาในการประมวลผลจึงเป็นตัววัดประสิทธิภาพของอัลกอริทึมที่ไม่ดี
แล้วทำไมไม่ลองใช้ตัวจับเวลาในการประมวลผลดูล่ะ? หลายคนก็ทำแบบนั้น และผมเข้าใจ แต่ปัญหาคือเวลาในการประมวลผลจะดึงเอาสิ่งต่างๆ มากมายที่อัลกอริทึมของคุณไม่เกี่ยวข้องเข้ามาเกี่ยวข้องด้วย:
- ฮาร์ดแวร์ แล็ปท็อปอายุห้าปีของผมกับอุปกรณ์จัดเก็บข้อมูลบนคลาวด์ตัวใหม่เอี่ยมจะให้ผลลัพธ์ที่แตกต่างกันอย่างมากสำหรับสคริปต์เดียวกัน
- ภาษาโปรแกรม เขียนลูปเดียวกันในภาษา C และ Python คุณอาจเห็นความแตกต่างถึง 10 เท่า หรือมากกว่านั้น
- โหลดระบบ การ อัปเดตเบื้องหลังบางอย่างเริ่มทำงาน ตัวเก็บขยะทำงาน แคชถูกปิดใช้งาน ผลลัพธ์ของคุณจึงเคลื่อนที่
- ไม่ว่าคุณจะหยิบข้อมูลป้อนเข้า แบบใดก็ตาม การเรียงลำดับที่เร็วกับข้อมูลที่เกือบเรียงลำดับแล้ว อาจช้าลงกับข้อมูลที่สลับตำแหน่งกัน
นาฬิกาจับเวลาจะให้ข้อมูลการทำงานเพียงครั้งเดียวกับอุปกรณ์หนึ่งชิ้นและอินพุตเดียว แต่ถ้าถามถึงข้อมูลที่มากกว่า 100 เท่า มันจะทำงานไม่ได้เลย
จำนวนขั้นตอนไม่เปลี่ยนแปลง ใช้อัลกอริทึมเดียวกัน ข้อมูลป้อนเข้าเดียวกัน และคุณจะได้จำนวนขั้นตอนเท่ากัน ไม่ว่าจะเป็น Rust บนเซิร์ฟเวอร์แบบแร็ค หรือ JavaScript บนโทรศัพท์ของใครสักคน นั่นเป็นเหตุผลว่าทำไมความซับซ้อนของเวลาจึงเป็นการแข่งขันที่ยุติธรรมระหว่างสองวิธีแก้ปัญหา ก่อนที่คุณจะทำการวัดประสิทธิภาพ ถึงแม้ว่าหลังจากนั้นผมก็ยังแนะนำให้วัดประสิทธิภาพอยู่ดี มันเป็นเพียงคำถามที่แตกต่างกันเท่านั้น
คำอธิบายเกี่ยวกับสัญลักษณ์ Big O และสัญลักษณ์เชิงอะซิมโทติกอื่นๆ
ตำราเรียนเรียกสิ่งนี้ว่า สัญกรณ์เชิงเส้นกำกับ ซึ่งฟังดูแย่กว่าความเป็นจริง คุณปล่อยให้ n มีค่ามหาศาลและเลิกสนใจรายละเอียดเล็กๆ น้อยๆ ดังนั้น ตัวคูณคงที่และปัจจัยนำเข้าเล็กๆ น้อยๆ จะหายไป เหลือเพียงเส้นโค้งการเติบโตเท่านั้น มีสามเส้นโค้งที่ควรทราบ:
| สัญกรณ์ | มันอธิบายถึงอะไร | ความหมายตรงไปตรงมา | ตัวอย่าง |
|---|---|---|---|
| บิ๊กโอ, โอ(ฟ(น)) | ขอบเขตบน | อัลกอริทึมเติบโตไม่เร็วกว่า f(n) | การค้นหาเชิงเส้นคือ O(n) |
| บิ๊กโอเมก้า, Ω(f(n)) | ขอบล่าง | อัลกอริทึมนี้ต้องการงานอย่างน้อย f(n) ครั้ง | การเรียงลำดับแบบเปรียบเทียบใดๆ ก็ตามคือ Ω(n log n) |
| บิ๊กธีตา, Θ(f(n)) | ผูกแน่น | ขอบเขตบนและล่างตรงกัน | การเรียงลำดับแบบผสาน (Merge sort) มีประสิทธิภาพ Θ(n log n) |
ในทางปฏิบัติ คุณจะได้ยินการใช้สัญลักษณ์ Big O ประมาณ 95% ของเวลาทั้งหมด มันเป็นการกำหนดขอบเขตบน หมายความว่าเวลาในการทำงานจะไม่เพิ่มขึ้นเร็วกว่าอัตราที่ระบุไว้ในวงเล็บ ในการตรวจสอบโค้ดครั้งแรกของผมในที่ทำงานจริง นักพัฒนาอาวุโสคนหนึ่งเขียนว่า "O(n²), โปรดแก้ไข" ไว้ข้างๆ ลูปซ้อนกัน และสิ่งที่พวกเขาหมายถึงก็คือ ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดคือแบบกำลังสอง และรายการที่จะแก้ไขนั้นกำลังจะยาวขึ้นมาก
โอเมกาและเธต้าส่วนใหญ่มักพบในหลักสูตรมหาวิทยาลัยเกี่ยวกับการวิเคราะห์อัลกอริทึม และผมคิดว่าผมไม่ได้พิมพ์คำเหล่านี้ในที่ทำงานมาหลายปีแล้ว โอเมกาชนะใจผมเพราะมันตอบคำถามที่คนถามจริงๆ ในที่ประชุม ซึ่งก็คือ "ถ้าปริมาณการใช้งานเพิ่มขึ้นสามเท่า สถานการณ์จะแย่ลงแค่ไหน?"
มีรายละเอียดทางเทคนิคอย่างหนึ่งที่ทำให้ผมสับสนอยู่พักใหญ่ เนื่องจาก Big O เป็นเพียงค่าสูงสุด ดังนั้นฟังก์ชัน O(n) จึงเป็น O(n²) อย่างเคร่งครัด เหมือนกับที่คนสูง 5 ฟุต "ต่ำกว่า 7 ฟุต" จริงอยู่แต่ก็ไร้ประโยชน์ ทุกคนมักจะยกขอบเขตที่แคบที่สุดเท่าที่จะหาเหตุผลมาสนับสนุนได้ และผมก็จะทำเช่นเดียวกัน
คลาสความซับซ้อนของเวลาทั่วไป พร้อมตัวอย่าง
ในโค้ดจริง คุณจะได้เห็นคลาสไม่มากนัก อาจจะแค่เจ็ดคลาสถ้าหากนับรวมคลาสที่ซับซ้อนด้วย นี่คือค่าใช้จ่ายโดยประมาณของแต่ละคลาสเมื่อ n = 1,000:
| ระดับ | ชื่อ | ตัวอย่างทั่วไป | การดำเนินงานที่ n = 1,000 |
|---|---|---|---|
| O(1) | คงที่ | ดัชนีอาร์เรย์ การค้นหาในตารางแฮช | 1 |
| O(log n) | ลอการิทึม | การค้นหาแบบไบนารี | ~10 |
| บน) | เชิงเส้น | การสแกนรายการ | 1,000 |
| O(n log n) | ลิเนียร์ลิธมิค | การเรียงลำดับแบบผสาน (Merge sort), การเรียงลำดับแบบเร็ว (Quick sort) (ค่าเฉลี่ย) | ~10,000 |
| โอ(n²) | กำลังสอง | ลูปซ้อนกัน, การเรียงลำดับแบบบับเบิล | 1,000,000 |
| O(2ⁿ) | เลขชี้กำลัง | ลำดับฟิโบนาชชีแบบเรียกซ้ำอย่างง่าย | มากกว่าอะตอมในจักรวาล |
| บน!) | แฟกทอเรียล | พนักงานขายเดินทางแบบใช้กำลังเข้าสู้ | ใหญ่กว่านั้นอีก |
O(1): เวลาคงที่
ไม่ว่าพจนานุกรม Python ของคุณจะมีคีย์สิบตัวหรือสิบล้านตัว การดึงคีย์ออกมาหนึ่งตัวก็มีค่าใช้จ่ายประมาณเท่ากัน และการอ่านรายการ[5] จากรายการก็เช่นกัน ความราบเรียบนั้นคือจุดประสงค์ทั้งหมดของเวลาคงที่
O(log n): เวลาเชิงลอการิทึม
ผมคิดว่านี่คืออัลกอริธึมประเภท "เดาตัวเลขระหว่าง 1 ถึง 100" ซึ่งการเดาแต่ละครั้งจะตัดตัวเลือกที่เหลือออกไปครึ่งหนึ่ง การค้นหาแบบไบนารีก็ทำแบบนั้นกับรายการที่เรียงลำดับแล้วเช่นกัน:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
เมื่อมีรายการที่จัดเรียงแล้วเป็นพันล้านรายการ จะต้องเปรียบเทียบประมาณ 30 ครั้ง ในขณะที่การเปรียบเทียบทีละรายการอาจใช้เวลาถึงพันล้านรายการ และผมก็ยังคงรู้สึกว่ามันตลกอยู่เสมอ
O(n) และ O(n log n)
อัลกอริทึมเชิงเส้นจะตรวจสอบแต่ละองค์ประกอบเป็นจำนวนครั้งคงที่ เหมือนกับการค้นหาตัวเลขที่ใหญ่ที่สุดในคอลัมน์ของสเปรดชีตด้วยสายตา O(n log n) คืออัลกอริทึมการเรียงลำดับที่ดี ส่วนการเรียงลำดับแบบผสาน (Merge sort) จะแบ่งรายการออกเป็นรายการเดี่ยวๆ (ระดับการแบ่ง log n) จากนั้นจะทำการประมวลผลเชิงเส้นหนึ่งครั้งต่อระดับในขณะที่ผสานเข้าด้วยกัน ดังนั้นเวลาในการทำงานจึงคงที่ ไม่ว่าข้อมูลจะเรียงลำดับแล้วหรือไม่ก็ตาม
O(n²) และแย่กว่านั้น
โค้ดแบบกำลังสองมักจะมีลูปซ้อนอยู่ในลูปอีกอันเสมอ เช่น การตรวจสอบค่าซ้ำที่เปรียบเทียบทุกคู่ดังนี้:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
การเติบโตแบบเลขชี้กำลังและแบบแฟกทอเรียลแย่กว่ามาก สูตรฟิโบนาชี่แบบเวียนซ้ำในตำราเรียนจะแก้ปัญหาเดิมซ้ำแล้วซ้ำเล่า ดังนั้นทุกๆ การเพิ่ม n ขึ้น 1 จะทำให้งานเพิ่มขึ้นเป็นสองเท่าโดยประมาณ ที่ n = 20 คุณจะไม่สังเกตเห็นความเปลี่ยนแปลง แต่ที่ n = 60 คุณสามารถไปทำอาหารเย็น กินข้าว ล้างจาน แล้วงานก็ยังไม่เสร็จอยู่ดี
วิธีการคำนวณความซับซ้อนของเวลาทีละขั้นตอน
คุณแทบจะไม่ต้องใช้การพิสูจน์อย่างเป็นทางการเพื่อคำนวณความซับซ้อนของเวลาเลย ผมลองคิดตามรายการนี้ในใจ และมันครอบคลุมโค้ดส่วนใหญ่ที่ผมเห็น:
- กำหนดค่า n และ ระบุว่าขนาดของข้อมูลนำเข้าคืออะไร เช่น ความยาวของลิสต์ จำนวนโหนดในกราฟ หรือจำนวนหลักในตัวเลข
- นับปริมาณงานในแต่ละบรรทัด คำสั่งง่ายๆ (การกำหนดค่า การเปรียบเทียบ การคำนวณทางคณิตศาสตร์) ใช้ทรัพยากร O(1)
- เพิ่มบล็อกตามลำดับ ลูป สองลูปต่อกัน โดยแต่ละลูปวนซ้ำ n จะได้ n + n = 2n
- คูณ บล็อกที่ซ้อนกัน การ วนลูปผ่าน n ภายในลูปผ่าน n อีกครั้งจะให้ผลลัพธ์เป็น n × n = n²
- ตัดค่าคงที่ออก 2n กลายเป็น n และ 500 กลายเป็น 1
- เก็บเฉพาะพจน์ที่เด่นที่สุดไว้ ใน n² + n ส่วนของ n² จะมีค่ามากกว่าส่วนที่เหลืออย่างมากเมื่อ n เพิ่มขึ้น
ตัวอย่างที่ทำได้อย่างรวดเร็ว จำนวนที่ได้คือ T(n) = 3n² + 5n + 2 แทนค่าหนึ่งล้านลงไป: 3n² คือสามล้านล้าน, 5n คือห้าล้าน เกิดข้อผิดพลาดจากการปัดเศษ เรียกได้ว่าเป็น O(n²) เสร็จแล้ว
ลูปที่กระโดดข้ามไปมาแทนที่จะก้าวทีละขั้นนั้นซับซ้อนกว่า:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
ในแต่ละรอบการทำงาน n จะลดลงครึ่งหนึ่ง ดังนั้นลูป while นี้จะหยุดทำงานหลังจากประมาณ log₂(n) รอบ ซึ่งโดยพื้นฐานแล้วนี่คือคำตอบทั้งหมดของคำถามที่ว่า "เมื่อใดที่ความซับซ้อนของเวลาเป็น O(log n)?" ถ้าสิ่งที่เหลืออยู่ลดลงด้วยปัจจัยคงที่ในแต่ละขั้นตอน นั่นหมายความว่าถึงจุดนั้นแล้ว
การเรียกซ้ำต้องการเครื่องมืออีกอย่างหนึ่ง นั่นคือความสัมพันธ์เวียนเกิด การเรียงลำดับแบบผสาน (Merge sort) ทำงานขนาดครึ่งหนึ่งสองครั้งแล้วจึงผสานเข้าด้วยกัน ดังนั้น T(n) = 2T(n/2) + n ทฤษฎีบทหลัก (Master Theorem) เป็นเหมือนคู่มือลัดสำหรับความสัมพันธ์เวียนเกิดที่มีรูปร่างแบบนั้น และสำหรับความสัมพันธ์เวียนเกิดนี้ มันจะให้ผลลัพธ์เป็น O(n log n)
และกฎง่ายๆ จากการเขียนโปรแกรมเชิงแข่งขันที่ผมใช้บ่อยๆ คือ เครื่องคอมพิวเตอร์ทั่วไปจะประมวลผลการคำนวณง่ายๆ ได้ประมาณ 10⁸ ครั้งต่อวินาที เป็นการประมาณอย่างคร่าวๆ แต่ก็เพียงพอที่จะตรวจสอบความซับซ้อนของเวลาในการแก้ปัญหา ก่อนที่จะกดส่ง ถ้า n เท่ากับ 10⁵ O(n²) จะใช้เวลาประมาณ 10¹⁰ ครั้ง ดังนั้นจึงหมดเวลา ส่วน O(n log n) จะใช้เวลาน้อยกว่า 2 ล้านครั้ง จึงผ่านไปได้อย่างราบรื่น
การวิเคราะห์กรณีเลวร้ายที่สุด กรณีดีที่สุด และกรณีเฉลี่ย
หากป้อนข้อมูลที่แตกต่างกันให้กับอัลกอริทึมเดียวกัน ปริมาณงานก็อาจเปลี่ยนแปลงไปอย่างมาก การค้นหาเชิงเส้นแสดงให้เห็นสิ่งนี้ได้อย่างชัดเจน:
- กรณีที่ดีที่สุด: สิ่งที่คุณต้องการจะอยู่ด้านหน้าสุด ถ้าเปรียบเทียบเพียงครั้งเดียว คุณก็ตกรอบไปเลย
- กรณีที่แย่ที่สุด: มันอยู่ตอนท้ายสุด หรือไม่มีอยู่เลย นั่นคือการเปรียบเทียบ
- กรณีเฉลี่ย: ถ้าเป็นไปได้ทุกที่ที่มีโอกาสเท่ากัน คุณจะตรวจสอบประมาณ n/2 โดยเฉลี่ย ซึ่งยังคงเป็น O(n) อยู่ดี
หากคุณถามนักพัฒนาซอฟต์แวร์เกี่ยวกับ "ความซับซ้อน" ของบางสิ่งบางอย่าง พวกเขามักจะบอกคุณถึงความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุด เพราะตัวเลขนั้นเป็นคำมั่นสัญญาที่คุณสามารถวางแผนได้
สมมติว่า API ของคุณประมวลผลคำขอได้ในเวลา O(n) ในกรณีที่แย่ที่สุด เยี่ยมเลย ตอนนี้คุณรู้แล้วว่าคำขอที่ช้าที่สุดทำงานอย่างไร และคุณก็พร้อมรับมือเมื่อมีคนส่งข้อมูลขยะมาให้คุณโดยเจตนา แน่นอนว่ามีคนทำแบบนี้: ถ้าผู้โจมตีรู้ว่าคีย์ใดทำให้ตารางแฮชของคุณเกิดการชนกัน คีย์เหล่านั้นจะเป็นคีย์เดียวที่คุณจะได้เห็นไปสักพัก
กรณีเฉลี่ยเป็นสิ่งที่ควรพิจารณา เนื่องจากสถานการณ์ที่เลวร้ายแทบจะไม่เกิดขึ้นเลย Quicksort เป็นตัวอย่างที่ดีในเรื่องนี้ โดยมีประสิทธิภาพเฉลี่ย O(n log n) แต่จะลดลงเหลือ O(n²) หากเลือกจุดหมุนอย่างไม่รอบคอบบนข้อมูลที่เรียงลำดับแล้ว ไลบรารีมาตรฐานแก้ไขปัญหานี้ด้วยการเลือกจุดหมุนแบบสุ่ม หรือโดยการเปลี่ยนไปใช้อัลกอริทึมการเรียงลำดับอื่นเมื่อการเรียกซ้ำลึกเกินไปจนน่าสงสัย
ความซับซ้อนของพื้นที่และพื้นที่เสริมคืออะไร?
หน่วยความจำคือค่าใช้จ่ายอีกอย่างหนึ่งที่อัลกอริทึมก่อให้เกิด ความซับซ้อนของพื้นที่จัดเก็บข้อมูลจะติดตามว่าคุณต้องการพื้นที่จัดเก็บข้อมูลมากแค่ไหนเมื่อขนาดของข้อมูลป้อนเข้าเพิ่มขึ้น และคุณสามารถเขียนมันด้วยสัญกรณ์ Big O เดียวกันกับเวลา
ส่วนหนึ่งของหน่วยความจำนั้นคือข้อมูลป้อนเข้า ซึ่งคุณต้องจ่ายค่าใช้จ่ายนั้นไม่ว่าคุณจะทำอะไรกับมันก็ตาม ส่วนที่คุณควบคุมได้จริง ๆ เรียกว่าพื้นที่เสริม หมายถึงสิ่งพิเศษที่โค้ดของคุณจัดสรรขณะทำงาน เช่น ตัวแปรชั่วคราวและอาร์เรย์ใหม่ รวมถึงสแต็กการเรียกใช้ฟังก์ชันที่ไม่มีใครจำได้จนกว่าจะเกิดปัญหาขึ้น
ตัวอย่างกรณีศึกษาอย่างรวดเร็ว:
- การสลับตัวแปรสองตัวต้องใช้สล็อตสองสามสล็อตโดยไม่คำนึงถึงสิ่งอื่นใด ดังนั้นจึงใช้พื้นที่เสริม O(1)
- การคัดลอกรายการที่มี n รายการลงในรายการใหม่จะใช้หน่วยความจำเพิ่มขึ้น O(n)
- การเรียกซ้ำลึก n ระดับจะทำให้มีเฟรม n เฟรมอยู่บนสแต็ก ซึ่งใช้พื้นที่ O(n) แม้ว่าคุณจะไม่ได้สร้างอาร์เรย์เลยก็ตาม
ผมเคยเห็นนักพัฒนาซอฟต์แวร์รุ่นน้องคนหนึ่งเสียเวลาช่วงบ่ายไปกับปัญหาข้อสุดท้ายนั้น ฟังก์ชันเรียกตัวเองซ้ำของเขาดูเหมือนจะไม่ใช้หน่วยความจำเลย แต่การเรียกที่ไม่เสร็จสมบูรณ์แต่ละครั้งจะถูกพักไว้บนสแต็กเพื่อรอให้การเรียกที่อยู่ลึกกว่านั้นส่งค่ากลับ และเมื่อรับข้อมูลขนาดใหญ่เข้ามา ระบบก็ล่มเพราะเกิดสแต็กโอเวอร์โฟลว์
การเพิ่มประสิทธิภาพส่วนใหญ่ก็คือการแลกเปลี่ยนหน่วยความจำกับเวลา หรือในทางกลับกัน การจดจำผลลัพธ์ (Memoization) จะแคชผลลัพธ์ที่คุณคำนวณไว้แล้ว ซึ่งทำให้การคำนวณแบบ Fibonacci ง่ายๆ ใช้เวลาน้อยลงจาก O(2ⁿ) เหลือ O(n) โดยแลกกับหน่วยความจำ O(n) ตารางแฮชช่วยให้คุณค้นหาข้อมูลได้โดยเฉลี่ย O(1) โดยใช้พื้นที่กับบัคเก็ต บนเซิร์ฟเวอร์ที่มี RAM 64 GB การแลกเปลี่ยนแบบนี้มักจะคุ้มค่า แต่บนไมโครคอนโทรลเลอร์หรือภายในสัญญาอัจฉริยะ คุณอาจต้องคิดให้ดีก่อน
ความซับซ้อนด้านเวลาและพื้นที่ของโครงสร้างข้อมูลทั่วไป
การเลือกโครงสร้างข้อมูลที่เหมาะสมมักจะดีกว่าการปรับแต่งรายละเอียดเล็กๆ น้อยๆ ภายในลูปของคุณ ต่อไปนี้คือค่าใช้จ่ายโดยเฉลี่ยสำหรับโครงสร้างข้อมูลที่คุณจะใช้บ่อยที่สุด:
| โครงสร้างข้อมูล | เข้าถึง | ค้นหา | แทรก | ลบ | ช่องว่าง |
|---|---|---|---|---|---|
| อาร์เรย์ | O(1) | บน) | บน) | บน) | บน) |
| รายการเชื่อมโยง | บน) | บน) | O(1) | O(1) | บน) |
| ตารางแฮช | ไม่มีข้อมูล | O(1) | O(1) | O(1) | บน) |
| ต้นไม้ค้นหาไบนารีที่สมดุล | O(log n) | O(log n) | O(log n) | O(log n) | บน) |
| ฮีปไบนารี | O(1) สำหรับ min/max | บน) | O(log n) | O(log n) | บน) |
หมายเหตุสองข้อ การแทรกและการลบในลิสต์แบบเชื่อมโยงใช้เวลาเพียง O(1) หากคุณถือโหนดนั้นอยู่แล้ว และตารางแฮชอาจใช้เวลาถึง O(n) เมื่อมีคีย์จำนวนมากชนกัน
อัลกอริทึมการเรียงลำดับมีความหลากหลายมากเช่นกัน:
| อัลกอริทึมการเรียงลำดับ | ดีที่สุด | เฉลี่ย | แย่ที่สุด | พื้นที่เสริม |
|---|---|---|---|---|
| การเรียงลำดับแบบฟอง | บน) | โอ(n²) | โอ(n²) | O(1) |
| การเรียงลำดับแบบผสาน | O(n log n) | O(n log n) | O(n log n) | บน) |
| เรียงลำดับเร็ว | O(n log n) | O(n log n) | โอ(n²) | O(log n) |
| การเรียงลำดับแบบฮีป | O(n log n) | O(n log n) | O(n log n) | O(1) |
การเรียงลำดับแบบผสาน (Merge sort) คาดเดาผลลัพธ์ได้ แต่ต้องการหน่วยความจำเพิ่มเติม การเรียงลำดับแบบฮีป (Heap sort) เรียงลำดับในตำแหน่งเดิมและคงกรณีที่เลวร้ายที่สุดไว้เหมือนเดิม ส่วนการเรียงลำดับแบบเร็ว (Quicksort) แม้จะมีข้อจำกัดที่ซับซ้อนกว่า แต่โดยทั่วไปแล้วมักจะได้ผลดีกว่าในทางปฏิบัติ
ความซับซ้อนเชิงเวลาในบล็อกเชนและสัญญาอัจฉริยะ
นี่แหละคือจุดที่สนุก บนเซิร์ฟเวอร์ของคุณเอง อัลกอริทึมที่หละหลวมจะสิ้นเปลือง CPU และอาจทำให้ผู้ใช้รำคาญ แต่บน Ethereum หรือเครือข่าย EVM ใดๆ มันจะสิ้นเปลืองเงิน ทุกคำสั่งที่สัญญาอัจฉริยะดำเนินการจะเสียค่าธรรมเนียมแก๊ส ซึ่งจ่ายด้วยเหรียญดั้งเดิมของเครือข่าย ดังนั้นจำนวนการดำเนินการของคุณจะปรากฏเป็นรายการในบิลของใครบางคน กล่าวอีกนัยหนึ่ง ความซับซ้อนของเวลาที่ไม่ดีนั้นมาพร้อมกับราคาที่ต้องจ่าย
สมมติว่าคุณมีสัญญาที่วนลูปจ่ายรางวัลให้กับผู้ถือโทเค็นทุกราย O(n) และค่าธรรมเนียมแก๊สจะเพิ่มขึ้นเรื่อย ๆ ทุกครั้งที่มีผู้ถือโทเค็นรายใหม่เข้ามา ในวันเปิดตัวไม่มีใครสังเกตเห็น
จากนั้นรายชื่อผู้ถือครองก็เพิ่มขึ้นเรื่อยๆ วันหนึ่งการจ่ายเงินต้องการค่าแก๊สมากกว่าขีดจำกัดแก๊สของบล็อก ซึ่งเป็นขีดจำกัดว่าบล็อกเดียวสามารถรองรับแก๊สได้มากแค่ไหน หลังจากนั้นธุรกรรมก็จะไม่สามารถดำเนินการได้ ไม่ใช่เพราะ "มันช้า" แต่มันไม่สำเร็จเลย และเงินทุนใดๆ ที่รออยู่เบื้องหลังฟังก์ชันนั้นก็จะติดอยู่ตรงนั้น ผู้ตรวจสอบบัญชีจะรายงานลูปที่ไม่มีที่สิ้นสุดเช่นนี้ภายใต้การโจมตีแบบปฏิเสธการให้บริการ และก็สมเหตุสมผลดี
วิธีแก้ปัญหาคือการคิดเชิงซับซ้อนอย่างแท้จริงและตรงไปตรงมา:
- แบ่งงานออกเป็นกลุ่มย่อยขนาดคงที่หลายกลุ่ม โดยแต่ละกลุ่มจะทำผ่านธุรกรรมหลายรายการ
- พลิกกลับด้านเพื่อให้ผู้ใช้แต่ละคนรับรางวัลของตนเอง การเรียกใช้แต่ละครั้งใช้เวลา O(1)
- เปลี่ยนจากการตรวจสอบด้วยลูปเป็นการตรวจสอบด้วยเมอร์เคิล
ฉันชอบ Merkle proofs ในฐานะตัวอย่างที่แสดงให้เห็นว่าทำไม log n ถึงมีความสำคัญมากบนบล็อกเชน Merkle tree จะทำการแฮชข้อมูลจำนวนมากให้ไปอยู่ในแฮชรากเดียว
ในการพิสูจน์ว่ารายการหนึ่งเป็นส่วนหนึ่งของเซตที่มี n รายการ คุณต้องใช้แฮชประมาณ log₂(n) ครั้ง สำหรับรายการหนึ่งล้านรายการ ก็ประมาณ 20 ครั้ง ไม่ใช่หนึ่งล้านรายการ การแจกเหรียญฟรี (Airdrop) อาศัยหลักการนี้ และกระเป๋าเงิน Bitcoin แบบเบา (Light Wallet) ก็ใช้เทคนิคเดียวกันนี้ในการยืนยันธุรกรรมโดยไม่ต้องดาวน์โหลดบล็อกทั้งหมด
นอกเครือข่ายก็เช่นเดียวกัน ลองนึกภาพระบบแบ็กเอนด์การชำระเงินที่จับคู่ธุรกรรมบล็อกเชนขาเข้าแต่ละรายการกับใบแจ้งหนี้โดยการสแกนใบแจ้งหนี้ที่ยังเปิดอยู่ทั้งหมด การประมวลผลต่อการชำระเงินหนึ่งครั้งจะเป็น O(n) และจะช้าลงเมื่อร้านค้าเติบโตขึ้น หากนำใบแจ้งหนี้ไปใส่ในแผนที่แฮชโดยใช้ที่อยู่หรือรหัสเป็นคีย์ การจับคู่แต่ละครั้งจะเป็น O(1) และหากคุณไม่อยากสร้างและดูแลระบบนั้นด้วยตัวเอง เกตเวย์การชำระเงินคริปโตอย่าง Plisio ก็จะจัดการให้คุณได้
