การวิเคราะห์ Time Complexity ของ Algorithm

Time Complexity เป็นศัพท์เฉพาะทางในทาง Programming ที่บ่งบอกถึง จำนวนเวลาที่ใช้ในการทำงาน ของ Algorithm ซึ่งการเปรียบเทียบผลลัพท์ที่ออกมาจาก การคำนวน Time Complexity จะเปรียบเทียบโดยใช้ Time Complexity Classes ดังนี้ (เรียงจากโตช้า ไปโตเร็ว)

โตช้า หมายถึง จำนวนเวลาเพิ่มช้า = ทำงานเร็ว

โตเร็ว หมายถึง จำนวนเวลาเพิ่มเร็ว = ทำงานช้า มากขึ้นเรื่อยๆ เมื่อมีจำนวนข้อมูลมาก

Image: freecodecamp.org

• C หมายถึง Constant ใดๆ เช่น 1, 2, 3, 4
• log n
• √n หมายถึง n^0.5
• n
•  n log n
• n²
• 2ⁿ
• n! เช่น  5! = 5*4*3*2*1

โจทย์ตัวอย่าง

โจทย์ตัวอย่างจะเป็นการวิเคราะห์ Time Complexity ของ Algorothm จัดเรียงข้อมูล แบบ Selection Sort

function selection_sort(arr) {
    for(i = 0; i < arr.length - 1; i++) {
        for(j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[i]) {
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}

T(n) = ∑_i=0^{n - 1} ∑_{j=i + 1}ⁿ 1 : เข้าสูตรที่ 1 (sum c)
T(n) = ∑_i=0^{n - 1} n + 1 - i + 1 : เข้าสูตรที่ 2 (sum i)
T(n) = (n - 1)(n - 1 + 1) 2 - 0(0 - 1) 2 + 1 - i + 1
T(n) = n(n - 1)2 - 1 + 1 - i + 1
T(n) = n(n - 1)2 - i + 1
T(n) = n^2 - n2 - i + 1
T(n) = θ (n²)

จากนั้นเราจะเลือก Term ที่ใหญ่ที่สุดของสมการที่เราพึ่งแก้ ซึ่งนั้นก็คือ n² เวลาเราบ่งบอกจะนำหน้าด้วย θ  หมายถึง "โตเท่ากับ" ก็จะเป็น T(n) = θ (n²) หากเราต้องการจะลองใส่ค่า n เข้าไป ซึ่งก็คือ ขนาดของข้อมูล เราจะได้ 5² = 25 ซึ่งก็หมายความว่า หากเราใส่ข้อมูลขนาด 5 ตัว จะมีรอบจริงในการวนรอบทั้งหมด 25 รอบ

จากข้อมูลนี้เราจะเห็นว่า Algorithm ที่มี For Loop ซ้อนกัน 2 อัน Time Complexity ก็มีแนวโน้วที่จะเป็น n² หากมี For Loop ซ้อนกัน 3 อัน Time Complexity ก็มีแนวโน้วที่จะเป็น n³ เป็นต้น แต่จะเป็นเฉพาะกับ Algorithm ที่แต่ละ Loop จะทำงาน  n ครั้งเท่านั้น อาจจะมี Algorithm ที่มี For Loop ซ้อนกัน 2 อัน แต่ไม่ได้มี Time Complexity เป็น n² ก็ได้ หากจำนวนรอบแต่ละ Loop วนซ้ำไม่ถึง n ครั้ง