Giải thích thuật toán Brute Force

Thuật toán Brute Force giống hệt như chúng - các phương pháp đơn giản để giải quyết một vấn đề dựa vào sức mạnh tính toán tuyệt đối và thử mọi khả năng thay vì các kỹ thuật tiên tiến để cải thiện hiệu quả.

Ví dụ, hãy tưởng tượng bạn có một ổ khóa nhỏ có 4 chữ số, mỗi chữ số từ 0-9. Bạn quên kết hợp của mình, nhưng bạn không muốn mua một ổ khóa khác. Vì bạn không thể nhớ bất kỳ chữ số nào, bạn phải sử dụng phương pháp thô bạo để mở khóa.

Vì vậy, bạn đặt tất cả các số về 0 và thử từng số một: 0001, 0002, 0003, v.v. cho đến khi nó mở ra. Trong trường hợp xấu nhất, sẽ mất 104 hoặc 10.000 lần thử để tìm ra sự kết hợp của bạn.

Một ví dụ kinh điển trong khoa học máy tính là bài toán nhân viên bán hàng đi du lịch (TSP). Giả sử một nhân viên bán hàng cần đến thăm 10 thành phố trên khắp đất nước. Làm thế nào để xác định thứ tự mà các thành phố đó nên được đến thăm sao cho tổng quãng đường đi được là tối thiểu?

Giải pháp bạo lực chỉ đơn giản là tính tổng khoảng cách cho mọi tuyến đường có thể và sau đó chọn tuyến đường ngắn nhất. Điều này không đặc biệt hiệu quả vì có thể loại bỏ nhiều tuyến đường khả thi thông qua các thuật toán thông minh.

Độ phức tạp về thời gian của bạo lực là O (m n ) , đôi khi được viết là O (n * m). Vì vậy, nếu chúng ta tìm kiếm một chuỗi ký tự "n" trong chuỗi ký tự "m" bằng cách sử dụng vũ lực, chúng ta sẽ mất n * m lần thử.

Thông tin thêm về các thuật toán

Trong khoa học máy tính, một thuật toán chỉ đơn giản là một tập hợp các thủ tục từng bước để giải quyết một vấn đề nhất định. Các thuật toán có thể được thiết kế để thực hiện các phép tính, xử lý dữ liệu hoặc thực hiện các tác vụ suy luận tự động.

Đây là cách Wikipedia định nghĩa chúng:

Thuật toán là một phương pháp hiệu quả có thể được biểu diễn trong một khoảng không gian và thời gian hữu hạn và bằng một ngôn ngữ hình thức được xác định rõ ràng để tính toán một hàm. Bắt đầu từ trạng thái ban đầu và đầu vào ban đầu (có thể trống), các lệnh mô tả một phép tính, khi được thực thi, sẽ tiến hành thông qua một số hữu hạn các trạng thái liên tiếp được xác định rõ, cuối cùng tạo ra “đầu ra” và kết thúc ở trạng thái kết thúc cuối cùng. Sự chuyển đổi từ trạng thái này sang trạng thái tiếp theo không nhất thiết phải mang tính xác định; một số thuật toán, được gọi là thuật toán ngẫu nhiên, kết hợp đầu vào ngẫu nhiên.

Có một số yêu cầu nhất định mà một thuật toán phải tuân theo:

  1. Tính xác định: Mỗi bước trong quy trình đều được nêu chính xác.
  2. Tính toán hiệu quả: Mỗi bước trong quy trình có thể được thực hiện bằng máy tính.
  3. Tính hữu hạn: Chương trình cuối cùng sẽ kết thúc thành công.

Một số loại thuật toán phổ biến bao gồm:

  • thuật toán sắp xếp
  • thuật toán tìm kiếm
  • các thuật toán nén.

Các lớp thuật toán bao gồm

  • Đồ thị
  • Lập trình năng động
  • Sắp xếp
  • Đang tìm kiếm
  • Dây
  • môn Toán
  • Hình học tính toán
  • Tối ưu hóa
  • Điều khoản khác.

Mặc dù về mặt kỹ thuật không phải là một lớp thuật toán, nhưng Cấu trúc dữ liệu thường được nhóm lại với chúng.

Hiệu quả

Các thuật toán được đánh giá phổ biến nhất bởi hiệu quả của chúng và lượng tài nguyên máy tính mà chúng yêu cầu để hoàn thành nhiệm vụ của chúng.

Một cách phổ biến để đánh giá một thuật toán là xem xét độ phức tạp về thời gian của nó. Điều này cho thấy thời gian chạy của thuật toán tăng lên như thế nào khi kích thước đầu vào tăng lên. Vì các thuật toán ngày nay phải hoạt động trên đầu vào dữ liệu lớn, nên điều cần thiết là các thuật toán của chúng ta phải có thời gian chạy nhanh hợp lý.

Giải thuật sắp xếp

Các thuật toán sắp xếp có nhiều loại khác nhau tùy thuộc vào sự cần thiết của bạn. Một số, rất phổ biến và được sử dụng rộng rãi là:

Sắp xếp nhanh chóng

Không có cuộc thảo luận sắp xếp nào có thể kết thúc mà không có sự sắp xếp nhanh chóng. Đây là khái niệm cơ bản: Sắp xếp nhanh

Hợp nhất

Một thuật toán sắp xếp dựa trên khái niệm cách các mảng đã sắp xếp được hợp nhất để tạo ra một mảng đã sắp xếp. Đọc thêm về nó ở đây: Mergesort

Chương trình học của freeCodeCamp nhấn mạnh nhiều vào việc tạo ra các thuật toán. Điều này là do học thuật toán là một cách tốt để thực hành kỹ năng lập trình. Người phỏng vấn thường kiểm tra ứng viên về các thuật toán trong các cuộc phỏng vấn tuyển dụng nhà phát triển.

Sách về các thuật toán trong JavaScript:

Cấu trúc dữ liệu trong JavaScript

  • Cuốn sách miễn phí bao gồm Cấu trúc dữ liệu trong JavaScript
  • GitBook

Học cấu trúc dữ liệu và thuật toán JavaScript - Ấn bản thứ hai

  • Bao gồm lập trình hướng đối tượng, kế thừa nguyên mẫu, thuật toán sắp xếp & tìm kiếm, quicksort, hợp nhất, cây tìm kiếm nhị phân và các khái niệm thuật toán nâng cao
  • Amazon
  • ISBN-13: 978-1785285493

Cấu trúc dữ liệu và thuật toán với JavaScript: Đưa các phương pháp điện toán cổ điển vào Web

  • Bao gồm các thuật toán đệ quy, sắp xếp và tìm kiếm, danh sách liên kết và cây tìm kiếm nhị phân.
  • Amazon
  • ISBN-13: 978-1449364939