Big O Notation - Độ phức tạp của thuật toán

Độ phức tạp của thuật toán hay gọi là thời gian thực hiện giải thuật (Big O Notation) có thể được hiểu là tiêu chí đánh giá hiệu quả thực hiện thuật toán khi kích thước input tăng tới n. Độ phức tạp của thuật toán không phụ thuộc vào các thiết bị tính toán, bộ nhớ ... mà nó chỉ phụ thuộc vào việc hiệu quả thực hiện của thuật toán như thế nào khi kích thước input tăng.

Làm một cuộc so sánh

Để hiểu về Big O Notation là một điều cần thiết khi so sánh thuật toán. Và trong ví dụ chúng ta sẽ so sánh các kỹ thuật để tìm kiếm giá trị trong một mảng đã được sắp xếp.

//Mảng mẫu đơn giản
let numberList : Array<Int> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Độ phức tạp tuyến tính - Linear Time - O(n)

Cách tiếp cần thông thường của chúng ta là "brute force" kỹ thuật liên quan tới lặp hết các phần tử của mảng cho đến khi chúng ta tìm ra kết quả. Trong Swift, thuật toán có thể được cài đặt như sau:

//brute force approach - O(n) linear timefunc linearSearch(key : Int) {
        for number in numberList {
               if (number == key) {
                    let results = "value \(key) found."
                     break
               }
        }
}

Ở đây để tìm được kết quả thì mỗi thành phần trong mảng phải được kiểm tra. Hàm này được gọi là chạy trong "Linear time - thời gian tuyến tính" bởi vì tốc độ của nó phụ thuộc vào kích thước input. Nói một cách khác thì độ hiệu quả của thuật toán giảm đi khi kích thước của input tăng theo số n.

Độ phức tạp theo hàm số log - O(log n)
Kỹ thuật tiếp theo để chúng ta tiến đển xử lý bài toán này là tìm kiếm nhị phân. Với phương pháp này chúng ta sử dụng các hiểu biết về dữ liệu để giúp chúng ta giảm được vùng tìm kiếm.
Ý tưởng: Dùng tính chất của cây nhị phân tìm kiếm là nút con có giá trị nhỏ hơn nút cha thì nằm bên trái, nút con có giá trị lớn hơn nút cha thì nằm bên phải để thu hẹp vùng tìm kiếm.

//Tìm kiếm nhị phân
func binarySearch(key: Int, imin: Int, imax: Int) { 

    // tìm giá trị ở vị trí giữa của mảng
    var midIndex : Double = round(Double((imin + imax) / 2))
    var midNumber = numberList[Int(midIndex)] 

    //Sử dụng đệ quy để giảm vùng tìm kiếm
    if  (midNumber > key) {
        binarySearch(key, imin, Int(midIndex) - 1)
    }
    else if (midNumber < key) {
         binarySearch(key, Int(midIndex) + 1, imax)
    }
    else {
         let results = "value \(key) found.."
    }
} 

Việc sử dụng hiểu biết về cấu trúc dữ liệu giúp chúng ta loại bỏ được rất nhiều phần tử không phải xét. Đây là một mảng đã được sắp xếp theo thứ tự nhất định, nếu chúng ta tìm giá trị ở vị trí thứ 8 thì nó không thể được tìm thấy trong khoảng vị trí từ 0-7.
Nhìn chung các thuật toán có thời gian chạy theo hàm logarit "logarithmic time" - O(log n) là các thuật toán mà có độ hiệu quả tăng dần khi kích thước input tăng tới n.
Sau đây là bảng hiệu suất của các giải thuật tìm kiếm đã nêu

Và dưới đây là đồ thị biểu diễn độ phức tạp thuật toán khi tăng kích thước đầu vào.

Trên đây mình đã giới thiệu với các bạn về Độ phức tạp của thuật toán - Big O Notation mọi ý kiến thắc mắc xin vui lòng để lại comment hoặc gửi vào địa chỉ email của mình.