Hi các bạn! DL again. Để đảm bảo Series thực hiện một cách trơn tru thì bài viết này giúp các bạn nắm bắt rõ một số vấn đề liên quan đến giải thuật và cấu trúc dữ liệu và trong các bài viết khác sẽ không phải nhắc lại nhiều lần nữa :v
- Kiểu dữ liệu nguyên thủy (primitve data type): Là những dữ liệu được định nghĩa bởi hệ thống. Như: float, int, double (C++, Java)
- Kiểu dữ liệu do người dùng tự định nghĩa (user defined data types): Là các kiểu dữ liệu do người dùng xây dựng bằng cách tổ hợp các kiểu dữ liệu nguyên thủy. Như: kiểu mảng (array), kiểu cấu trúc (struct)
int a, b, c; //Khai báo với kiểu nguyên thủy
int arr[100]; //Khai báo với kiểu mảng
struct data //Khai báo với kiểu struct
{
int x;
float y;
};
- Cấu trúc dữ liệu tuyến tính: mảng (array), ngăn xếp (stack), danh sách liên kết (link list),... Việc truy cập các phần tử được thực hiện một cách tuần tự.
- Cấu trúc dữ liệu không tuyến tính: cây (tree), đồ thị (graph),... Các phần tử được tổ chức và truy cập không tuần tự.
- Cấu trúc dữ liệu trừu tượng:
- Là phương pháp kết hợp các phép toán trên dữ liệu cụ thể của cấu trúc dữ liệu
- Độ phức tạp của thuật toán:
Một cách dễ hiểu thì đây là số phép tính toán trong một giải thuật (1s ~ 2*10^-8 phép tính). Vì rất khó có thể xác định chính xác độ phức tạp vậy nên ta thường xấp xỉ thuật toán với một phiếm hàm
O(g(x))
for (int i=1; i<=c; i++)
{
// O(1)
}
O(n)
for (int i=1; i<=n; i=i+c)
{
// O(1)
}
O(n^2)
for (int i=1; i<=n; i=i+c)
{
for (int j=1; j<=n; j=j+c)
{
// O(1)
}
}
O(log(n))
for (int i=1; i<=n; i=i*c)
{
// O(1)
}
O(log(log(n)))
for (int i=1; i<=n; i*=pow(i,c))
{
// O(1)
}
 |
| độ tăng của các hàm |
Như vậy qua bài viết trên đây. Mình mong rằng các bạn có thể hiểu qua phần nào về những vấn đề liên quan đến thuật toán. Bài viết sau ta sẽ đi vào cụ thể chi tiết các thuật toán và cách sử dụng nó.
Share this
