Tản mạn về BIG O trong môn Giải thuật & Cấu trúc dữ liệu
Giải thuật & cấu trúc dữ liệu là một trong những môn "củ khoai" nhất của chứng chỉ 3. Mặc dù các bài assignment mình làm điểm khá OK, tuy nhiên khi thi mình cũng không chịu nổi nhiệt và điểm khá thấp.
Mình cũng vừa trải qua một kì xin việc khó khăn, và ở rất nhiều nơi họ tuyển đầu vào là những bài toán giải thuật mà ta hay thấy trên Hackerrank, Leetcode. Do đó, dưới góc độ của những người học lập trình như chúng ta mà nói, việc luyện tập giải thuật hằng ngày là một điều cần thiết.
Trong phần giải thuật có một khái niệm quan trọng nhưng mình cũng tốn khá nhiều thời gian để lĩnh hội, đó là Big O Notation (đơn vị đánh giá mức độ hiệu quả của một thuật toán theo thời gian). Hôm nay mình muốn chia sẽ kiến thức này ngắn gọn và gần gũi nhất cho dễ hiểu.
(Disclaimer: đây là bài viết dưới góc độ cá nhân còn thiển cận của mình, các xters hay mentors thấy sai chỗ nào comment sửa giúp nhé).
ĐÁNH GIÁ MỨC ĐỘ HIỆU QUẢ CỦA MỘT THUẬT TOÁN
Việc đầu tiên cần nhận thức rõ trong thuật toán là, làm sao để biết thuật toán A tốt/ hiệu quả hơn thuật toán B?
Thông thường có 2 tiêu chí chính:
-
Một là Time Complexity: tức là đánh giá thuật toán đó chạy nhanh hay chậm.
-
Hai là Space Complexity: đánh giá thuật toán đó tiêu tốn nhiều hay ít bộ nhớ.
Trong bài viết này mình sẽ đi sâu vào phần Time Complexity hơn, cá nhân mình thấy đa phần người ta cũng quan tâm nó nhiều hơn là Space Complexity.
Đơn vị đo thời gian là giây, là phút. Tuy nhiên việc đánh giá một thuật toán bằng cách bấm đồng hồ như vậy thì không thể đánh giá đầy đủ được. Vì một thuật toán chạy trên CPU xịn sẽ có tốc độ nhanh hơn ở một CPU yếu hơn, do đó nếu dùng thời gian để đo đạc thì ta phải chọn một phần cứng điển hình làm quy chiếu, điều đó thì vô lý quá.
Do đó, người ta dùng tới khái niệm được gọi là Big O để làm đơn vị đo chung cho mức độ hiệu quả của một thuật toán về phương diện thời gian.
Với cách tiếp cận này, như đã nói ở trên ta sẽ không đo thề gian về phương diện vật lý, mà về phương diện thứ tự của lần chạy thuật toán đó tương đối với kích thước của dữ liệu đầu vào.
Thông thường, có những giá trị chính của Big O Notation là 1, n, n^2 (n bình phương) và log(n) (các bạn chú ý trong tin học thì lôgarit là cơ số 2 chứ không phải 10 như trong toán học nhé!).
Người ta sẽ viết như sau O(1), O(n), O(n^2), O(log n):
-
O(1): level thần thánh! Nếu bạn viết được một thuật toán với big O notation này bạn có thể sánh ngang các vị thánh giải thuật, đạt tới giới hạn cực hạn về mặt hiệu quả về phương diện thời gian rồi.
-
O(log n): level yêu thích của mọi người.
-
O(n): level chấp nhận được, nhưng cũng chưa ngon lắm.
-
O(n^2): level ác quỷ, nếu có thể thì cố gắng cải thiện nó xuống level thấp hơn.
LÀM CÁCH NÀO ĐỂ ĐO TIME COMPLEXITY BẰNG BIG O?
Bằng cách đếm các phép tính thôi ạ! Giả sử bạn có một mảng có n chữ số nguyên, để cộng tổng thì ta sẽ dùng vòng lập như sau (viết bằng mã giả):
def int sumTotal(int[] array)
int sum = 0
for i = 0 to array length – 1, I++
sum+=array[i]
end for
return sum
Như vậy thì ta có tổng cộng bao nhiêu phép tính?
-
1 phép tính cho việc set sum = 0
-
n phép tính cho việc cộng dồn với n phần tử cho sum
-
1 phép tính trả kết quả
Vậy ta có big O của thuật toán này là O(n + 2).
Tuy nhiên nếu ta lấy n là 1000 phần tử thì 2 phần +2 trong big O sẽ không có ý nghĩa gì cả so với độ lớn của n. Do đó, người ta sẽ loại bỏ phần + 2 đó, và nói chung, người ta sẽ loại bỏ các hằng số trong big O khi đo đạc.
Do đó time complexity của thuật toán này là O(n).
TẠM KẾT
Đây là khái niệm vỡ lòng cho phần nhập môn môn học này, mình nghĩ khi phỏng vấn xin việc sẽ đụng tới nhiều. Cộng đồng lập trình viên trên thế giới nếu muốn nhắm vào các công ty FAANG (Facebook, Apple, Amazon, Netflix) họ cũng nói phải ôn luyện mỗi ngày :’( Chúc các bạn có một môn học thành công, đừng thi điểm thấp như mình :’)
Học viên Hồ Nhật Minh
|
Anh Hồ Nhật Minh chọn học FUNiX vì giá trị chia sẻ kiến thức trong cộng đồng công nghệ, hình thức học trực tuyến linh động. “Lập trình đang là một ngôn ngữ của thời đại, bản thân sống ở thời đại này mà không biết về lập trình có nghĩa mình đang bị thời đại mới bỏ lại phía sau”, anh Hồ Nhật Minh chia sẻ. |
ĐĂNG KÝ TƯ VẤN HỌC LẬP TRÌNH TẠI FUNiX
Bài liên quan
Bài liên quan
Đừng chờ đến khi thất nghiệp mới học kỹ năng mới - Báo động từ thị trường lao động 2025
Cuối năm là lúc các hội nhóm trở nên dày đặc bài đăng kiểu: “Mình mới nhận quyết định sa thải, giờ nên học gì để ổn định lại?”, “Thất nghiệp 3–6 tháng rồi, học Data Analytics có ổn không?”,...
Khóa học Software Engineering cho Người đi làm tại FUNiX
Mục lục Vì sao người đi làm lựa chọn Software Engineering để chuyển nghề sang IT? Phương pháp học tại FUNiX dành riêng cho người đi làm Yêu cầu đầu vào và ai phù hợp với khóa học? Lộ trình...
Khóa học Software Engineering cho học sinh tại FUNiX
Khóa học lập trình cho học sinh tại FUNiX giúp xây nền tảng công nghệ sớm, lộ trình bài bản, học online linh hoạt và mở rộng cơ hội nghề nghiệp. Mục lục Vì sao nên học khóa Software Engineering...
Khóa học Software Engineering cho Học sinh tại FUNiX: Lộ trình, kỹ năng & cơ hội nghề nghiệp
Khóa học Software Engineering cho học sinh tại FUNiX cung cấp một lộ trình toàn diện từ nền tảng lập trình cơ bản đến kỹ năng phần mềm chuyên sâu. Học sinh cấp 3 sẽ tiếp cận với các môn...
Khóa học Web Full-Stack tại FUNiX: Lộ trình, kỹ năng & cơ hội nghề nghiệp
Lập trình web là một trong những kỹ năng được săn đón nhất trong kỷ nguyên số. Dù ở doanh nghiệp lớn, startup hay làm việc tự do, khả năng xây dựng website và ứng dụng web sẽ giúp bạn...
Khóa học Tester tại FUNiX: Lộ trình, kỹ năng & cơ hội nghề nghiệp
Khóa học Tester tại FUNiX cung cấp nền tảng toàn diện cho người mới bắt đầu muốn bước chân vào lĩnh vực kiểm thử phần mềm. Trong 20 tuần, học viên sẽ nắm vững từ kỹ năng viết test case,...
Khóa học Business Analyst tại FUNiX: Lộ trình, kỹ năng & cơ hội nghề nghiệp
Khóa học Business Analysis FUNiX (Business Analyst) là chương trình dành cho người mong muốn gia nhập ngành CNTT với vai trò cầu nối giữa kinh doanh và công nghệ. Khóa học cung cấp lộ trình 7 tháng, từ cơ...
Khóa học Data Analysis tại FUNiX: Lộ trình, kỹ năng & cơ hội nghề nghiệp
Khóa học Data Analysis tại FUNiX trang bị cho học viên kỹ năng phân tích dữ liệu toàn diện – từ Excel, SQL, Power BI đến Python, scikit-learn. Người học sẽ làm chủ quy trình xử lý dữ liệu, trực...
Đăng ký nhận bản tin
×
×
Bình luận (0
)