What is bigO notation?

What is bigO notation?

Image from: bigocheatsheet.com

BigO notation is simplified analysis of an algorithm's efficiency.

Nói đơn giản BigO cho chúng ta biết độ phức tạp của thật toán với kích thước đầu vào là n. Nó cung cấp cho chúng ta một cách trừu tượng hóa hiệu quả của các thuật toán. Chúng ta không quan tâm tới thời gian thuật toán thật sự chạy trên máy vì nó phụ thuộc vào phần cứng và nhiều thứ khác, chúng ta trừu tượng nó bằng các quy tắc mà bigO đặt ra.

Trong khi phân tích hiệu quả của một thuật toán ta quan tâm đến ba trường hợp:

  • Xấu nhất
  • Tốt nhất
  • Trung bình

Nhưng thật ra chúng ta chỉ quan tâm đến trường hợp xấu nhất

  1. Quy tắc đầu tiên
    Bỏ giá trị hằng số: 6n -> O(n)
    Tức là chúng ta sẽ chỉ quan tâm đến n là bậc mấy chứ hằng số không quan tâm
  2. Quy tắc thứ hai: chỉ lấy bậc cao nhất trong thuật toán:
    O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2^n)<O(n!)
    Đây là bảng thể hiện tốc độ:
    bigO.png Nguồn: bigocheatsheet.com

Đến với các ví dụ:
Đầu tiên là O(1)

X=1+(2 *3);//mọi người hay gọi là "big oh of one" ký hiệu là O(1)
x=1+(2*3);
y=4-5;
print x+y;
/*
total time=O(1)+O(1)+O(1)=O(1)
                   3*O(1)
*/

Tiếp theo là linear time:

for x in range (0, n):
   print x; // O(1)
//=> N*O(1)=O(N)

Nếu chúng ta kết hợp giữa O(1 ) và O(n) thì sẽ là:

x=1+(2*3);//O(1)
for x in range (0, n):
   print x; // O(1)
//=>total time=O(1)+O(N)=O(N)

Tiếp theo đến với ví dụ về quadratic time:

for x in range (0, n):
   for y in range (0, n):
       printxy; // O(1)
//=> O(n²)

Nếu kết hợp với O(1) và O(n) thì sao?

x=1+(2*3);//O(1)
for x in range (0, n):
   print x; // O(1)
for x in range (0, n):
   for y in range (0, n):
       printxy; // O(1)
=>total time=O(1)+O(N)+O(n²)=O(n²)

Đấy, chúng ta chỉ cần quan tâm đến cái lớn nhất thôi.
Để lấy thêm một ví dụ thì ta xem xét cái ông If đi:

if x>0:
    // O(1)
else if x<O:
   // O(logn)
else:
    // O(n²)

Đúng rồi, cứ thằng lớn nhất mà tính, ta hết O(n²)

Thôi ví dụ vậy được rồi, túm lại thì chúng ta cần nhớ thế này:

  1. Chỉ lấy độ phức tạp lớn nhất làm kết quả
  2. Không cần quan tâm đến hằng số.
  3. Cũng nên để ý đến trường hợp tốt nhất và trung bình trong khi lựa chọn các thuật toán.

Hết rồi... see ya!

À quên, học mấy cái này ở video: youtu.be/__vX2sjlpXU
Muốn học thêm về thuật toán thì có một số nơi:
Đây là nơi đầu tiên mình biết :))
vnoi.info/wiki/Home
Đây cũng là một trang hay:
giaithuatlaptrinh.com/?page_id=4