Tản mạn về Big O

Hi mọi người, mình là Hiếu, 1 developer cùi "bép" ở 1 công ty startup nọ. Mình rất đam mê giải thuật ( nhưng mình khá cùi ) nên mình đã làm khá nhiều dạng bài. Khi vừa bắt đầu tập tành, mình lúc nào cũng thoả mãn với việc mình giải ra 1 bài toán với tư duy logic ( nghe khá nguy hiểm ), nhưng vào lúc đó mình luôn luôn chỉ code 1 cách mù quáng, code cho ra.

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

Big O là gì ?

Imtermet và chim bồ câu:

Big(O) không dùng để làm công thức tính thời gian chạy

Máy tính của bạn là siêu máy tính của IBM hay là cái máy tính được sản xuất từ đời Tống, thì sẽ có những tốc độ xử lý khác nhau.Bạn code bằng ngôn ngữ gì ? Vì mỗi ngôn ngữ có những cơ chế thông dịch hoặc phiên dịch khác nhau, nên nó sẽ cho ra những hiệu suất khác nhau.Space complexity là độ phức tạp bộ nhớ.Nhiều nhiều lắm kể mệt quá

Best Case, Worst Case

Bạn sử dụng Facebook tìm 1 group random nào đó và đi nhắn tin cho từng người trong danh sách đó để hỏi họ có phải developer không để còn mà tuyển. Nếu đúng hoặc không bạn lại tiếp tục hỏi người đó để xem họ có biết thêm ai khác không, và tiếp tục nhắn cho những người đó. Vậy mỗi khi hỏi 1 người xong bạn sẽ lại nhận thêm 1 list dài những người khác. Vậy độ phức tạp ở đây là O(N^2) phải không :worried:.Vẫn tìm người trong group nào đó như trên. Nhưng lần này bạn hỏi họ có phải developer không Yes/No và không hỏi thêm những thông tin khác. Có thể bạn sẽ tìm ra 1 vài người ngay trong những người đầu tiên, có thể không. Làm vậy có nghĩa là bạn phải chạy tuần tự từ người đầu tiên tới người cuối cùng của nhóm phải hông :sleepy:. Vậy độ phức tạp ở đây là O(N).Lần này bạn sử dụng Linkedin để sử dụng chức năng search filter của nó và tìm kiếm developer. Hihi giờ sẽ ra 1 list gồm những anh toàn là developer cao to đen hôi nhé. rồi lại dùng filter để lọc ra các anh Java developer lọc nhiều lần theo yêu cầu bạn đưa ra. Như thế mỗi lần sử dụng bộ lọc nó sẽ giúp bạn giảm đi 1 thành phần đáng kể những người không phù hợp. Trường hợp này độ phức tạp sẽ là O(logn)Big(O): là trường hợp tệ nhất của thuật toán :cry:Big Omega (Ω): Cái này ngon lắm. Nó là trường hợp tốt nhất. Ví dụ như tìm số điện thoại trong danh bạ thì người cần tìm sẽ là người đầu tiên chẳng hạn.Big Theta (Θ): Big Theta thì bao gồm luôn cả 2 thằng kia :confused:

Quy tắc bỏ hằng số

Quy tắc lấy công, nhân

function print(arr){
    for(let i = 0; i < arr.length; i++) // O(N)
        console.log(arrDup[i]);
    if(arr.length > 3) // O(1)
        console.log("?? :D ??);      
}

Quy tắc lấy max

    function printAllDuplicate(arr){
        let arrDup = [];
        for(let i = 0; i < arr.length-1; i++)
            for(let j = i + 1; j < arr.length; j++)
                if(arr[i] == arr[j])
                    arrDup.push(arr[i]);
        for(let i = 0; i < arrDup.length; i++)
            console.log(arrDup[i]);
    }

Kết