Phân tích thuật toán: Tiệm cận (Asymptotic notation)

#1

Ở bài này, mình sẽ nói về độ phức tạp của một thuật toán. Do mình cũng mới nghiên cứu để viết bài này nên chưa thể hiểu rõ được, nhưng mình sẽ cố viết một cách dễ hiểu, có thể sẽ có sai sót, mong mọi người thông cảm và góp ý. Mọi người ráng đọc vậy, hơi dài

  • Khi phân tích một thuật toán, một trong những vấn đề quan trọng nhất mà ta quan tâm là thời gian chạy (running time). Thời gian chạy của một thuật toán dựa trên nhiều yếu tố, ví dụ như tốc độ của máy tính, ngôn ngữ lập trình (C/C++, Python, blah blah blah, không phải tiếng Anh tiếng Miên gì nhá), compiler và blah blah blah, nói chung là nhiều yếu tố.

=> Vậy tiệm cận (Asymptotic) là một khái niệm giúp ta ước lượng được thời gian chạy (running time) của một thuật toán, thông qua số chỉ thị (machine instructions) hay gọi đơn giản là số bước.

Bây giờ hãy xem xét (chữ đầu là “xờ” nhé, chuyển thành “sờ” là có chuyện ngay) kỹ về thời gian chạy (đây là lần cuối mình mở ngoặc và thêm chữ running time). Chúng ta phải nghĩ về 2 thứ

Ta phải xác định, với kích thước của input (dữ liệu nhập), thuật toán sẽ chạy bao lâu. Ví dụ như số bước thực hiện tối đa của Binary Search hay Linear Search tăng theo chiều dài của dãy số (mảng). Vì thế ta nghĩ về thời gian chạy của một thuật toán như là một hàm về kích thước của dữ liệu nhập .

Ví dụ như ta có hàm F(n) = 9n<sup>2</sup> + 6n + 9 với n là kích thước *tối đa của dữ liệu nhập thì hàm F(n) chính là running time

  • Thứ 2, ta tập trung vào ý nghĩ: khi kích thước input tăng thì thì tốc độ của thuật toán sẽ tăng nhanh như thế nào. Hay như ví dụ trên: Khi n (kích thước tối đa của input) tăng thì giá trị của hàm F(n) sẽ bao như thế nào (ví dụ n tăng 2 thì nguyên hàm đó tăng 4, đại loại thế) . Và chúng ta gọi nó là Tỷ suất gia tăng, hay gọi cho đơn giản là rate of growth (mọi người luyện tiếng Anh chút vậy).

  • Để dễ quản lý, ta lược bỏ các phần ít quan trọng trong cái hàm đi. Ví dụ như với kích thước input là n, ta tốn 9n2 + 6n + 9 bước thì phần n2 lớn hơn phần 6n + 9 (chú ý là đến 1 giá trị n nào đó thì nó mới lớn hơn, và từ đó trở đi sẽ luôn lớn hơn nữa. Mọi người học lại sách toán 9 để vẽ đồ thị sẽ rõ ).

  • Vì thế ta bỏ phần hệ số (số 9) cùng phần 6n + 9 đi, chỉ giữ lại n2. Và ta nói rằng Running time của thuật toán này là n2

Và theo kinh nghiệm thì ta luôn lấy biến có bậc cao nhất làm running time. Và khi ta bỏ đi phần hệ số cũng như phần ít quan trọng hơn kia, thì lúc này, chúng ta có thể làm việc với chúng qua một thứ gọi là: Asymptotic notation, hay là các ký hiệu tiệm cận (cái tên tiếng Việt nghe không lọt lỗ tai)

Asymptotic notation gồm các dạng:

  • Big-Theta (Big-θ):

  • Big-O: thường được viết là O()

  • Big-Omega (Big-Ω):

Chú ý:

  • Do diễn đàn không hỗ trợ viết các notation này (mà có thì cũng chẳng mấy ai viết đâu, tốn thời gian lắm) nên sau này khi dùng đến chúng, hãy viết như mình viết ở trên.
  • Giữa 2 chữ có dấu gạch nối nhé (Big-O, Big-Theta, Big-Omega)
  • Sau các notation trên đều có đóng mở ngoặc đơn, bên trong là số liệu (ví dụ: O(n) )

Về các loại notation trên, mình sẽ nghiên cứu và viết về chúng sau. Cám ơn mọi người

Chết, quên ghi nguồn:

8 Likes
#3

Anh @Gio chắc nhận xét chuẩn hơn, anh còn chưa đọc kĩ tài liệu về cái này, chỉ góp ý em là viết tút mở đóng ngoặc ít ít thôi , đọc kiểu này nó cứ sao sao á :blush:

#4

Quá cao siêu đối với mình, mấy cái thuật toán mình bỏ hết. Chẳng giữ gì trong đầu.

1 Like
#5

Cho người đọc bớt căng thẳng anh ơi, đọc chữ trên xuống dưới cũng choáng lắm chứ bộ

1 Like
#6

:+1: anh cũng thích đọc những bài viết mang tính thoải mái nhẹ nhàng hơn mấy bài viết như sách giáo khoa :smile:, nhưng đôi lúc không “khô” một tí là không được, đặc biệt trong phần thuật toán :blush: , anh cũng đang đọc tài liệu về phần này để khi nào thử viết một bài về cách phân tích thuật toán :blush:

1 Like
#7

Tóm tắt lại:

  • Big-O , Omega, Theta đều là lim n-> Infinity
  • Big-O của f(n) là g(n) khi: f(n)<=C * g(n)
  • Big-Omega của f(n) là g(n) khi: f(n)>= C* g(n)
  • Big-Theta của f(n) là g(n) khi: C1 * g(n) <=f(n) <= C2* g(n)

:dizzy:

2 Likes
#8

Wow đọc tài liệu một lúc thì rút ra một điều rằng: độ phức tạp là để đánh giá độ tốt xấu của thuật toán, và đánh giá bằng cách tìm một hàm càng xát sự tăng thời gian tính toán (hoặc số lần truy cập bộ nhớ,…) của thuật toán càng tốt để làm sao độ tăng của hàm số đó luôn không nhỏ hơn độ tăng của thuật toán.

Hàm cần tìm đó thường để ở dạng đơn giản nhất để dễ so sánh , và các kí tự O, ô mê ga, tê ta là để đảm bảo độ đơn giản đó, nếu lấy thằng O so sánh không được thì lấy thằng Ô mê ga, không được nữa thì lấy thằng tê ta, càng thằng cấp cao thì càng phức tạp nhưng lại càng sát với thuật toán.

Không biết hiểu vậy đã ổn chưa nhỉ :smiley: @nhatlonggunz @Gio

1 Like
#9

Anh @ltd ơi, sao chỗ này nó hiển thị ra là 2 chứ nó không đưa số 2 lên trên đầu số 9 vậy ?
Ở dưới em viết vậy vẫn được mà.

#10

Anh @nhatlonggunz có thể update lại 2 picture trong topic không ?

#11

Update lại r nha Minh :smiley:
Có thêm ký tự đặc biệt luôn r đó.

2 Likes
#12

cho em hỏi là độ dài xâu input của thuật toán kiểm tra số chính phương là bao nhiêu ạ

#13

Là số chữ số của số đó.

Nếu không phải thì bạn hãy đặt lại câu hỏi.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?