in General

Giải mã BigO trong lập trình

Nhiều người có lẽ không lạ lẫm gì lắm về từ khóa “BigO” trong giới lập trình rồi nhỉ? Với mình thì nó lại là cái gì đó tương đối khó nắm bắt =))). Một phần là do ngày trước đi học không được dạy (hoặc có thể có nhưng không nhớ là đã được dạy), một phần là mình cũng hơi dốt toán nữa =))). Nên hôm nay quyết viết 1 bài để tự dạy cho chính bản thân, cũng như là giúp các bạn chưa có rõ ràng về BigO có thể nắm được rõ ràng nhất có thể để sau này có đi phỏng vấn cũng không bị hố.

Vậy thì BigO là gì? Trên mạng có rất nhiều rồi nên mình chọn đại 1 cái khái niệm cơ bản nhất thôi:

BigO là chỉ số để đánh giá độ phức tạp của một giải thuật

BigO thường thì hay được dùng để đánh giá lượng thời gian tiêu hao của một giải thuật dựa trên dữ liệu đầu vào

Một số chỉ số phức tạp phổ biến gồm: O(1), O(n), O(logn), O(nlogn), O(n!) v.v… Với một số bạn mà học toán khó vào như mình, thì lúc đầu nhìn đống này thì rõ là chả hiểu gì roài, hầyyy. Chúng ta sẽ cùng đi qua từng đứa 1 xem nó như thế nào nha.

O(1): Đây là thằng gần nhanh nhất

Cùng nhìn qua đoạn code sau để hiểu vì sao nó là số 1

function O_1(array){
  return array[0];
}

Bạn có thể thấy ngay là hàm này chỉ làm 1 việc duy nhất đó là: In ra phần tử “0” của 1 mảng. Nó chả phải làm cái mẹ gì lằng nhằng để ra kết quả cả, bất chấp đầu vào mảng bao nhiêu đi nữa. Vậy nên nó là nhanh cmn nhất. Rất đơn giản phải không nào? =))))

O(n)

Thằng này thì cũng đơn giản hơn tí, là đầu vào bao nhiêu thì tốn bấy nhiêu. Tức đầu vào mà 1000 phần tử thì (có thể) mất thời gian 1000 lần.

function O_n(array){
  foreach(var item in array){
     console.log(item);
  }
}
// hoặc kiểu như này:
function O_n(array){
  for(var i = 0; i < array.length; i++){
   console.log(array[i]); // In ra phần tử thứ i trong mảng
  }
}

Trên đây là 1 dạng worst-case – tình huống tệ nhất (Cũng chả có mấy ai dùng cái này đâu, LOL). Nhưng thời gian thực tế có thể ít hơn với đoạn code sau:

function Seach_O_n(input, target){
  foreach(var value in input){
    if(value === target) return true;
  }
  return false;
}

Có thể thấy phương thức tương đối dễ hiểu, hàm sẽ dừng ngay khi có kết quả phù hợp với yêu cầu đầu vào. Trong trường hợp tệ nhất là không có kết quả phù hợp thì sẽ lặp hết toàn bộ mảng đầu vào và trả về kết quả false như đoạn code trước đó

O(logn)

Ơ ơ … log là cái gì thế ???


.