Một số anh em tham gia CodeLearn nhiều khi chạy bài tập bị quá thời gian. Lí do là code của các bạn chạy mất quá nhiều thời gian Show Tại sao thời gian lại quan trọng?
Do đó, các bài tập ở CodeLearn khi đưa ra đều có giới hạn thời gian để người dùng suy nghĩ, lựa chọn giải thuật phù hợp. Đó là thời gian chạy. Vậy độ phức tạp thuật toán là gì, có liên quan gì tới thời gian chạy? 1. Độ phức tạp thuật toán là gì?Về lý thuyết, các bạn có thể tìm theo từ khoá algorithm complexity hoặc đọc ở đây Nói ngắn gọn thì, mỗi một bài toán có giới hạn/kích thước của đầu vào. Độ phức tạp thuật toán là 1 khái niệm/định nghĩa/định lượng tương đối thể hiện số phép toán của giải thuật so với kích thước của đầu vào. Ví dụ cho dễ hiểu:
Và như bạn thấy đó, máy tính của chúng ta có tốc độ là khác nhau. Có thể hiểu là, cùng có 100000 phép tính, thì máy của ông A có thể chạy nhanh hơn máy ông B. Do đó, độ phức tạp giải thuật có thể thể hiện tương đối chính xác thuật toán nào nhanh hay chậm, so với việc đo thời gian chạy trên các máy khác nhau. Có nhiều bạn cũng comment tại sao chạy ở máy ở nhà thì không quá thời gian, lên server thì bị quá. Cũng là cùng lí do như thế. 2. Chọn giải thuật phù hợpNhư giải thích ở trên, độ phức tạp thuật toán có thể hiểu là số phép toán thực hiện của một hàm dựa trên kích thước tối đa của dữ liệu. Độ phức tạp thuật toán (trên cùng 1 máy) có thể hiểu là nó tỉ lệ thuận (1 cách tương đối) với thời gian chạy.
3. Tổng kếtHiểu rõ về khái niệm độ phức tạp thuật toán và cách tính toán độ phức tạp của giải thuật (của mình hay của người khác) bạn sẽ tối ưu thuật toán để đáp ứng thời gian chạy tốt hơn ví dụ như làm ứng dụng của bạn chạy nhanh, thời gian phản hồi cao, ... Do đó, với mỗi bài toán hay yêu cầu cụ thể, hãy xem xét độ lớn của tập dữ liệu mà chọn giải thuật cho phù hợp. Chúc anh em thành công Bài viết theo ý hiểu của mình, cố gắng đơn giản hoá cho anh em, có gì anh em mạnh dạn góp ý nha.
Chào ace, bài này chúng ta sẽ tìm hiểu về Tìm kiếm một phần tử bên trong linked list trong series tự học về cấu trúc dữ liệu và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau. Trong bài học này chúng ta sẽ viết một hàm có chức năng tìm kiếm một key ‘x’ ở bên trong một singly linked list (danh sách liên kết đơn). Hàm này sẽ trả về true nếu x xuất hiện bên trong linked list, và trả về false trong trường hợp ngược lại. bool search(Node *head, int x)Ví dụ, nếu key cần tìm kiếm là 15 và linked list có dạng 14 -> 21 -> 11 -> 30 -> 10, trong trường hợp này hàm search(Node *head, int x) sẽ trả về false. Tuy nhiên, nếu key cần tìm là 14, thì kết quả trả về sẽ là true. 1. Thuật toán sử dụng vòng lặp1. Khởi tạo một con trỏ node, khai báo và khởi tạo một con trỏ current = head 2. Khi con trỏ current vẫn còn chưa NULL thì thực hiện những việc sau: a) Nếu current -> key bằng với key đang được tìm kiếm, thì return true luôn b) Nếu không thì gán current = current -> next và tiếp tục chạy vòng lặp 3. Khi mà con trỏ current đã NULL rồi, mà vẫn chưa tìm thấy key, vậy thì return false Sau đây sẽ là đoạn code cài đặt cái thuật toán tìm kiếm một key cụ thể trong một linked list sử dụng vòng lặp đã nêu ở trên, được viết bằng nhiều ngôn ngữ lập trình: CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C++ C Java Python C# C // Iterative C program to search an element in linked list #include<stdio.h> #include<stdlib.h> #include<stdbool.h> /* Link list node */ struct Node { int key; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(struct Node** head_ref, int new_key) { /* allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); /* put in the key */ new_node->key = new_key; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search(struct Node* head, int x) { struct Node* current = head; // Initialize current while (current != NULL) { if (current->key == x) return true; current = current->next; } return false; } /* Driver program to test count function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); search(head, 21)? printf("Yes") : printf("No"); return 0; }C++ // Iterative C++ program to search // an element in linked list #include <bits/stdc++.h> using namespace std; /* Link list node */ class Node { public: int key; Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(Node** head_ref, int new_key) { /* allocate node */ Node* new_node = new Node(); /* put in the key */ new_node->key = new_key; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search(Node* head, int x) { Node* current = head; // Initialize current while (current != NULL) { if (current->key == x) return true; current = current->next; } return false; } /* Driver program to test count function*/ int main() { /* Start with the empty list */ Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); search(head, 21)? cout<<"Yes" : cout<<"No"; return 0; }Java // Iterative Java program to search an element // in linked list //Node class class Node { int data; Node next; Node(int d) { data = d; next = null; } } //Linked list class class LinkedList { Node head; //Head of list //Inserts a new node at the front of the list public void push(int new_data) { //Allocate new node and putting data Node new_node = new Node(new_data); //Make next of new node as head new_node.next = head; //Move the head to point to new Node head = new_node; } //Checks whether the value x is present in linked list public boolean search(Node head, int x) { Node current = head; //Initialize current while (current != null) { if (current.data == x) return true; //data found current = current.next; } return false; //data not found } //Driver function to test the above functions public static void main(String args[]) { //Start with the empty list LinkedList llist = new LinkedList(); /*Use push() to construct below list 14->21->11->30->10 */ llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); if (llist.search(llist.head, 21)) System.out.println("Yes"); else System.out.println("No"); } }Python # Iterative Python program to search an element # in linked list # Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null # Linked List class class LinkedList: def __init__(self): self.head = None # Initialize head as None # This function insert a new node at the # beginning of the linked list def push(self, new_data): # Create a new Node new_node = Node(new_data) # 3. Make next of new Node as head new_node.next = self.head # 4. Move the head to point to new Node self.head = new_node # This Function checks whether the value # x present in the linked list def search(self, x): # Initialize current to head current = self.head # loop till current not equal to None while current != None: if current.data == x: return True # data found current = current.next return False # Data Not found # Code execution starts here if __name__ == '__main__': # Start with the empty list llist = LinkedList() ''' Use push() to construct below list 14->21->11->30->10 ''' llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); if llist.search(21): print("Yes") else: print("No")C# // Iterative C# program to search an element // in linked list using System; // Node class public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // Linked list class public class LinkedList { Node head; // Head of list // Inserts a new node at the front of the list public void push(int new_data) { // Allocate new node and putting data Node new_node = new Node(new_data); // Make next of new node as head new_node.next = head; // Move the head to point to new Node head = new_node; } // Checks whether the value x is present in linked list public bool search(Node head, int x) { Node current = head; // Initialize current while (current != null) { if (current.data == x) return true; // data found current = current.next; } return false; // data not found } // Driver code public static void Main(String []args) { // Start with the empty list LinkedList llist = new LinkedList(); /*Use push() to construct below list 14->21->11->30->10 */ llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); if (llist.search(llist.head, 21)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }Kết quả in ra là: Yes2. Thuật toán sử dụng đệ quyỞ bên trong hàm bool search(head, x) chúng ta sẽ làm: 1. Nếu con trỏ head là NULL, return false luôn. 2. Nếu key của con trỏ head bằng với x, return true (đã tìm thấy sự hiện diện của key trong liked list). 3. Nếu không phải cả hai trường hợp trên thì return search(head->next, x) để tiếp tục gọi đến hàm đệ quy để chạy thuật toán Sau đây sẽ là đoạn code cài đặt cái thuật toán tìm kiếm một key cụ thể trong một linked list sử dụng đệ quy đã nêu ở trên, được viết bằng nhiều ngôn ngữ lập trình: CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C++ C Java Python C# C // Recursive C program to search an element in linked list #include<stdio.h> #include<stdlib.h> #include<stdbool.h> /* Link list node */ struct Node { int key; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(struct Node** head_ref, int new_key) { /* allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); /* put in the key */ new_node->key = new_key; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search(struct Node* head, int x) { // Base case if (head == NULL) return false; // If key is present in current node, return true if (head->key == x) return true; // Recur for remaining list return search(head->next, x); } /* Driver program to test count function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); search(head, 21)? printf("Yes") : printf("No"); return 0; }C++ // Recursive C++ program to search // an element in linked list #include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int key; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(struct Node** head_ref, int new_key) { /* allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); /* put in the key */ new_node->key = new_key; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search(struct Node* head, int x) { // Base case if (head == NULL) return false; // If key is present in current node, return true if (head->key == x) return true; // Recur for remaining list return search(head->next, x); } /* Driver code*/ int main() { /* Start with the empty list */ struct Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); search(head, 21)? cout << "Yes" : cout << "No"; return 0; }Java // Recursive Java program to search an element // in linked list // Node class class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Linked list class class LinkedList { Node head; //Head of list //Inserts a new node at the front of the list public void push(int new_data) { //Allocate new node and putting data Node new_node = new Node(new_data); //Make next of new node as head new_node.next = head; //Move the head to point to new Node head = new_node; } // Checks whether the value x is present // in linked list public boolean search(Node head, int x) { // Base case if (head == null) return false; // If key is present in current node, // return true if (head.data == x) return true; // Recur for remaining list return search(head.next, x); } // Driver function to test the above functions public static void main(String args[]) { // Start with the empty list LinkedList llist = new LinkedList(); /* Use push() to construct below list 14->21->11->30->10 */ llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); if (llist.search(llist.head, 21)) System.out.println("Yes"); else System.out.println("No"); } }Python # Recursive Python program to # search an element in linked list # Node class class Node: # Function to initialise # the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null class LinkedList: def __init__(self): self.head = None # Initialize head as None # This function insert a new node at # the beginning of the linked list def push(self, new_data): # Create a new Node new_node = Node(new_data) # Make next of new Node as head new_node.next = self.head # Move the head to # point to new Node self.head = new_node # Checks whether the value key # is present in linked list def search(self, li, key): # Base case if(not li): return False # If key is present in # current node, return true if(li.data == key): return True # Recur for remaining list return self.search(li.next, key) # Driver Code if __name__=='__main__': li = LinkedList() li.push(1) li.push(2) li.push(3) li.push(4) key = 4 if li.search(li.head,key): print("Yes") else: print("No")C# // Recursive C# program to search // an element in linked list using System; // Node class public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // Linked list class public class LinkedList { Node head; //Head of list //Inserts a new node at the front of the list public void push(int new_data) { //Allocate new node and putting data Node new_node = new Node(new_data); //Make next of new node as head new_node.next = head; //Move the head to point to new Node head = new_node; } // Checks whether the value x is present // in linked list public bool search(Node head, int x) { // Base case if (head == null) return false; // If key is present in current node, // return true if (head.data == x) return true; // Recur for remaining list return search(head.next, x); } // Driver code public static void Main() { // Start with the empty list LinkedList llist = new LinkedList(); /* Use push() to construct below list 14->21->11->30->10 */ llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); if (llist.search(llist.head, 21)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }Kết quả in ra là: YesNguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev: Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng! |
