Cấu trúc dữ liệu với Kotlin: Kiến thức

Sau khi bạn đã có hiểu biết về ngôn ngữ lập trình Kotlin. Giờ là lúc học sâu về cấu trúc dữ liệu & Giải thuật để tăng cường nội công cho quá trình chinh phạt giang hồ.

Let’s go!!!

Cấu trúc dữ liệu là gì?

Tham khảo định nghĩa Wiki Pedia về CTDL.

Mỗi chương trình thực thi đều cần bộ nhớ để lưu trữ các biến.

Cách tổ chức các biến trong chương trình để thuận tiện cho việc cấp phát (allocate), truy cập (access), cập nhật (update) hoặc giải phóng (free / deallocate) bộ nhớ chính là Cấu trúc dữ liệu.

Một số loại Cấu trúc dữ liệu thường được sử dụng trong chương trình: Danh sách liên kết – List; Mảng – Array, Bảng băm – HashTable – HashSet, Stack, Queue ,..

Giải thuật là gì?

Giải thuật là tập hợp các bước xử lý cụ thể để giải quyết 1 vấn đề nhất định.

Trong chương trình máy tính, Giải thuật là cách Lập trình viên tổ chức các Logic sao cho xử lý được vấn đề.

Ví dụ: Giải thuật để xác định 1 số tự nhiên N là số Nguyên tố hay không. Giải thuật để chuyển đổi số La mã sang số tự nhiên và ngược lại. Giải thuật để mã hóa một đoạn text. Giải thuật để giải mã 1 đoạn text. …

Khái niệm Time Complexity, Space Complexity

Để đo mức độ phức tạp cũng như hao tổn tài nguyên của 1 giải thuật, người ta sử dụng 2 khái niệm: Time Complexity, Space Complexity

Time Complexity là chỉ số của sự tăng của thời gian thực thi của một giải thuật khi ta tăng kích thước của dữ liệu đầu vào (input). Nó cung cấp cho chúng ta cái nhìn tổng quát về 1 giải thuật, hiểu được sự tương quan giữa hiệu suất và độ lớn của input.

Space Complexity là 1 chỉ số để đo lường sự tăng của hao tổn bộ nhớ (RAM) khi thay đổi kích thước của dữ liệu đầu vào.

Cả hai chỉ số đều rất quan trọng trong việc thiết kế giải thuật, cần hiểu và nắm rõ để có thể ứng biến tốt trong quá trình phỏng vấn và làm việc.

Time Complexity của 1 số loại Cấu trúc dữ liệu thường dùng