BigO là gì trong thuật toán ? 1 công cụ quan trọng của lập trình viên giỏi

Trong khoa học máy tính nói chung và phần mềm nói riêng, để lập trình tạo ra những dòng code chất lương, chúng ta phải đi từ những khái niệm cơ bản nhất. Và BigO là khái niệm cần phải biết trước tiên khi bước vào từng cấu trúc giải thuật và dữ liệu!

 

 

BigO là gì ?

 

 

Là độ phức tạp của thuật toán, dùng để đánh giá, phân tích thuật toán có tối ưu hay không ? dựa vào giá trị gia tăng của số lượng biến đầu vào

 

 

Các dạng BigO phổ biến

 

 

- O(n): Linear time

 

 

- O(1): Constant time, là hằng số thời gian không thay đổi theo lượng input đầu vàoVD: có 100000 input item và 1 input item thì kết quả của thuật toán không khác nhau

 

 

- O(logN): Mỗi lần lặp sẽ giảm đi 1/2 thời gian

 

 

- O (n2): 2 vòng lặp lồng nhau

 

 

Sự khác nhau giữa BigO, Big Omega, BigTheta notations ?

 

 

Dưới là 2 link mình đã tìm kiếm có giải thích kỹ lưỡng về sự khác nhau của 3 khái niệmhttps://www.quora.com/What-is-the-difference-between-big-oh-big-omega-and-big-theta-notations

 

 

chatgpt.com/share/67511669-c008-8013-9f74-e212c9eda9d2

 

 

Khá khó giải thích bằng lời, nhưng để cho dễ tiếp cận mình sẽ giải thích sự khác nhau như sau:

 

 

- BigO: Trường hợp xấu nhất

 

 

- Big Omega: Trường hợp tốt nhất (best case)

 

 

- Big Theta: Trường hợp xấu nhất, tốt nhất, trung bình

 

 

Ví dụ: về thuật toán linear search

 

 

function linearSearch(arr, target) {

for (let i = 0; i

 

 

-

 

 

- Worst-case: We have to check all elements.

 

 

- Time complexity: O(n).

 

 

-

 

 

- Best-case: We find it in 1 operation.

trannhatsang.com/bigo-la-gi-trong-thuat-toan-1-cong-cu-qu...

Done