หนึ่งในการวิเคราะห์เวลาในการทำงานที่โปรแกรมเมอร์รู้จักกันดีคือ Big-O notation

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

เช่นอัลกอริทึม A และ B เมื่อทำงานบนข้อมูลนำเข้าขนาด N มีการทำงาน N ขั้นตอน แต่ละขั้นตอนใช้เวลาการทำงานไม่เกิน $ O(N) $ อัลกอริทึมทั้งคู่นี้จะใช้เวลาทำงาน $ O(N^2) $

แต่ถ้าหากในความเป็นจริงแล้ว ไม่ใช่ทุกครั้งที่ A จะใช้เวลาถึง $ O(N) $ หลายๆครั้งอาจจะใช้เวลาแค่ $ O(1) $ แล้วนานๆครั้งถึงจะมีการใช้เวลาถึง $ O(N) $ แต่ B นั้นจะใช้เวลา $ O(N) $ ทุกครั้ง เราพอจะบอกว่า A เร็วกว่า B ได้ไหม?

ตัวอย่างปัญหาคลาสสิค

การจองหน่วยความจำเพื่อใช้เป็นอาเรย์นั้นจำเป็นต้องระบุว่าจะจองจำนวนกี่ช่อง ถ้าหากเราอยากได้หน่วยความจำที่ไม่จำกัดจำนวน เราอาจเลือกใช้โครงสร้างข้อมูลแบบ linked list แทน ซึ่ง linked list มีข้อเสียที่การเข้าถึงข้อมูลด้วยตำแหน่ง บนโครงสร้างข้อมูลขนาด $ N $ จะใช้เวลา $ O(N) $ แทนที่จะเป็น $ O(1) $ เหมือนอาเรย์

แต่ในภาษาโปรแกรมมิ่งทั่วๆไปเราจะเห็นว่า มีโครงสร้างข้อมูลคล้ายอาเรย์ที่สามารถอ้างถึงข้อมูลด้วยตำแหน่งได้อย่างรวดเร็ว รวมถึงไม่จำเป็นต้องระบุขนาดก่อน เช่น [] ของ javascript หรือ vector ของ C++ ที่สามารถ push() หรือ push_back() ได้อย่างอิสระ

วิธีสร้างโครงสร้างข้อมูลที่มีคุณสมบัติแบบนี้อย่างง่ายที่สุดก็คือ

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

จะเห็นได้ว่าถ้าหากวิเคราะห์เวลาการทำงานแบบเดิมๆ ไม่ว่าเราจะเริ่มจองอาเรย์ขนาดเท่าไหร่และขยายขนาดอาเรย์เมื่อเต็มอย่างไร การเพิ่มสมาชิกลงอาเรย์หนึ่งครั้งก็อาจจะใช้เวลาทำงานถึง $ O(N) $ เนื่องจากต้องใช้เวลาเพื่อคัดลอกอาเรย์

ตัวอย่างอัลกอริทึมที่น่าสนใจ

อัลกอริทึม A

จองอาเรย์ขนาดเป็นกำลังของสอง นั่นคือ $ 1,2,4,8,16,… $ เช่น เมื่อเรามีอาเรย์ขนาด 16 แล้วมีสมาชิกตัวที่ 17 ถูกเพิ่มมา เราจะจองอาเรย์ใหม่ขนาด 32 แล้วจึงคัดลอกอาเรย์

อัลกอริทึม B

จองอาเรย์เพิ่มขนาดทีละ 1 เช่น เมื่อเรามีอาเรย์ขนาด 16 แล้วมีสมาชิกตัวที่ 17 ถูกเพิ่มมา เราจะจองอาเรย์ใหม่ขนาด 17 แล้วจึงคัดลอกอาเรย์

ทั้งสองอัลกอริทึมอาจจะใช้เวลาในการเพิ่มสมาชิกมากถึง $ O(N) $ เมื่อมีสมาชิกอยู่แล้ว N ตัว ณ ขณะที่เพิ่มสมาชิก แต่พิจารณาแล้วเราจะเห็นได้ไม่ยากว่า อัลกอริทึม A ควรจะเร็วกว่า B

การวิเคราะห์เวลาการทำงานอีกรูปแบบหนึ่ง

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

ให้ $ T(X,N) $ แทนเวลาการทำงานทั้งหมดเพื่อเพิ่มสมาชิกจากศูนย์ไปเป็น N ตัว เมื่อจองอาเรย์ด้วยอัลกอริทึม X และ $ 2^k \le N \le 2^{k+1} $

\[\begin{align} T(A,N) &= 1 + (1+1) + (2+1) + 1 + (4+1) + ... + (2^k + 1) + 1 + ... \\ &= N + 1 + 2 + 4 + ... + 2^k \\ &\le N + 2N \\ &= 3N \\ &= O(N) \end{align}\]

และ

\[\begin{align} T(B,N) &= 1 + (1+1) + (2+1) + (3+1) + (4+1) + ... + ((N-1)+1) \\ &= N + 1 + 2 + 3 + ... + (N - 1) \\ &= N + \frac{N(N-1)}{2} \\ &= \frac{N^2 + N}{2} \\ &\le N^2 \\ &= O(N^2) \end{align}\]

จะพบว่าอัลกอริทึม A ใช้เวลาเฉลี่ยเป็นค่าคงที่ต่อการเพิ่มสมาชิกหนึ่งตัว ซึ่งเขียนแทนด้วย $ \tilde{O}(1) $ และอัลกอริทึม B ใช้เวลาเฉลี่ย (ซึ่งเท่ากับกรณีที่แย่ที่สุด) $ \tilde{O}(N) $ ต่อการเพิ่มสมาชิกหนึ่งตัว

ซึ่งวิธีการวิเคราะห์เวลาแบบเฉลี่ยต่อหลายจำนวนขั้นตอนนี้เรียกว่า Amortized analysis

ตอนแรกว่าจะมินิบล็อก สุดท้ายก็ไม่ค่อยมินิเท่าไหร่แฮะ…