Tám chuyện công nghệ

GIẢI THÍCH MỘT SỐ DẠNG BIG O: O(LOGN) Đây là một độ phức tạp điển hình, có rất nhiều trong các dạng cấu trúc dữ liệu và giải thuật cơ bản. Nắm được cách tính độ phức tạp O(logn) của các thuật toán sẽ giúp bạn tự tin hơn được 50% trong hầu hết các dạng big O. Trước khi bắt đầu bài viết, mình muốn các bạn cần tìm hiểu qua về hai bài viết cũ của mình về Big O là gì và cách tính độ phức tạp của Big O cho hàm đệ quy. Bạn tham khảo qua hai bài viết sau:

  ĐỘ PHỨC TẠP THỜI GIAN CỦA BFS ĐỐI VỚI CÂY ĐỒ THỊ Ở đây chúng ta không nói đến cách thuật toán hoạt động ra sao, chỉ xét đến độ phức tạp của thuật toán. (Các bạn nên xem các bài trước về cách tính big O trước khi xem bài này nhé) Ta sẽ tóm lại các bước của quá trình duyệt BFS rồi tiến hành phân tích: B1: Khởi tạo một danh sách là một queue B2: Truyền vào danh sách node bắt đầu B3: Lặp B3.1: Nếu danh sách hết thì sẽ kết thúc (false) B3.2: Lấy một phần tử ra khỏi danh sách, đặt là current B3.3: Nếu current là goal thì kết thúc (true) B3.4: Duyệt từng con của nó và thêm vào danh sách Tiếp theo ta tiến hành đặt ký hiệu: Gọi b là độ sâu tối đa của cây và d là số nhánh tối đa của nó như hình. Vì sao ta lại chọn là tối đa? Vì một cây thông thường thì số nhánh cũng như độ sâu từng node lá sẽ không cố định, nên ta sẽ xét trường hợp xấu nhất để thuận tiện tính toán cũng như là biết được giới hạn của nó. Trong thuật toán ta để ý rằng vòng lặp ở bước ba số lần lặp ...

  Thuật toán Quick Sort Quick Sort là một thuật toán sắp xếp không còn xa lạ với chúng ta. Không khó để tìm các tài liệu về Quick Sort, nhưng khá khó để hiểu Quick Sort một cách tường tận. Trong bài viết này, mình sẽ phân tích thuật toán trên một cách chi tiết nhất nhé. Nào bắt đầu thôi! THUẬT TOÁN Cho một dãy số 9, -1, 0, 4, 7, 10, 6. Dùng thuật toán Quick Sort để sắp xếp dãy số trên. Sau khi sắp xếp, kết quả cho ra sẽ là   -1, 0, 4, 6, 7, 9, 10 là một dãy số tăng dần. Gọi quickSort(arr, l, r) là hàm của thuật toán với 3 thành phần: arr: mảng chúng ta cần sắp xếp l, r: left và right, là hai con số xác định phần nào của mảng arr dùng để sắp xếp Để dễ hình dung hơn, ta có ví dụ thế này Cho arr là dãy số lúc nãy. Như hình trên, ta thấy rằng l = 4, r = 6. Lúc đấy ta sẽ gọi hàm lúc nãy là quickSort(arr, 4, 6), hàm này sẽ chỉ sắp xếp một phần của dãy số là 7, 10, 6. Sau khi gọi hàm này sắp xếp, ta sẽ thu được dãy như sau Trong quá trình tính toán thì l và r mớ...

Tính toán big O cho hàm đệ quy Nếu bạn chưa hiểu big O là gì, hãy đọc bài trước: https://8techblog.blogspot.com/2020/05/tim-hieu-o-phuc-tap-thoi-gian-big-o-cho.html

Tìm hiểu Big O cho người mới chi tiết Khi chúng ta làm việc với thuật toán, chúng ta cần đánh giá chúng xem thuật toán chúng ta đã tốt chưa. Một câu hỏi được đặt ra như sau:

