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.

Swift Optionals: Khác biệt giữa "!" và "?"

Như các bạn đã biết, Optionals trong Swift được tạo ra để nhắc nhở lập trình viên luôn luôn phải để ý tới dữ liệu trong biến đó. Sự thiếu vắng dữ liệu trong Optionals value hoặc là bạn sẽ bị crash app, hoặc là bạn sẽ bị lỗi trong quá trình biên dịch. Khai báo biến dạng Optionals thì bạn có 2 cách để làm đó là thêm dấu "?" hoặc dấu "!" sau kiểu dữ liệu ví dụ:

var optionalsValue1 : Int?
var optionalsValue2 : Int!

 Cả 2 cách trên bạn đều đã tạo một optionals value, tuy nhiên 2 cách khai báo này có sự khác nhau. Để hiểu hơn mình cho bạn 1 ví dụ:

var optionalValue1 : Int? = nil
print(optionalsValue1)
//"nil\n"
var optionalValue1 : Int! = nil
print(optionalsValue1)
//fatal error: unexpectedly found nil while unwrapping an Optional value

Trong trường hợp 1, chương trình vẫn chạy, in ra kết quả trong màn hình là "nil\n", còn trường hợp thứ 2 trình biên dịch sẽ báo lỗi.

Giải thích: Khi ta khai báo "?" tức là ta thông báo rằng tôi không chắc chắn rằng khi biến đó được sử dụng thì biến đó đã có dữ liệu hay không. Còn khi bạn khai báo "!" thì bạn đã thông báo rằng bạn chắc chắn rằng khi biến đó được sử dụng biến đó có dữ liệu, nếu lúc biến đó được sử dụng mà dữ liệu trong biến đó là nil thì hoặc là trình biên dịch sẽ báo lỗi, hoặc là khi chạy app của bạn sẽ bị crash khi tác vụ xử lý tới biến đó.