Video học lập trình mỗi ngày

Nếu như ở những bài viết khác thì chúng ta có thể bắt tay vào bài viết nhanh nhất có thể luôn. Nhưng ở khía cạnh Cấu trúc dữ liệu và thuật toán thì có lẽ tôi luôn có đôi lời, vì những lý bỏ cuộc khi học thuật toán ở bài viết trước.

Cấu trúc dữ liệu và giải thuật - khó thật sự

Có những khoá học oang oang rằng "Học Cấu trúc dữ liệu và thuật toán trong vòng 6 tháng". Đó là không trung thực, vì trong vòng 6 tháng bạn được những gì? Chứ học 1 tháng cũng là học vậy. Ở đây tôi không dám chắc, tôi có thể giúp bạn nắm chắc về thuật toán hay không nhưng tôi chắc chắc sẽ giúp bạn tìm được câu hỏi "Học thuật toán để làm gì?".  Câu trả lời ở bài viết trước rồi, ở đó tôi đã nêu "Những điểm lợi thế vượt xa người khác khi học Cấu trúc dữ liệu và thuật toán" . Ở đây tôi không nhắc lại nữa. 

Khi tôi bắt đầu tìm hiểu lại và trình bày cho bạn về series "Thuật toán và giải thuật" thì tôi nghĩ nó sẽ giảm dần theo thời gian về số lượng đọc. Nhưng quả là bất ngờ, tôi đã dự đoán sai. Thông kê cho thấy, bài đầu tiên có số lượng đọc 1k2 views, nhưng bài thứ hai về chủ đề này lên tới 2k1 views. Điều đó có nghĩa rằng tư duy của bạn ở thế hệ này khác xa chúng tôi. Thật ngưỡng mộ. Và đây để tiếp theo series này, chúng ta sẽ phân tích 2 độ phức tạp trong Cấu trúc dữ liệu và thuật toán . 

Độ phức tạp của thuật toán cấu trúc dữ liệu và giải thuật thì chúng ta chỉ cần tập trung vào hai khía cạnh cụ thể đó là thời gian và không gian. Càng về cuối thì càng khó, chính vì như vậy số ít chỉ ở lại và tiếp tục con đường chinh phục cấu trúc dữ liệu và giải thuật. Ở trong bài viết trước tôi có nói những lý do từ bỏ học về cấu trúc dữ liệu và thuật toán, bởi vì càng ngày nó càng khó. 

Thuật toán và cấu trúc dữ liệu mang một vẻ đẹp tiềm ẩn, bởi nó tiềm ẩn cho nên ít được ai khai phá đến. Và hôm nay, chúng ta cũng kiên nhẫn đi tiếp khám phá độ phức tạp của thuật toán cấu trúc dữ liệu và giải thuật. Trước khi bắt đầu tìm hiểu, trước tiên chúng ta phải hiểu các khái niệm về độ phức tạp về thời gian và độ phức tạp về không gian, và mức độ của chúng cùng nhau xác định chất lượng của một đoạn code.

Cách xác định thời gian thực hiện giải thuật - Độ phức tạp về thời gian

Độ phức tạp về thời gian đó chính là cách xác định thời gian thực hiện giải thuật. Độ phức tạp về thời gian của một thuật toán phản ánh thời gian cần thiết để thực hiện chương trình chạy từ đầu đến cuối. Độ phức tạp về thời gian của thuật toán là số lượng (tần suất) hay những ai đã từng thấy O(n) thực hiện lặp lại thao tác cơ bản trong thuật toán. Hay có bài tập dạng như tính độ phức tạp của vòng lặp... 

Ví dụ: Không có câu lệnh lặp nào trong chương trình của bạn thì , được ký hiệu là O(1), còn được gọi là thứ tự không đổi. Chỉ có một chu kỳ, tần suất thực hiện của hoạt động cơ bản của thuật toán tăng tuyến tính với thang đo n, được ký hiệu là O(n), còn gọi là bậc tuyến tính. 

Để hình dung, bạn có thể xem qua hình ảnh này, nên ngắm nó lâu một cách có thể. 

Cụ thể trên hình:

• O(1): Độ phức tạp không đổi: Độ phức tạp không đổi 
• O(log n): Logarithmic Complexity: Độ phức tạp logarit 
• O(n): Độ phức tạp tuyến tính: Độ phức tạp thời gian tuyến tính 
• O(n^2): N square Complexity Square 
• O(n^3): N bình phương Độ phức tạp 
• O(2^n): Chỉ số tăng trưởng theo cấp số nhân

Độ phức tạp về không gian

Sẽ không có nhiều tài liệu trình bày về khía cạnh này, vì nó bao trùm nhiều yếu tố. Nhưng cụ thể ở đây, độ phức tạp không gian của một chương trình đề cập đến dung lượng bộ nhớ cần thiết để chạy một chương trình. Sử dụng độ phức tạp về không gian của chương trình, chúng ta có thể ước lượng trước dung lượng bộ nhớ mà chương trình cần để chạy cho thuật toán này là bao nhiêu? 

Bạn có thể biết or không biết thì tôi cũng nói thêm rằng khi một chương trình được thực thi, ngoài không gian lưu trữ và các lệnh, hằng số, biến và dữ liệu đầu vào được sử dụng bởi chính nó, nó cũng cần một số đơn vị công việc để thao tác dữ liệu và không gian bổ trợ để lưu trữ một số thông tin cần thiết cho các tính toán thực tế trên đó nữa. Chính vì vậy nó rất nhiều yếu tố. Nhưng ở đây bạn chỉ chú ý đến bộ nhớ khi thực hiện một thuật toán thôi nhé.

Các loại cấu trúc dữ liệu

Tôi tin rằng mọi người đều quen thuộc với thuật ngữ cấu trúc dữ liệu. Bạn có thể đã nghe nó trong nhiều tình huống, nhưng bạn đã bao giờ xem "cấu trúc dữ liệu" là gì chưa? .... Tôi dừng lại tại đây, không phải là không viết được hay một lý do gì? Lý do duy nhất là, các bạn nên học nó từ từ... từ từ... Từ từ.... Các bạn có thể đọc lại 2 phần trước tại link dưới đây:

Điểm lợi thế khi học cấu trúc dữ liệu và thuật toán - Phần 2

Những lý do sinh viên từ bỏ môn học này - Phần 1