TỔNG QUAN XÁC SUẤT THỐNG KÊ Xác suất thống kê là một lý thuyết quan trọng trong các bài toán nghiên cứu về số liệu, đặc biệt là ngành CNTT. Học tốt môn xác suất thống kê sẽ là nền tảng cho việc nghiên cứu chuyên sâu sau này, đặc biệt là trong lĩnh vực Trí tuệ nhân tạo. Vậy xác suất thống kê là gì? Nó là một nhánh của toán học bao gồm hai nội dung: Xác suất, Thống kê. Chúng ta sẽ phân tích rõ từng thành phần trong khái niệm này Xác suất (Probability) Đó là một lý thuyết toán học tính toán về khả năng xảy ra của một vấn đề nào đó, như là tỉ lệ tung ra một mặt của xúc xắc, hay là khả năng trúng giải độc đắc của một tờ vé số. Các bài toán xác suất đã có từ thời nguyên thủy, nhưng nở rộ vào thời kỳ Phục Hưng (*) . Những con bạc không thể giải thích được quy luật của những trò chơi may rủi, nên đã tìm đến những nhà khoa học nổi tiếng và nhờ họ nghiên cứu về nó. Trong một khoảng thời gian dài, có những nghi ngờ về việc liệu lý thuyết xác suất sẽ trở thành một phần trong toán học...

TỔNG QUAN CẤU TRÚC DỮ LIỆU Cấu trúc dữ liệu là một thành phần không thể thiếu trong môn học. Nó áp dụng cho rất nhiều, hầu như là toàn bộ bài toán dù lớn hay nhỏ. Thế cấu trúc dữ liệu là gì? Trích Wikipedia EN: “ Trong ngành khoa học máy tính, cấu trúc dữ liệu là cách tổ chức, quản lý và lưu trữ dữ liệu theo một định dạng nào đó mà ta có thể truy cập và chỉnh sửa một cách hiệu quả. Nói đúng hơn, cấu trúc dữ liệu là một tập các dữ liệu, mối quan hệ giữa chúng, và các hàm hoặc toán tử có thể áp dụng lên chúng. ” Theo Wiki, ta có thể hiểu nôm na rằng đó là một cách tổ chức (bao gồm bố trí, quản lý, lưu trữ,…) để ta có thể dễ dàng thao tác trên dữ liệu (truy cập; chỉnh sửa – thêm, xóa, sắp xếp;…). Dùng một Arrays để lưu trữ danh sách điểm số, tên của các thành viên trong một lớp học, cũng có thể xem như là một cách cấu trúc dữ liệu, vì Arrays này có sự bố trí các dữ liệu cùng loại liền kề nhau, khi duyệt từng ô dữ liệu để thao tác sẽ khá là dễ dàng. Một cách định nghĩa tương tự...

Stack, Queue và Priority Queue trong Java Phần 3: Priority Queue 1.      Định nghĩa Priority Queue là gì? Priority Queue là một danh sách dạng biến thể của queue với thứ tự sắp xếp dựa trên mức độ ưu tiên của phần tử. Tức danh sách này có cấu trúc đưa vào và đưa ra giống queue, chỉ có một điểm khác là sau khi đưa vào thì nó sẽ đẩy phần tử mới vào vị trí phù hợp theo thứ tự giảm dần từ rear – có giá trị cao nhất, đến top – có giá trị thấp nhất. Nói một chút về giá trị ưu tiên (priority). Về mặt tổng quan, đó là một cách để sắp xếp công việc nào sẽ được thực hiện trước, công việc nào sẽ được thực hiện sau. Về mặt cụ thể, đây là chỉ số giúp cho ta biết được phần tử nào sẽ được đưa ra ngoài trước, phần tử nào sẽ được đưa ra ngoài sau. Theo quy tắc trong đây, giá trị nào được xem như là nhỏ nhất thì sẽ được thực hiện trước. (Lưu ý: Việc định giá trị của 1 phần tử lớn hay nhỏ không theo 1 công thức cụ thể, mà phụ thuộc vào từng bài toán khác nhau).  ...

Stack, Queue và Priority trong Java (phần 2) Phần 2: Queue Queue là gì? Queue là một cách thức lưu trữ và lấy dữ liệu theo kiểu hàng đợi. Bạn có thể tưởng tượng 1 hàng người đi mua vé, ai tới trước thì sẽ mua vé và ra trước Bạn có 5 người đang đứng đợi mua vé theo thứ tự từ trái sang lần lượt là 1, 2, 3, 4, 5. Người thứ 1 vào trước, người thứ 2 vào sau người thứ 1 và cứ như thế

Stack, Queue và Priority Queue trong Java (phần 1) Phần 1: Stack Stack là gì? Stack là một cách thức lưu trữ và lấy dữ liệu theo kiểu xếp chồng. Để dễ hình dung, giả sử bạn có 1 thùng dựng sách có chiều dài và chiều rộng vừa với cuốn sách, và chiều cao vừa đủ.