Khái Niệm Thuật Toán | Các Tiêu Chí Đánh Giá Một Thuật Toán

Ví dụ[sửa | sửa mã nguồn]

Ví dụ thuật toán[sửa | sửa mã nguồn]

Một trong những thuật toán đơn giản nhất là tìm số lớn nhất trong danh sách các số có thứ tự ngẫu nhiên. Tìm lời giải yêu cầu nhìn vào mọi số trong danh sách. Từ đó dẫn đến một thuật toán đơn giản, có thể được nêu trong phần mô tả cấp cao bằng văn xuôi tiếng Anh, như:

Mô tả cấp cao:

1. Nếu không có số nào trong tập hợp thì không có số cao nhất.
2. Giả sử số đầu tiên trong tập hợp là số lớn nhất trong tập hợp.
3. Với mỗi số còn lại trong tập hợp: nếu số này lớn hơn số lớn nhất hiện tại thì coi số này là số lớn nhất trong tập hợp.
4. Khi không còn số nào trong tập hợp để lặp lại, hãy coi số lớn nhất hiện tại là số lớn nhất của tập hợp.

Bán mô tả chính thức: Được viết bằng văn xuôi nhưng gần với ngôn ngữ cấp cao của chương trình máy tính hơn nhiều, sau đây là cách mã hóa chính thức hơn của thuật toán bằng mã giả hoặc mã pidgin:

Input: A list of numbers L. Output: The largest number in the list L.

if L.size = 0 return null largest ← L[0] for each item in L, do if item > largest, then largest ← item return largest

Thuật toán Euclid[sửa | sửa mã nguồn]

Thuật toán của Euclid để tính ước số chung lớn nhất (ƯCLN) cho hai số xuất hiện dưới dạng Mệnh đề II trong Quyển VII (“Lý thuyết số cơ bản”) của tác phẩm Cơ sở của ông.[50] Do đó, Euclid đặt ra vấn đề: “Cho hai số không nguyên tố với nhau, hãy tìm số đo chung lớn nhất của chúng”. Ông định nghĩa “Một số [là] một vô số bao gồm các đơn vị”: một số đếm, một số nguyên dương không bao gồm số không. Để “đo” là đặt một chiều dài ngắn s liên tiếp (q lần) lên trên chiều dài l cho đến khi phần còn lại là r nhỏ hơn chiều dài ngắn s. [51] Nói cách hiện đại, phần dư r = l – q × s, q là thương số, hoặc phần dư r là “môđun”, phần nguyên còn lại sau phép chia.[52]

Để phương pháp Euclid thành công, độ dài bắt đầu phải thỏa mãn hai yêu cầu: (i) độ dài không được bằng 0, VÀ (ii) phép trừ phải “hợp lệ”; tức là, một phép thử phải đảm bảo rằng số nhỏ hơn trong hai số bị trừ đi số lớn hơn (hoặc hai số có thể bằng nhau để phép trừ của chúng cho kết quả bằng không).

Chứng minh ban đầu của Euclid bổ sung thêm một yêu cầu thứ ba: hai độ dài không được nguyên tố với nhau. Euclid đã quy định điều này để ông có thể xây dựng một bằng chứng rút gọn là vô lý rằng số đo chung của hai số trên thực tế là lớn nhất.[53] Trong khi thuật toán của Nicomachus cũng giống như thuật toán của Euclid, khi các số nguyên tố với nhau, nó mang lại số “1” cho số đo chung của chúng. Vì vậy, chính xác mà nói, sau đây thực sự là thuật toán của Nicomachus.

1599 = 650×2 + 299 650 = 299×2 + 52 299 = 52×5 + 39 52 = 39×1 + 13 39 = 13×3 + 0

Ngôn ngữ máy tính cho thuật toán Euclid[sửa | sửa mã nguồn]

Chỉ một số loại lệnh được yêu cầu để thực thi thuật toán Euclid — một số phép thử logic (GOTO có điều kiện), GOTO không điều kiện, phép gán (thay thế) và phép trừ.

• Vị trí được ký hiệu bằng (các) chữ cái viết hoa, ví dụ: S, A, v.v.
• Số lượng (số) khác nhau ở một vị trí được viết bằng (các) chữ cái thường và (thường) được kết hợp với tên của vị trí. Ví dụ, vị trí L ở đầu có thể chứa số l = 3009.

Một chương trình đơn giản cho thuật toán Euclid[sửa | sửa mã nguồn]

Thuật toán sau đây được đóng khung như là phiên bản bốn bước của Knuth của Euclid’s và Nicomachus, nhưng thay vì sử dụng phép chia để tìm phần dư, nó sử dụng các phép trừ liên tiếp của độ dài s từ độ dài còn lại r cho đến khi r nhỏ hơn s. Mô tả cấp cao, được in đậm, được phỏng theo Knuth 1973: 2–4:

ĐẦU VÀO:

1 [Into two locations L and S put the numbers l and s that represent the two lengths]: INPUT L, S

2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]: R ← L

E0: [Đảm bảo r ≥ s. ]

3 [Ensure the smaller of the two numbers is in S and the larger in R]: IF R > S THEN the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6: GOTO step 6 ELSE swap the contents of R and S.

4 L ← R (this first step is redundant, but is useful for later discussion).

5 R ← S

6 S ← L

E1: [Tìm phần dư]: Cho đến khi độ dài còn lại r trong R nhỏ hơn độ dài ngắn hơn s trong S, lặp đi lặp lại phép trừ số đo s trong S với độ dài còn lại r trong R.

7 IF S > R THEN done measuring so GOTO 10 ELSE measure again,

8 R ← R − S

9 [Remainder-loop]: GOTO 7.

E2: [Phần dư có bằng 0? ]: HOẶC (i) số đo cuối cùng là chính xác, phần còn lại trong R bằng 0 và chương trình có thể tạm dừng, HOẶC (ii) thuật toán phải tiếp tục: số đo cuối cùng để lại phần dư trong R nhỏ hơn số đo trong S.

10 IF R = 0 THEN done so GOTO step 15 ELSE CONTINUE TO step 11,

E3: [Đảo vị trí s và r ]: Điểm mấu chốt của thuật toán Euclid. Sử dụng phần dư r để đo số trước đó nhỏ hơn s; L phục vụ như một kho lưu trữ tạm thời.

11 L ← R

12 R ← S

13 S ← L

14 [Repeat the measuring process]: GOTO 7

ĐẦU RA:

15 [Done. S contains the greatest common divisor]: PRINT S

XONG:

16 HALT, END, STOP.

Một chương trình đơn giản cho thuật toán Euclid[sửa | sửa mã nguồn]

Phiên bản sau của thuật toán Euclid chỉ yêu cầu sáu lệnh cốt lõi để thực hiện mười ba lệnh được yêu cầu bởi “chương trình chưa thanh lịch”; tệ hơn nữa là “chương trình chưa thanh lịch” yêu cầu nhiều loại hướng dẫn hơn. [làm rõ] Bạn có thể tìm thấy sơ đồ của “Thanh lịch” ở đầu bài viết này. Trong ngôn ngữ BASIC (không có cấu trúc), các bước được đánh số, và lệnh LET [] = [] là lệnh gán được ký hiệu bằng ←.

5 REM Euclid’s algorithm for greatest common divisor 6 PRINT “Type two integers greater than 0” 10 INPUT A,B 20 IF B=0 THEN GOTO 80 30 IF A > B THEN GOTO 60 40 LET B=B-A 50 GOTO 20 60 LET A=A-B 70 GOTO 20 80 PRINT A 90 END

Cách “chương trình thanh lịch” hoạt động: Thay cho “vòng lặp Euclid” bên ngoài, “Elegant” di chuyển qua lại giữa hai “co-vòng lặp”, một vòng lặp A> B tính A ← A – B và một vòng lặp B ≤ A tính toán B ← B – A. Điều này hoạt động bởi vì, khi cuối cùng giá trị nhỏ nhất M nhỏ hơn hoặc bằng dải con S (Chênh lệch = Minuend – Subtrahend), minuend có thể trở thành s (chiều dài đo mới) và subtrahend có thể trở thành r mới (độ dài được đo); nói cách khác, “ý nghĩa” của phép trừ đảo ngược. Phiên bản sau có thể được sử dụng với các ngôn ngữ hướng đối tượng:

// Euclid’s algorithm for greatest common divisor int euclidAlgorithm (int A, int B){ A=Math.abs(A); B=Math.abs(B); while (B!=0){ if (A>B) A=A-B; else B=B-A; } return A; }

Kiểm tra các thuật toán Euclid[sửa | sửa mã nguồn]

Một thuật toán có làm được những gì mà tác giả của nó muốn nó làm không? Một số trường hợp thử nghiệm thường cung cấp một số tin cậy về chức năng cốt lõi. Nhưng các thử nghiệm là không đủ. Đối với các trường hợp thử nghiệm, một nguồn [54] sử dụng 3009 và 884. Knuth đề xuất 40902, 24140. Một trường hợp thú vị khác là hai số nguyên tố cùng nhau 14157 và 5950.

Nhưng “trường hợp ngoại lệ” [55] phải được xác định và thử nghiệm. Liệu “Inelegant” có thực hiện đúng khi R> S, S> R, R = S không? Cũng vậy cho chương trình “Thanh lịch”: B> A, A> B, A = B? (Có cho tất cả). Điều gì xảy ra khi một số bằng 0, cả hai số đều bằng không? (“Chưa thanh lịch” rơi vào vòng lặp vĩnh viễn trong các trường hợp trên; “Thanh lịch” rơi vào vòng lặp vĩnh viễn khi A = 0.) Điều gì xảy ra nếu người dùng nhập số âm ? Số phân số? Nếu các số đầu vào, tức là miền của hàm được tính toán bởi thuật toán / chương trình, chỉ bao gồm các số nguyên dương bao gồm cả số 0, thì các lỗi ở số 0 chỉ ra rằng thuật toán (và chương trình khởi tạo nó) là một hàm riêng phần chứ không phải một hàm tổng. Một thất bại đáng chú ý do các ngoại lệ kiểu như vậy là sự cố tên lửa Ariane 5 Flight 501 (ngày 4 tháng 6 năm 1996).

Chứng minh tính đúng đắn của chương trình bằng cách sử dụng quy nạp toán học: Knuth chứng minh việc áp dụng quy nạp toán học cho phiên bản “mở rộng” của thuật toán Euclid và ông đề xuất “một phương pháp chung áp dụng để chứng minh tính hợp lệ của bất kỳ thuật toán nào”.[56] Tausworthe đề xuất rằng thước đo độ phức tạp của một chương trình là độ dài của bằng chứng tính đúng đắn của nó.[57]

Đo lường và cải thiện các thuật toán Euclid[sửa | sửa mã nguồn]

Thanh lịch (nhỏ gọn) so với tốt (tốc độ): Chỉ với sáu lệnh cốt lõi, “Thanh lịch” là chiến thắng rõ ràng, so với “Không thanh lịch” với 13 lệnh. Tuy nhiên, “Không thanh lịch” nhanh hơn (nó đến HALT trong ít bước hơn). Phân tích thuật toán [58] chỉ ra lý do tại sao lại như vậy: “Thanh lịch” thực hiện hai phép thử điều kiện trong mỗi vòng trừ, trong khi “Không thanh lịch” chỉ thực hiện một phép thử. Vì thuật toán (thường) yêu cầu nhiều lần lặp lại, nên trung bình sẽ lãng phí nhiều thời gian để thực hiện “B = 0?” kiểm tra chỉ cần thiết sau khi phần còn lại được tính toán.

Các thuật toán có thể được cải thiện không?: Một khi lập trình viên đánh giá một chương trình “phù hợp” và “hiệu quả” – nghĩa là nó tính toán chức năng mà tác giả của nó dự định – thì câu hỏi sẽ trở thành, liệu nó có thể được cải thiện không?

Có thể cải thiện độ nhỏ gọn của “Không thanh lịch” bằng cách loại bỏ năm bước. Nhưng Chaitin đã chứng minh rằng việc nén một thuật toán không thể được tự động hóa bằng một thuật toán tổng quát;[59] đúng hơn, nó chỉ có thể được thực hiện theo kinh nghiệm; tức là, bằng cách tìm kiếm đầy đủ, thử và sai, thông minh, sáng suốt, áp dụng suy luận quy nạp, v.v. Quan sát các bước 4, 5 và 6 được lặp lại trong các bước 11, 12 và 13. So sánh với “Thanh lịch” cung cấp gợi ý rằng các bước này, cùng với các bước 2 và 3, có thể bị loại bỏ. Điều này làm giảm số lượng lệnh cốt lõi từ 13 xuống 8, làm cho nó “thanh lịch” hơn “Thanh lịch”, với chín bước.

Tốc độ của “Thanh lịch” có thể được cải thiện bằng cách di chuyển “B = 0?” kiểm tra bên ngoài của hai vòng trừ. Thay đổi này yêu cầu bổ sung ba lệnh (B = 0 ?, A = 0 ?, GOTO). Bây giờ “Thanh lịch” tính toán các số ví dụ nhanh hơn; cho dù điều này luôn đúng đối với bất kỳ A, B và R, S nào cho trước hay không sẽ yêu cầu một phân tích chi tiết.

Tổng hợp 12 loại thuật toán cơ bản cần biết

Sau đây là tổng hợp các thuật toán cơ bản mà lập trình viên cần biết để hỗ trợ tốt hơn cho công việc của mình:

Thuật toán Hashing

Hashing là thuật toán tham gia vào quá trình phát hiện và xác định dữ liệu thích hợp thông qua key và ID. Vai trò chính của hashing chính là phát hiện lỗi, quản lý bộ nhớ cache, mật mã và tra cứu. Cụ thể, hàm hashing được tích hợp vào khóa và cho ra các giá trị chính xác nhất.

Hàm hashing còn được sử dụng như một định danh duy nhất cho những tập dữ liệu và các phép tính toán cho những người dùng để tạo ra các giá trị dữ liệu không bị trùng lặp. Thường thì hàm hashing được sử dụng trong các bộ định tuyến để lưu trữ địa chỉ IP.

Thuật toán tìm kiếm

Thuật toán tìm kiếm thường được áp dụng cho dãy cấu trúc dữ liệu tuyến tính hay cấu trúc dữ liệu về đồ họa. Đây được gọi là thuật toán tìm kiếm nhị phân nhằm giúp cho các nhà phát triển dễ dàng tìm kiếm sự hiệu quả trên những tập dữ liệu đã được sắp xếp với hàm phức tạp với thời gian của O (log N).

Cơ chế của thuật toán tìm kiếm nhị phân là chia danh sách thành hai nửa cho đến khi thấy được mục đích yêu cầu. Sau đó, dùng nó để gỡ lỗi, đặc biệt là những lỗi có sự liên quan đến git bisection.

Thuật toán sắp xếp

Các nhà phát triển sử dụng thuật toán này để có thể đặt dữ liệu theo cách có tổ chức. Các thành phần cơ bản của thuật toán QuickSort là các phần dữ liệu được dùng để so sánh với nhau nhằm xác định được thứ tự tương ứng của chúng.

Mức độ phức tạp thời gian của O (nlogn) được dùng để thực hiện vào việc so sánh. Tuy nhiên, Radix Sort có kỹ thuật xử lý nhanh hơn QuickSort. Lý do nó được sắp xếp các phần tử trong một mô hình tuyến tính với độ phức tạo thời gian O (n). Các thuật toán sắp xếp khác như: sắp xếp đếm, sắp xếp hợp nhất và sắp xếp nhóm.

Thuật toán lập trình động

thuật toán lập trình động là một hàm được dùng với mục đích giải quyết các vấn đề phức tạp có sự liên quan đến trí tuệ thông qua quá trình tách các vấn đề thành, các bài toán con nhỏ hơn. Sau khi đã giải quyết được các bài toán rồi thì thực hiện xây dựng lại thành một vấn đề phức tạp, đòi hỏi bộ nhớ của các kết quả nhỏ hơn để đưa ra câu trả lời cho các vấn đề phức tạp.

thuật toán trong lập trình thích hợp để ghi nhớ, thông qua đó cho phép lưu trữ các vấn đề đã được giải quyết trước đó. Trường hợp tiếp theo xuất hiện thì vấn đề sẽ được giải quyết nhanh hơn rất nhiều.

Thuật toán Dijkstra

Một vấn đề cực kỳ quan trọng khác mà các nhà phát triển làm việc là tìm đường dẫn. Đồ thị hóa một cách cực kỳ linh hoạt để mô tả tất cả các loại vấn đề liên quan đến mạng lưới các đối tượng riêng biệt.

thuật toán Dijkstra là một cách tìm đường đi nhanh nhất giữa hai nút trong biểu đồ. Đây chính là nền tảng của hầu hết các công việc được thực hiện trong việc tìm kiếm đường đi và được sử dụng trong mọi thứ, từ trí tuệ nhân tạo cho đến thiết kế trò chơi.

Thuật toán phân tích liên kết

thuật toán phân tích liên kết thường được ứng dụng chủ yếu trong lĩnh vực mạng. thuật toán này cung cấp khả năng tương quan trong cùng một tên miền với nhiều thực thể khác nhau.

Phân tích liên kế sử dụng trong những ma trận phức tạp và biểu diễn đồ họa nhằm liên kết các căn cứ tương tự trong cùng một miền hiện tại. Loại thuật toán cơ bản này thường được dùng trong các công cụ như: Google, Facebook, Twitter.

Thuật toán Mô-đun

Các thuật toán mã hóa phức tạp nếu được phân tích dựa trên thuật toán mô-đun sẽ trở nên đơn giản và trở nên dễ dàng hơn rất nhiều. Đối với số học mô-đun, các thông số hiện tại đang xử lý chỉ là số nguyên và các phép toán chủ yếu được dùng chính là cộng, trừ, nhân, chia.

Thuật toán phân tích cú pháp và xâu ký tự

Quy trình tạo xâu luôn đặc biệt và quan trọng đối với miền và phân tử mạng. Để giúp thuật toán xâu ký tự có thể phát huy được hết khả năng thì các xâu phải khớp trong cùng một chuỗi dài hoặc khi xác nhận chuỗi bằng cách phân tích cú pháp qua giới hạn đã được xác định từ trước. thuật toán phân tích cú pháp và xâu ký tự được dùng chủ yếu trong quá trình phát triển web cho URL.

Thuật toán biến đổi Fourier

thuật toán biến đổi Fourier thường được biết đến là một trong những thuật toán đơn giản nhưng lại rất mạnh. Loại thuật toán này được dùng để giúp chuyển đổi tín hiệu từ tên miền thời gian sang miền tần số và ngược lại.

Hiện tại, các mạng kỹ thuật số như: wifi, internet, máy tính, điện thoại, vệ tinh, bộ định vị,…đều sử dụng thuật toán biến đổi Fourier để vận hành.

Thuật toán mã hóa Huffman

thuật toán mã hóa Huffman chính là nền tảng của nén văn bản hiện đại. Nó thường hoạt động bằng cách xem xét tần suất các ký tự khác nhau, xuất hiện trong một văn bản và sắp xếp chúng trong một cây dựa trên tần suất này.

Thuật toán các tập không giao nhau

thuật toán các tập không giao nhau chính là một cấu trúc dữ liệu, nó đóng vai trò như một cấu trúc trợ giúp một thuật toán được dùng để biểu diễn nhiều tập hợp khác nhau trong mảng riêng lẻ. Và mỗi mục chính là một phần tử của nhiều tập hợp. Do đó, các bộ tách rời được đại diện cho những phần tử được kết nối với nhau trong cùng một thuật toán đồ thị hay phân đoạn của hình ảnh.

Hệ số tích phân

thuật toán hệ số tích phân chính là thuật toán cung cấp hướng dẫn từng bước về cách lấy các thừa số nguyên tố của một số tổng hợp. Hệ số tích phân sẽ giúp bạn giải quyết các vấn đề phức tạp trong nền tảng mã hóa yêu cầu, bạn cần phải giải quyết các số nguyên phức hợp lớn.

Trên đây là những chia sẻ về khái niệm thuật toán là gì, tầm quan trọng cũng như các loại thuật toán phổ biến hiện nay. Mong rằng với những chia sẻ trên đây sẽ giúp bạn đọc có thể hiểu rõ hơn về thuật toán và biết cách ứng dụng thuật toán hiệu quả cho công việc lập trình của mình. Cùng theo dõi HR Insider để xem thêm nhiều thông tin hữu ích hơn nhé!

Bài viết dành riêng cho thành viên của HR Insider.

Khái niệm ‘thuật toán’ ra đời như thế nào?

Thuật toán (algorithm), bắt nguồn từ tên nhà toán học người Ba Tư trong thế kỷ 8, là một tập hợp các bước để giải quyết một vấn đề.

Khái niệm ‘thuật toán’ ra đời như thế nào?

Video: BBC

Khái niệm ‘thuật toán’ ra đời như thế nào?

Thuật toán (algorithm), bắt nguồn từ tên nhà toán học người Ba Tư trong thế kỷ 8, là một tập hợp các bước để giải quyết một vấn đề.

Khái niệm ‘thuật toán’ ra đời như thế nào?

Video: BBC

Bài 11: Thuật toán và Phân tích thuật toán

Thuật toán và những tính chất của thuật toán

Tại sao cần dùng thuật toán?

Tối ưu hóa việc tìm kiếm

Thuật toán chính là những chỉ dẫn để tìm thấy kết quả cho vấn đề một cách tối ưu nhất. Các lập trình viên thường sử dụng thuật toán để tìm ra con đường ngắn nhất để giải quyết vấn đề.

Ví dụ như: Google Map, Grab, Uber là những ứng dụng thường sử dụng thuật toán để tính toán quãng đường ngắn nhất, thuận tiện nhất khi hướng dẫn và hỗ trợ khách hàng di chuyển.

Một ví dụ dễ hiểu khác chính là Google, bạn có thể tìm bất cứ thông tin gì tại nơi đây. Vì Google luôn cập nhật và nâng cấp thuật toán của mình để cung cấp thông tin cho người dùng về mọi lĩnh vực, với tốc độ trả kết quả cực kỳ nhanh, chỉ trong 1 giây có thể hiển thị lên đến hàng ngàn kết quả.

Khả năng bảo mật cao

Thuật toán đều sẽ được mã hóa thành các chuỗi ký tự. Vì thế, khi truyền tải và nhận dữ liệu đều cần phải mã hóa. Điều này thể giảm sự xâm nhập từ các hacker và thể hiện khả năng bảo mật tốt của thuật toán.

Tham khảo[sửa | sửa mã nguồn]

1. ^ “The Definitive Glossary of Higher Mathematical Jargon — Algorithm”. Math Vault (bằng tiếng Anh). ngày 1 tháng 8 năm 2019. Bản gốc lưu trữ ngày 28 tháng 2 năm 2020. Truy cập ngày 14 tháng 11 năm 2019.
2. ^ “Definition oALGORITHM”. Merriam-Webster Online Dictionary (bằng tiếng Anh). Bản gốc lưu trữ ngày 14 tháng 2 năm 2020. Truy cập ngày 14 tháng 11 năm 2019.
3. ^ “Any classical mathematical algorithm, for example, can be described in a finite number of English words” (Rogers 1987:2).
4. ^ Well defined with respect to the agent that executes the algorithm: “There is a computing agent, usually human, which can react to the instructions and carry out the computations” (Rogers 1987:2).
5. ^ “an algorithm is a procedure for computing a function (with respect to some chosen notation for integers)… this limitation (to numerical functions) results in no loss of generality”, (Rogers 1987:1).
6. ^ “An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins” (Knuth 1973:5).
7. ^ “A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a ‘computational method'” (Knuth 1973:5).
8. ^ “An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs” (Knuth 1973:5).
9. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: “a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analogue devices… carried forward deterministically, without resort to random methods or devices, e.g., dice” (Rogers 1987:2).
10. ^ Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. tr. 7–8. ISBN 9783642181924.
11. ^ “Hellenistic Mathematics”. The Story of Mathematics. Bản gốc lưu trữ ngày 11 tháng 9 năm 2019. Truy cập ngày 14 tháng 11 năm 2019.
12. ^ Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons. ISBN 978-1-118-46029-0.
13. ^ Dooley, John F. (2013). A Brief History of Cryptology and Cryptographic Algorithms. Springer Science & Business Media. tr. 12–3. ISBN 9783319016283.
14. ^ “Al-Khwarizmi – Islamic Mathematics”. The Story of Mathematics. Bản gốc lưu trữ ngày 25 tháng 7 năm 2019. Truy cập ngày 14 tháng 11 năm 2019.
15. ^ Kleene 1943 in Davis 1965:274
16. ^ Rosser 1939 in Davis 1965:225
17. ^ Stone 1973:4
18. ^ Simanowski, Roberto (2018). The Death Algorithm and Other Digital Dilemmas. Untimely Meditations. 14. Chase, Jefferson biên dịch. Cambridge, Massachusetts: MIT Press. tr. 147. ISBN 9780262536370. Bản gốc lưu trữ ngày 22 tháng 12 năm 2019. Truy cập ngày 27 tháng 5 năm 2019.

    […] the next level of abstraction of central bureaucracy: globally operating algorithms.

19. ^ Dietrich, Eric (2001) [1999]. “Algorithm”. Trong Wilson, Robert Andrew; Keil, Frank C. (biên tập). The MIT Encyclopedia of the Cognitive Sciences. MIT Cognet library. Cambridge, Massachusetts: MIT Press. tr. 11. ISBN 9780262731447. Truy cập ngày 22 tháng 7 năm 2020.

    An algorithm is a recipe, method, or technique for doing something.

20. ^ Stone simply requires that “it must terminate in a finite number of steps” (Stone 1973:7–8).
21. ^ Boolos and Jeffrey 1974,1999:19
22. ^ cf Stone 1972:5
23. ^ Knuth 1973:7 states: “In practice we not only want algorithms, we want good algorithms… one criterion of goodness is the length of time taken to perform the algorithm… other criteria are the adaptability of the algorithm to computers, its simplicity, and elegance, etc.”
24. ^ cf Stone 1973:6
25. ^ Stone 1973:7–8 states that there must be, “…a procedure that a robot [i.e., computer] can follow in order to determine precisely how to obey the instruction”. Stone adds finiteness of the process, and definiteness (having no ambiguity in the instructions) to this definition.
26. ^ Knuth, loc. cit
27. ^ Minsky 1967Lỗi harv: không có mục tiêu: CITEREFMinsky1967 (trợ giúp)
28. ^ Gurevich 2000:1, 3
29. ^ Sipser 2006:157
30. ^ Algorithm Design: Foundations, Analysis, and Internet Examples, ISBN 978-0-471-38365-9
31. ^ Knuth 1973:7
32. ^ Chaitin 2005:32
33. ^ Rogers 1987:1–2
34. ^ In his essay “Calculations by Man and Machine: Conceptual Analysis” Seig 2002:390 credits this distinction to Robin Gandy, cf Wilfred Seig, et al., 2002 Reflections on the foundations of mathematics: Essays in honor of Solomon Feferman, Association for Symbolic Logic, A.K. Peters Ltd, Natick, MA.
35. ^ cf Gandy 1980:126, Robin Gandy Church’s Thesis and Principles for Mechanisms appearing on pp. 123–148 in J. Barwise et al. 1980 The Kleene Symposium, North-Holland Publishing Company.
36. ^ A “robot”: “A computer is a robot that performs any task that can be described as a sequence of instructions.” cf Stone 1972:3
37. ^ Lambek’s “abacus” is a “countably infinite number of locations (holes, wires etc.) together with an unlimited supply of counters (pebbles, beads, etc). The locations are distinguishable, the counters are not”. The holes have unlimited capacity, and standing by is an agent who understands and is able to carry out the list of instructions” (Lambek 1961:295). Lambek references Melzak who defines his Q-machine as “an indefinitely large number of locations… an indefinitely large supply of counters distributed among these locations, a program, and an operator whose sole purpose is to carry out the program” (Melzak 1961:283). B-B-J (loc. cit.) add the stipulation that the holes are “capable of holding any number of stones” (p. 46). Both Melzak and Lambek appear in The Canadian Mathematical Bulletin, vol. 4, no. 3, September 1961.
38. ^ If no confusion results, the word “counters” can be dropped, and a location can be said to contain a single “number”.
39. ^ “We say that an instruction is effective if there is a procedure that the robot can follow in order to determine precisely how to obey the instruction.” (Stone 1972:6)
40. ^ cf Minsky 1967: Chapter 11 “Computer models” and Chapter 14 “Very Simple Bases for Computability” pp. 255–281 in particular
41. ^ cf Knuth 1973:3.
42. ^ But always preceded by IF–THEN to avoid improper subtraction.
43. ^ Knuth 1973:4
44. ^ Stone 1972:5. Methods for extracting roots are not trivial: see Methods of computing square roots.
45. ^ Leeuwen, Jan (1990). Handbook of Theoretical Computer Science: Algorithms and complexity. Volume A. Elsevier. tr. 85. ISBN 978-0-444-88071-0.
46. ^ John G. Kemeny và Thomas E. Kurtz 1985 Back to Basic: The History, Corruption, and Future of the Language, Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0.
47. ^ Tausworthe 1977:101
48. ^ Tausworthe 1977:142
49. ^ Knuth 1973 section 1.2.1, expanded by Tausworthe 1977 at pages 100ff and Chapter 9.1
50. ^ Heath 1908:300; Hawking’s Dover 2005 edition derives from Heath.
51. ^ ” ‘Let CD, measuring BF, leave FA less than itself.’ This is a neat abbreviation for saying, measure along BA successive lengths equal to CD until a point F is reached such that the length FA remaining is less than CD; in other words, let BF be the largest exact multiple of CD contained in BA” (Heath 1908:297)
52. ^ For modern treatments using division in the algorithm, see Hardy and Wright 1979:180, Knuth 1973:2 (Volume 1), plus more discussion of Euclid’s algorithm in Knuth 1969:293–297 (Volume 2).
53. ^ Euclid covers this question in his Proposition 1.
54. ^ “Euclid’s Elements, Book VII, Proposition 2”. Aleph0.clarku.edu. Bản gốc lưu trữ ngày 24 tháng 5 năm 2012. Truy cập ngày 20 tháng 5 năm 2012.
55. ^ While this notion is in widespread use, it cannot be defined precisely.
56. ^ Knuth 1973:13–18. He credits “the formulation of algorithm-proving in terms of assertions and induction” to R W. Floyd, Peter Naur, C.A.R. Hoare, H.H. Goldstine and J. von Neumann. Tausworth 1977 borrows Knuth’s Euclid example and extends Knuth’s method in section 9.1 Formal Proofs (pp. 288–298).
57. ^ Tausworthe 1997:294
58. ^ cf Knuth 1973:7 (Vol. I), and his more-detailed analyses on pp. 1969:294–313 (Vol II).
59. ^ Breakdown occurs when an algorithm tries to compact itself. Success would solve the Halting problem.

Ngày đăng: 30/10/2022 | Không có phản hồi

Ngày cập nhật: 30/10/2022

Thuật toán là gì? Thuật toán quan trọng như thế nào trong lập trình? Có bao nhiêu thuật toán được sử dụng trong lập trình? Nếu bạn đang thắc mắc về những vấn đề này thì đừng bỏ qua bài viết sau đây của Glints. Theo dõi ngay để hiểu rõ hơn về thuật toán nhé.

Thuật toán là gì? Thuật toán hay còn gọi là giải thuật có khá nhiều định nghĩa khác nhau. Hiểu một cách đơn giản thuật toán là một tập hợp hữu hạn bao gồm các hướng dẫn được xác định rõ ràng, bạn có thể thực hiện được bằng máy tính, thường được dùng để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.

Nói một cách dễ hiểu hơn, mỗi bài toán được ví như một chiếc hòm đựng đầy kho báu, và chìa khóa chính là “giải thuật”.Nếu sử dụng không đúng chìa bạn vẫn có thể mở được hòm kho báu, tuy nhiên sẽ mất khá nhiều thời gian và công sức, hoặc nếu mở được hòm thì kho báu bên trong cũng bị méo mó, không được toàn vẹn.

Việc sử dụng đúng chìa khóa sẽ giúp bạn dễ dàng lấy được kho báu nhanh chóng. Dĩ nhiên, mỗi hòm sẽ luôn cần đến một loại chìa khóa khác nhau, tương tự như thuật toán luôn có những giải thuật xác định.

Sẽ không có chiếc chìa khóa nào có thể mở được tất cả các hòm kho báu, và cũng không có giải thuật nào có thể giải được toàn bộ các bài toán.

Sau đây là các thuật toán cơ bản lập trình viên cần biết để hỗ trợ tốt hơn cho công việc của mình. Cùng tìm hiểu để biết được các thuật toán đó là gì nhé.

Hashing là một trong những thuật toán tham gia vào quá trình phát hiện và xác định dữ liệu thích hợp thông qua key và ID. Vai trò chính của hashing là phát hiện lỗi, quản lý bộ nhớ cache, mật mã và tra cứu, cụ thể hàm hashing được tích hợp vào khóa và cho ra các giá trị chính xác nhất.

Hàm hashing còn được sử dụng như một định danh duy nhất cho các tập dữ liệu và các phép tính toán cho người dùng để tạo ra các giá trị dữ liệu không trùng lặp. Thường hàm hashing được sử dụng trong các bộ định tuyến để lưu trữ địa chỉ IP.

Đọc thêm: C++ Là Gì? Ứng Dụng Ngôn Ngữ Lập Trình C++ Trong Thực Tế

Thuật toán tìm kiếm được áp dụng cho dãy cấu trúc dữ liệu tuyến tính hay cấu trúc dữ liệu đồ họa. Đây còn được gọi là thuật toán tìm kiếm nhị phân, giúp cho các nhà phát triển dễ dàng tìm kiếm các hiệu quả trên những tập dữ liệu đã được sắp xếp với hàm phức tạp thời gian của O (log N).

Cơ chế của thuật toán tìm kiếm nhị phân là chia danh sách thành hai nửa cho đến khi thấy được mục đích yêu cầu, sau đó dùng nó để gỡ lỗi, đặc biệt những lỗi liên quan đến git bisection.

Các nhà phát triển sử dụng thuật toán này để đặt dữ liệu theo cách có tổ chức. Các thành phần cơ bản của thuật toán QuickSort là các phần dữ liệu được dùng để so sánh với nhau nhằm xác định thứ tự tương ứng của chúng.

Mức độ phức tạp thời gian của O (nlogn) được dùng để thực hiện vào việc so sánh. Tuy nhiên, Radix Sort có kỹ thuật xử lý nhanh hơn QuickSort, lý do vì nó sắp xếp các phần tử trong một mô hình tuyến tính với độ phức tạo thời gian O (n). Các thuật toán sắp xếp khác như: sắp xếp đếm, sắp xếp hợp nhất và sắp xếp nhóm.

Thuật toán lập trình động thường là một hàm được dùng với mục đích giải quyết các vấn đề phức tạp liên quan đến trí tuệ thông qua quá trình tách các vấn đề thành các bài toán con nhỏ hơn. Sau khi đã giải quyết các bài toán rồi thì thực hiện xây dựng trở lại thành một vấn đề phức tạp đòi hỏi bộ nhớ của các kết quả nhỏ hơn để đưa ra câu trả lời cho vấn đề phức tạp ban đầu.

Thuật toán trong lập trình có thể tích hợp để ghi nhớ, thông qua đó cho phép lưu trữ các vấn đề đã được giải quyết trước đó. Trường hợp lần tiếp theo xuất hiện thì vấn đề sẽ được giải quyết nhanh hơn rất nhiều.

Đọc thêm: ASP Net Là Gì? Từ Điển A-Z Về ASP.net Framework Trong Lập Trình

Một vấn đề cực kỳ quan trọng khác mà các nhà phát triển làm việc là tìm đường dẫn. Đồ thị hóa một cách cực kỳ linh hoạt để mô tả tất cả các loại vấn đề liên quan đến mạng lưới các đối tượng riêng biệt.

Thuật toán Dijkstra là một cách tìm đường đi nhanh nhất giữa hai nút trong biểu đồ. Đây cũng chính là nền tảng của hầu hết các công việc được thực hiện trong việc tìm kiếm đường đi và được sử dụng trong mọi thứ, từ trí tuệ nhân tạo đến thiết kế trò chơi.

Thuật toán phân tích liên kết được ứng dụng chủ yếu trong lĩnh vực mạng, thuật toán nào cung cấp khả năng tương quan trong cùng một tên miền với nhiều thực thể khác nhau.

Phân tích liên kế sử dụng ma trận phức tạp và biểu diễn đồ họa nhằm liên kết các căn cứ tương tự trong cùng một miền hiện tại. Loại thuật toán cơ bản này được dùng trong các công cụ như Google, Facebook, Twitter.

Các thuật toán mã hóa phức tạp nếu được phân tích dựa trên thuật toán mô-đun sẽ trở nên đơn giản và dễ dàng hơn rất nhiều. Đối với số học mô-đun, các thông số hiện tại đang xử lý chỉ là số nguyên và các phép toán chủ yếu được dùng là cộng, trừ, nhân và chia.

Có thể nói quy trình tạo xâu luôn đặc biệt quan trọng đối với miền và phân tử mạng. Để giúp thuật toán xâu ký tự có thể phát huy hết khả năng thì các xâu phải khớp trong cùng một chuỗi dài hoặc khi xác nhận chuỗi bằng cách phân tích cú pháp qua giới hạn đã được xác định từ trước. Thuật toán phân tích cú pháp và xâu ký tự được dùng chỉ yếu trong quá trình phát triển web cho URL.

Thuật toán biến đổi Fourier được biết đến là một trong những thuật toán đơn giản nhưng rất mạnh. Loại thuật toán lập trình này được dùng để chuyển đổi tín hiệu từ tên miền thời gian sang miền tần số và ngược lại.

Hiện tại, các mạng kỹ thuật số như wifi, internet, máy tính, điện thoại, vệ tinh, bộ định vị đều sử dụng thuật toán biến đổi Fourier để vận hành.

Mã hóa Huffman là nền tảng của nén văn bản hiện đại. Nó hoạt động bằng cách xem xét tần suất các ký tự khác nhau xuất hiện trong một văn bản và sắp xếp chúng trong một cây dựa trên tần suất này.

Thuật toán các tập không giao nhau là một cấu trúc dữ liệu đóng vai trò như một cấu trúc trợ giúp một thuật toán được dùng để biểu diễn nhiều tập hợp trong mảng riêng lẻ. Và mỗi mục chính là một phần tử của nhiều tập hợp.

Do đó, các bộ tách rời được đại diện cho các phần tử được kết nối với nhau trong cùng một thuật toán đồ thị hay phân đoạn của một hình ảnh.

Thuật toán hệ số tích phân là một thuật toán cung cấp hướng dẫn từng bước cho bạn về cách lấy các thừa số nguyên tố của một số tổng hợp. Hệ số tích phân giúp bạn giải quyết các vấn đề phức tạp trong nền tảng mã hóa yêu cầu bạn phải giải quyết các số nguyên phức hợp lớn.

Đọc thêm: Abap Là Gì? Tìm Hiểu Về Ngôn Ngữ Lập Trình Có Thu nhập Khủng

Trên đây là những chia sẻ của Glints về khái niệm thuật toán là gì? Có những loại thuật toán nào được sử dụng rộng rãi trong quá trình lập trình. Mong rằng từ những chia sẻ trên bạn đọc sẽ hiểu rõ hơn về thuật toán và biết cách ứng dụng thuật toán hiệu quả cho công việc lập trình của mình.

Theo dõi Glints để xem thêm nhiều thông tin hữu ích khác nhé!

Chúng tôi rất buồn khi bài viết không hữu ích với bạn

Hãy giúp chúng tôi cải thiện bài viết này!

Làm sao để chúng tôi cải thiện bài viết này?

Có thể bạn cũng thích

Khám phá ngay 10k+ công việc mới tại GlintsNền tảng tuyển dụng hàng đầu Đông Nam Á

Lý thuyết: Bài toán và thuật toán trang 32 SGK Tin học 10>

1. Khái niệm bài toán

– Bài toán là một việc nào đó mà con người muốn máy tính thực hiện.

– Các yếu tố của một bài toán:

+ Input: Thông tin đã biết, thông tin đưa vào máy tính.

+ Output: Thông tin cần tìm, thông tin lấy ra từ máy tính.

– Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó:

+ Input: hai số nguyên dương A, B.

+ Output: ước chung lớn nhất của A và B

2. Khái niệm thuật toán

a) Khái niệm

Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.

b) Biểu diễn thuật toán

– Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành.

– Sử dụng sơ đồ khối để mô tả thuật toán.

c) Các tính chất của thuật toán

– Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác.

– Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo.

– Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

3. Một số ví dụ về thuật toán

Ví dụ 1: Kiểm tra tính nguyên tố của 1 số nguyên dương

• Xác định bài toán

– Input: N là một số nguyên dương;

– Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″.

• Ý tưởng:

– Định nghĩa: ″Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N″

– Nếu N = 1 thì N không là số nguyên tố.

– Nếu 1 < N < 4 thì N là số nguyên tố.

– N ≥ 4: Tìm ước i đầu tiên > 1 của N.

+ Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N).

+ Nếu i = N thì N là số nguyên tố.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập số nguyên dương N;

– Bước 2: Nếu N=1 thì thông báo ″N không là số nguyên tố″, kết thúc;

– Bước 3: Nếu N<4 thì thông báo ″N là số nguyên tố″, kết thúc;

– Bước 4: i ← 2;

– Bước 5: Nếu i là ước của N thì đến bước 7;

– Bước 6: i ← i+1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị)

– Bước 7: Nếu i = N thì thông báo ″N là số nguyên tố″, ngược lại thì thông báo ″N không là số nguyên tố″, kết thúc;

b) Sơ đồ khối

Lưu ý: Nếu N >= 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.

Ví dụ 2: Sắp xếp bằng cách tráo đổi

• Xác định bài toán

– Input: Dãy A gồm N số nguyên a1, a2,…, an

– Output: Dãy A được sắp xếp thành dãy không giảm.

• Ý tưởng

– Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. (Các số lớn sẽ được đẩy dần về vị trí xác định cuối dãy).

– Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần so sánh cho đến khi không có sự đổi chỗ nào xảy ra nữa.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập N, các số hạng a1, a2,…, an;

– Bước 2: M ← N;

– Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp, rồi kết thúc;

– Bước 4: M ← M – 1, i ← 0;

– Bước 5: i ← i + 1;

– Bước 6: Nếu i > M thì quay lại bước 3;

– Bước 7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;

– Bước 8: Quay lại bước 5;

b) Sơ đồ khối

Ví dụ 3: Bài toán tìm kiếm

• Xác định bài toán

– Input : Dãy A gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k (khóa)

Ví dụ : A gồm các số nguyên ″ 5 7 1 4 2 9 8 11 25 51″ và k = 2 (k = 6).

– Output: Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 2 trong dãy là 5 (không tìm thấy 6)

• Ý tưởng

Tìm kiếm tuần tự được thực hiện một cách tự nhiên: Lần lượt đi từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khóa cho đến khi gặp một số hạng bằng khóa hoặc dãy đã được xét hết mà không tìm thấy giá trị của khóa trên dãy.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;

– Bước 2: i ← 1;

– Bước 3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;

– Bước 4: i ←i+1;

– Bước 5: Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc;

– Bước 6: Quay lại bước 3;

b) Sơ đồ khối

Ví dụ 4: Tìm kiếm nhị phân

• Xác định bài toán

– Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k.

Ví dụ: Dãy A gồm các số nguyên 2 4 5 6 9 21 22 30 31 33 và k = 21 (k = 25)

– Output : Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 21 trong dãy là 6 (không tìm thấy 25)

• Ý tưởng

Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh vùng tìm kiếm bằng cách so sánh k với số hạng ở giữa phạm vi tìm kiếm (agiữa), khi đó chỉ xảy ra một trong ba trường hợp:

– Nếu agiữa= k thì tìm được chỉ số, kết thúc;

– Nếu agiữa > k thì việc tìm kiếm thu hẹp chỉ xét từ adầu (phạm vi) → agiữa – 1;

– Nếu agiữa < k việc tìm kiếm thu hẹp chỉ xét từ agiữa + 1→acuối (phạm vi).

Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên dãy A hoặc phạm vi tìm kiếm bằng rỗng.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;

– Bước 2: Đầu ←1; Cuối ←N;

– Bước 3: Giữa←[(Đầu+Cuối)/2];

– Bước 4: Nếu agiữa = k thì thông báo chỉ số Giữa, rồi kết thúc;

– Bước 5: Nếu agiữa > k thì đặt Cuối = Giữa – 1 rồi chuyển sang bước 7;

– Bước 6: Đầu ←Giữa + 1;

– Bước 7: Nếu Đầu > Cuối thì thông báo không tìm thấy khóa k trên dãy, rồi kết thúc;

– Bước 8: Quay lại bước 3.

b) Sơ đồ khối

Loigiaihay.com

• Câu 1 trang 44 SGK Tin học 10
• Câu 3 trang 44 SGK Tin học 10
• Câu 2 trang 44 SGK Tin học 10
• Câu 4 trang 44 SGK Tin học 10
• Câu 6 trang 44 SGK Tin học 10

>> Xem thêm

Các bài khác cùng chuyên mục

• Câu 6 trang 162 SGK Tin học lớp 10
• Câu 2 trang 162 SGK Tin học 10
• Lý thuyết Thực hành 10: Sử dụng trình duyệt Internet Explorer trang 152 SGK Tin học 10
• Hướng dẫn thực hành 10: Sử dụng trình duyệt Internet Explorer trang 152 SGK Tin học 10
• Bài thực hành 11: Thư điện tử và máy tìm kiếm thông tin trang 155 SGK Tin học 10

Thuật toán là một phương thức gồm tập hợp các câu lệnh hay các bước được thực hiện theo một thứ tự nhất định nhằm giải quyết một vấn đề logic nào đó. Từ thuật toán còn được gọi là Algorithm, nó được đặt theo tên của một nhà toán học người Trung Á là al’Khwarizmi. Ông là tác giả của một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng và mạch lạc cách giải những bài toán. Sau này, phương pháp này đã được xem là một chuẩn mực và được nhiều nhà toán học khác áp dụng theo.

Trong toán học và khoa học máy tính, thuật toán máy tính, hay còn gọi là giải thuật, là một tập hợp các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, nhằm giải quyết một lớp vấn đề hoặc để thực hiện một phép tính. Các thiết bị máy tính sử dụng thuật toán để thực hiện các chức năng của nó một cách rõ ràng như thực hiện các phép tính, suy luận tự động, xử lý dữ liệu (database), và các tác vụ khác.

Tìm việc làm, tuyển dụng software developer có thể bạn quan tâm:

– Software Developer (ASP.Net MVC / DotNet / Java)

– Software Developer (ReactJs/ React Native)

Thuật toán là một tập hợp các bước để giải quyết một vấn đề cụ thể. Còn cấu trúc dữ liệu là một vị trí được đặt tên và có thể được sử dụng để lưu trữ, tổ chức dữ liệu. Thuật toán và cấu trúc dữ liệu cho phép chúng ta viết các chương trình rên laptop một cách hiệu quả và tối ưu. Hai thành phần này hỗ trợ nhau, các thuật toán sẽ cần cấu trúc dữ liệu bên trong để làm cho chúng hoạt động theo đúng kỳ vọng. Ví dụ, nếu chúng ta cần sắp xếp một danh sách thì có thể sử dụng cấu trúc dữ liệu mảng để lưu trữ và dùng thuật toán để sắp xếp các phần tử trong danh sách đó theo mong muốn.

Tối ưu hóa việc tìm kiếm: thuật toán chính là chỉ dẫn để tìm thấy kết quả cho vấn đề một cách tối ưu nhất. Các lập trình viên sử dụng thuật toán để tìm ra con đường ngắn nhất để giải quyết vấn đề. Chẳng hạn, Google Map, Grab, Uber sử dụng thuật toán để tính toán quãng đường ngắn nhất, thuận tiện nhất khi hướng dẫn, hỗ trợ khách hàng di chuyển. Một ví dụ khách là Google, bạn có thể tìm bất cứ thông tin gì tại đây. Vì Google luôn cập nhật và nâng cấp thuật toán để cung cấp thông tin cho người dùng về mọi lĩnh vực, với tốc độ trả kết quả cực kỳ nhanh, chỉ trong 1 giây có thể hiển thị lên đến vài ngàn kết quả.

Khả năng bảo mật tốt: thuật toán đều được mã hóa thành các chuỗi ký tự. Khi truyền tải và nhận dữ liệu đều cần mã hóa. Vì thế, có thể giảm sự xâm nhập từ các hacker. Điều này thể hiện khả năng bảo mật tốt của thuật toán.

Tính “không mập mờ” và “có thể thực thi được” được gọi chung là tính xác định. Trong kỹ thuật phần mềm, thuật toán phải là một dãy hữu hạn các bước rõ ràng, không mập mờ và có thể thực thi được, theo đúng trình tự để ra được kết quả như ta mong muốn. Vì vậy, bất kỳ thuật toán nào cũng phải có những bước được xác định, theo một trình tự nhất định, được thiết lập ngay từ ban đầu.

Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Tính “dừng” hay hữu hạn là tính chất rất dễ bị vi phạm vì sai sót khi trình bày thuật toán. Mọi thuật toán đều nhằm thực hiện một công việc nhất định và cho ra kết quả khi thực hiện xong. Nếu thuật toán không thỏa được tính hữu hạn thì ta nói rằng thuật toán bị lặp vô tận hoặc bị quẩn, không cho ra được kết quả cuối cùng.

Khi giải một bài toán, tất nhiên chúng ta đều mong muốn đạt được kết quả đúng đắn. Và thuật toán được sinh ra chính là để tìm ra được kết quả đúng cho bài toán hay vấn đề cụ thể. Tuy nhiên tính “đúng” dù là một tính chất khá hiển nhiên nhưng cũng khó để đạt tới. Bởi vì trong thực tế, có những vấn đề mà chúng ta cần phải nghiên cứu và thử nghiệm nhiều lần mới tìm ra được thuật toán hoàn hảo nhất để đưa ra đúng kết quả.

Tính hiệu quả của thuật toán là một yếu tố được đánh giá để chọn lựa cách giải quyết cho vấn đề bài toán trên thực tế. Tính hiệu quả của thuật toán được đánh giá dựa trên các tiêu chuẩn như khối lượng tính toán, thời gian và không gian khi thi hành thuật toán. Ngoài ra, một tiêu chuẩn cũng được sử dụng nhiều để đánh giá tính hiệu quả của thuật toán đó là độ phức tạp và logic của thuật toán.

Tính tổng quát của thuật toán nói đến việc thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không chỉ áp dụng được cho một số trường hợp riêng biệt nào đó. Có thể hiểu rằng thuật toán phải giống như các công thức toán học, có thể áp dụng nhiều. Tuy nhiên trong thực tế, cũng có các thuật toán được xây dựng dành riêng cho một bài toán, một vấn đề. Vì vậy, không phải thuật toán nào cũng cần đảm bảo được tính tổng quát mà phải tùy vào trường hợp sử dụng.

– Phân tích và phác thảo thuật toán: Bước đầu tiên, chúng ta cần phân tích rõ vấn đề, sau đó hình dung được hướng giải quyết và chiến thuật thiết kế thuật toán. Để hoàn thành được này, ta cần đến khá nhiều kiến thức căn bản của môn Cấu trúc dữ liệu và giải thuật, cụ thể, tiêu biểu là 5 chiến thuật thiết kế thuật toán sau: Chia để trị – divide and conquer, Giải thuật tham ăn – Greedy Method

Lập trình quy hoạch động – Dynamic Programming, Back Tracking và Branch and Bound. Trong đó, chiến thuật chia để trị là được sử dụng phổ biến nhất.

– Kiểm tra thuật toán: Sau khi thiết kế xong thuật toán, ta cần kiểm tra tính đúng đắn của nó bằng cách đưa thuật toán vào máy tính. Sau đó, nhập input, tức tài liệu nguồn vào ở định dạng tương thích. Bước kiểm tra này là để đảm bảo thuật toán sẽ hoạt động trơn tru trên mọi ngôn từ lập trình.

– Đánh giá thuật toán: Để biết được thuật toán có hiệu quả hay không thì chúng ta cần phải đánh giá nó. Ta có thể đánh giá hiệu năng thuật toán theo 2 yếu tố là thời hạn thực thi và bộ nhớ sử dụng. Vì trong quá trình chạy thuật toán thì CPU cần tiêu tốn thời gian quyết và xử lý để thực thi những phép toán, còn bộ nhớ sẽ là nơi chứa tài liệu và chương trình thực thi.

– Test chương trình thuật toán: Việc test chương trình được thực hiện bởi các Tester sẽ chia thành 2 giai đoạn là debugging và profiling. Debugging là quá trình thực thi chương trình dựa trên một tập dữ liệu mẫu để xác định các lỗi xảy ra (loại lỗi, vị trí lỗi,…) và khắc phục chúng. Tuy nhiên giai đoạn này hầu như không bao giờ phát hiện được 100% lỗi. Profiling cũng là quá trình thực thi chương trình trên một tập dữ liệu mẫu nhưng trong giai đoạn này, người ta sẽ đo thời gian cũng như dung lượng bộ nhớ.

– Hoàn thiện thuật toán và ứng dụng: Sau khi đã hoàn tất các bước trên thì ta sẽ một lần nữa kiểm thử lại, đảm bảo thuật toán không còn lỗi hay sai sót nào. Và cuối cùng là sử dụng thuật toán để giải quyết vấn đề hay bài toán mà bạn hay công ty đang gặp phải.

Dùng ngôn ngữ tự nhiên là phương pháp biểu diễn thuật toán bằng cách mô tả các bước thực thi theo ngôn ngữ thường ngày. Phương pháp này không đòi hỏi người viết và người đọc thuật toán phải nắm các nguyên tắc. Tuy nhiên nó khiến cho việc biểu diễn thuật toán trở nên dài dòng, không trực quan, không thể hiện được cấu trúc thuật toán nên có thể gây khó hiểu hoặc hiểu lầm. Vì không có nguyên tắc nào cho phương pháp này nên nếu sử dụng thì bạn nên phân cấp từng bước theo số thứ tự một cách dễ hiểu nhất.

Hiện nay, có rất nhiều các phần mềm vẽ lưu đồ nhanh và tốt nên sẽ thuận tiện cho việc biểu diễn thuật toán. Bên cạnh đó, bạn nên áp dụng theo các thao tác sau đây để có một lưu đồ hoàn chỉnh nhất.

– Thao tác chọn lựa (decision): Thao tác chọn lựa được biểu diễn bằng một hình thoi, ở trong chứa biểu thức điều kiện.

– Thao tác xử lý (process): Thao tác xử lý được biểu diễn bằng một hình chữ nhật, ở trong chứa nội dung xử lý.

– Ðường đi (route): Để thể hiện trình tự thực hiện các thao tác, người ta sử dụng đường cung nối các bước kế tiếp nhau. Trên đường cung có mũi tên để chỉ hướng hay thứ tự thực hiện.

– Ðiểm cuối (terminator): Ðifểm cuối là điểm khởi đầu và cũng là điểm kết thúc của thuật toán, nó được biểu diễn bằng hình ovan, bên trong có ghi chữ start/begin/bắt đầu hoặc end/kết thúc. Nếu là điểm khởi đầu thì điểm cuối chỉ có cung đi ra còn là điểm kết thúc thì có cung đi vào.

– Ðiểm nối (connector): Ðiểm nối dùng để nối các phần khác nhau của một lưu đồ. Bên trong điểm nối, người ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối đó.

– Ðiểm nối sang trang (off-page connector): Điểm nối sang trang cũng giống như điểm nối nhưng nó được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang, người ta cũng đặt một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang.

Phương pháp biểu diễn thuật toán thứ ba chính là mã giả. Khi sử dụng phương pháp này để biểu diễn thuật toán, ta cần vay mượn các cú pháp của một ngôn ngữ lập trình nào đó và vẫn sử dụng một phần ngôn ngữ tự nhiên. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Phương pháp dùng mã giả để biểu diễn thuật toán vừa tận dụng được các khái niệm trong các loại ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán.

Một lập trình viên có cần thiết phải học và biết về thuật toán hay không? Bạn vẫn có thể là một lập trình viên giỏi nếu không biết thuật toán. Tuy nhiên, đây là chìa khóa giúp bạn tiết kiệm được rất nhiều thời gian và công sức. Ví dụ, nếu ai đó đưa cho bạn một dãy các số và yêu cầu bạn phải tìm xem một con số bất kỳ có nằm trong dãy số đó hay không. Nếu bạn không biết thuật toán, bạn phải làm nó theo cách thủ công. Nhưng khi bạn biết thuật toán, dù số lượng có nhiều đến đâu, bạn chỉ cần dùng thuật toán và tìm ra nó một cách dễ dàng.

Hơn nữa, việc giải thuật toán cũng giống như giải quyết các vấn đề. Khi đã thành thạo giải thuật toán, tức là kỹ năng giải quyết vấn đề của bạn đã được rèn luyện và cải thiện rất nhiều. Vì thế, doanh nghiệp luôn ưu tiên tuyển dụng những lập trình viên hiểu biết về thuật toán.

Sau đây là 10 loại thuật toán mà lập trình viên nên biết để ghi điểm với nhà tuyển dụng và tối ưu hóa quy trình làm việc:

Thuật toán Hashing: hashing là thuật toán dùng để phát hiện và xác định dữ liệu phù hợp thông qua khóa, ID. Mục đích của Hashing là tìm ra lỗi, quản lý cache, mã hóa và tra cứu. Cụ thể, hashing được tích hợp sẵn trên key để cho ra giá trị chính xác nhất. Đây cũng là mã định danh duy nhất cho bộ dữ liệu và tính toán để người dùng tạo các giá trị dữ liệu duy nhất.

Thuật toán tìm kiếm: thuật toán tìm kiếm sử dụng các cấu trúc dữ liệu tuyến tính hoặc đồ thị. Nó cho phép các nhà phát triển dễ dàng tìm thấy hiệu quả của việc sắp xếp các tập dữ liệu với các hàm có độ phức tạp thời gian O(log N).

Thuật toán sắp xếp: thuật toán sắp xếp giúp sắp đặt các dữ liệu một cách có tổ chức. Các khối xây dựng cơ bản của thuật toán sắp xếp là các phần dữ liệu được so sánh với nhau để xác định thứ tự tương ứng của chúng. Ngoài ra, còn các thuật toán sắp xếp khác như: sắp xếp đếm, sắp xếp hợp nhất và sắp xếp theo nhóm.

Thuật toán lập trình động: là thuật toán dùng để giải các bài toán trí tuệ phức tạp thông qua quá trình phân rã bài toán thành các bài toán con nhỏ hơn. Khi vấn đề được giải quyết, việc xây dựng lại một câu hỏi phức tạp đòi hỏi phải ghi nhớ các kết quả nhỏ hơn để trả lời câu hỏi phức tạp ban đầu. Lần sau nếu có vấn đề phát sinh, nó sẽ được giải quyết nhanh hơn nhiều.

Thuật toán Dijkstra: đây là một phương pháp dùng để tìm ra cách di chuyển nhanh nhất giữa 2 vị trí. Nó được áp dụng cho phổ biến các ứng dụng tìm đường, vận chuyển ngày nay hoặc trong trí tuệ nhân tạo, các trò chơi.

Thuật toán phân tích liên kết: được sử dụng chủ yếu trong lĩnh vực mạng, nhằm tăng khả năng liên kết với nhiều thực thể khác nhau trong cùng một miền.Thuật toán liên kết sử dụng các ma trận phức tạp và biểu diễn đồ họa để liên kết các thành phần tương tự trong cùng một miền. Thuật toán này được các ông lớn như Google, Facebook, Twitter,… sử dụng.

Thuật toán Mô-đun: thuật toán mô-đun giúp các bài toán phức tạp trở nên dễ dàng hơn. Các thông số được thuật toán mô-đun giải quyết là các số nguyên, thông qua phép tính chủ yếu là cộng, trừ, nhân, chia

Thuật toán biến đổi Fourier: thuật toán này tuy đơn giản nhưng có tác dụng rất lớn. Nó được dùng để chuyển đổi tín hiệu từ tên miền thời gian sang miền tần số và được áp dụng cho các mạng kỹ thuật số hiện nay như: wifi, internet, máy tính, điện thoại, vệ tinh, bộ định vị đều sử dụng thuật toán biến đổi Fourier để vận hành.

Thuật toán các tập không giao nhau: là một cấu trúc trợ giúp thuật toán, được dùng để biểu diễn nhiều tập hợp trong mảng riêng lẻ. Và mỗi mục chính là một phần tử của nhiều tập hợp

Hệ số tích phân: dùng để hướng dẫn từng bước về cách lấy các thừa số nguyên tố của một số tổng hợp. Hệ số tích phân dùng để giải quyết các vấn đề phức tạp trong nền tảng mã hóa yêu cầu bạn phải giải quyết các số nguyên phức hợp lớn.

Xem thêm:

– Cách viết CV xin việc ngành IT, CNTT đơn giản mà chuẩn nhất

– ICT là gì? Ứng dụng trong ngành IT và mọi lĩnh vực đời sống

– Tuyển tập bài test và bộ câu hỏi phỏng vấn IT thường gặp

Hy vọng rằng, qua bài viết này bạn đã có cái nhìn rõ ràng hơn về thuật toán để áp dụng trong công việc của mình. Nếu thấy bài viết này hay và có ích thì đừng quên chia sẻ hoặc bình luận bên dưới nhé!

Nguồn tham khảo: https://vi.wikipedia.org/wiki/Thuật_toán

Áp dụng vào bài toán

Bây giờ, ta cùng xem một ví dụ về đề bài trong các cuộc thi lập trình thi đấu:

Một đề bài trên trang web lập trình codeforces.com

Những đề bài như trên rất phổ biến ở các trang web lập trình online, và đôi khi là cả ở các đề thi HSG cấp quận (huyện), tỉnh (thành phố), quốc gia,…Nó cho chúng ta biết giới hạn thời gian và không gian của bài toán:

• Giới hạn thời gian (Time limit per test): giây.
• Giới hạn không gian (Memory limit per test): Megabytes.

Những ràng buộc này cho chúng ta biết, chương trình phải cho ra kết quả sau tối đa 2 giây, và bộ nhớ sử dụng không được vượt quá Megabytes. Để tính toán, trước hết ta sẽ tính độ phức tạp thời gian và không gian của thuật toán đã cài đặt, giả sử lần lượt là và . Sau đó, dựa vào một số kiến thức dưới đây để cải tiến thuật toán nếu cần:

• Thời gian thực thi thuật toán sẽ giây nếu như .
• Không gian sử dụng sẽ bằng tích giữa và kích thước của kiểu dữ liệu đầu vào. Chẳng hạn, và có kiểu dữ liệu
  
long long

  , ta sẽ tính được không gian sử dụng là khoảng bytes, tương đương với khoảng gần Megabytes – hoàn toàn đáp ứng được ràng buộc. Thông thường, giới hạn không gian cho phép trong các bài toán là khoảng Megabytes, vì vậy nên nếu là kiểu
  
int

  , và khoảng nếu là kiểu
  
long long

  .

Sau khi tính toán được các yếu tố trên, các bạn sẽ tối ưu lại thuật toán để thỏa mãn được các ràng buộc.

Tài liệu tham khảo

All rights reserved

Thuật toán

Trong toán học và khoa học máy tính, một thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.[1][2] Các thuật toán luôn rõ ràng và được sử dụng chỉ rõ việc thực hiện các phép tính, xử lý dữ liệu, suy luận tự động và các tác vụ khác.

Là một phương pháp hiệu quả, một thuật toán có thể được biểu diễn trong một khoảng không gian và thời gian hữu hạn,[3] và bằng một ngôn ngữ hình thức được xác định rõ ràng [4] để tính toán một hàm số.[5] Bắt đầu từ trạng thái ban đầu và đầu vào ban đầu (có thể trống),[6] các hướng dẫn mô tả một phép tính, khi được thực thi, sẽ tiến hành qua một số [7] hữu hạn các trạng thái kế tiếp được xác định rõ, cuối cùng tạo ra “đầu ra” [8] và chấm dứt ở 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.[9]

Khái niệm thuật toán đã tồn tại từ thời cổ đại. Các thuật toán số học, chẳng hạn như thuật toán chia, được sử dụng bởi các nhà toán học Babylon cổ đại vào khoảng 2500 TCN và các nhà toán học Ai Cập vào khoảng 1550 TCN.[10] Các nhà toán học Hy Lạp sau đó đã sử dụng các thuật toán trong sàng Eratosthenes để tìm số nguyên tố,[11] và thuật toán Euclide để tìm ước chung lớn nhất của hai số.[12] Các nhà toán học Ả Rập như al-Kindi vào thế kỷ thứ 9 đã sử dụng các thuật toán mật mã để phá mã, dựa trên phân tích tần số.[13]

Bản thân từ thuật toán (algorithm) từ bắt nguồn từ nhà toán học thế kỷ thứ 9 Muḥammad ibn Mūsā al-Khwārizmī, tên ông được Latinh hóa thành Algoritmi.[14] Việc chính thức hóa một phần những gì sẽ trở thành khái niệm thuật toán hiện đại bắt đầu với nỗ lực giải Entscheidungsproblem (vấn đề quyết định) do David Hilbert đặt ra vào năm 1928. Các công thức hóa sau này được đóng khung như những nỗ lực để xác định ” khả năng tính toán hiệu quả ” [15] hoặc “phương pháp hiệu quả”.[16] Những công thức hóa đó bao gồm các hàm đệ quy Gödel – Herbrand – Kleene của các năm 1930, 1934 và 1935, phép tính lambda của Alonzo Church năm 1936, Công thức 1 của Emil Post năm 1936 và các máy Turing của Alan Turing năm 1936–37 và 1939.

Phân tích ví dụ

Ví dụ 1: Phân tích độ phức tạp thuật toán của đoạn chương trình sau


#include

using namespace std; int main() { int n; // (1) cin >> n; // (2) int s1 = 0; // (3) for (int i = 1; i <= n; ++i) // (4) s1 += i; // (5) int s2 = 0; // (6) for (int i = 1; i <= n; ++i) // (7) s2 += i * i; // (8) cout << s1 << endl << s2; // (9) return 0; }



Thời gian thực hiện chương trình trên phụ thuộc vào số . Ta phân tích chi tiết:

• Các lệnh đều có thời gian thực hiện là .
• Vòng
  
for

  số có số lần lặp là và câu lệnh ở phần thân (là câu lệnh ) có thời gian thực hiện . Vậy cả vòng lặp có thời gian thực hiện là . Tương tự với vòng lặp số .

Vậy thời gian thực hiện của cả thuật toán là:

Về độ phức tạp không gian, ta nhận thấy đoạn chương trình hoàn toàn sử dụng các biến đơn không hề phụ thuộc vào giá trị input :

• Biến : Chỉ có một biến nguyên được sử dụng, không phụ thuộc vào đầu vào độ phức tạp không gian của biến này là .
• Các biến và : Vì chúng chỉ được sử dụng trong các vòng lặp và không lưu trữ thông tin nào sau khi vòng lặp kết thúc, không có đóng góp vào độ phức tạp không gian cuối cùng. Độ phức tạp không gian của các biến này cũng là .
• Biến : Đây là biến đại diện cho giá trị đầu vào của chương trình. Biến này chỉ lưu trữ một giá trị nguyên và không phụ thuộc vào kích thước của dữ liệu đầu vào. Do đó, độ phức tạp không gian của biến này cũng là .

Vì vậy độ phức tạp bộ nhớ có thể coi là .

Ví dụ 2: Phân tích độ phức tạp thuật toán của đoạn chương trình sau


#include

using namespace std; int main() { int sum = 0; // (1) for (int i = 1; i <= N; ++i) // (2) for (int j = 1; j <= i; ++j) // (3) sum = sum + 1; // (4) cout << sum; // (5) }



Đoạn chương trình trên có thời gian thực hiện phụ thuộc vào số . Phân tích chi tiết:

• Câu lệnh và có thời gian thực hiện .
• Câu lệnh có thời gian thực hiện .
• Ứng với mỗi giá trị của câu lệnh lặp thì:
  • Khi lệnh lặp thực hiện lần.
  • Khi lệnh lặp thực hiện lần.
  • Khi lệnh lặp thực hiện lần. Như vậy, lệnh lặp có số lần thực hiện là từ đó suy ra cả lệnh lặp có thời gian thực hiện là .

Cả chương trình có thời gian thực hiện là .

Độ phức tạp không gian cũng vẫn là do đoạn chương trình chỉ sử dụng các biến đơn.

Ví dụ 3: Phân tích độ phức tạp thuật toán của đoạn chương trình sau:


#include

using namespace std; const int maxn = 1000; int a[maxn + 1][maxn + 1]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j]; // Tính tổng đường chéo chính của ma trận. int sum = 0; for (int i = 1; i <= n; ++i) sum += a[i][i]; cout << sum; return 0; }



Đoạn chương trình trên dùng để tính tổng các phần tử trên đường chéo chính của một ma trận vuông.

Về độ phức tạp thời gian, ta có thể thấy hai vòng lặp lồng nhau dùng để nhập ma trận là tốn nhiều thời gian thực thi nhất, vì vậy thời gian tổng quát của thuật toán là .

Về độ phức tạp bộ nhớ, ta thấy đoạn chương trình khai báo một mảng hai chiều kích thước còn lại đều là các biến đơn. Như vậy độ phức tạp bộ nhớ tổng quát là .

Phương pháp đánh giá bằng lý thuyết

Trong lập trình thi đấu, người ta sẽ đánh giá độ phức tạp thuật toán bằng phương pháp lý thuyết. Trong phương pháp này, ta quan tâm tới yêu tố kích thước của dữ liệu đầu vào, thông thường là một con số . Mối liên hệ giữa yếu tố này và số lượng các phép tính toán cũng như kích thước bộ nhớ lưu trữ để tìm ra được kết quả của bài toán gọi chung là độ phức tạp thuật toán (chứ không phải thời gian cụ thể như hay giây). Ta sử dụng hai hàm số và để biểu diễn thời gian thực hiện của thuật toán và không gian lưu trữ của thuật toán với dữ liệu đầu vào kích thước là .

Độ lớn của hàm được biểu diễn bằng một hàm với và là hai hàm số thực không âm. Nếu một thuật toán có thời gian thực hiện là thì ta nói thuật toán đó có thời gian thực hiện cấp . Nói một cách dễ hiểu, sẽ biểu diễn số phép tính tối đa cần thực hiện trong thuật toán với một bộ dữ liệu đầu vào cấp chẳng hạn trong bài toán kiểm tra tính nguyên tố của số nếu là số nguyên tố thì thuật toán sẽ phải thực hiện nhiều lần thử nhất.

Còn độ lớn của hàm cũng được biểu diễn bằng một hàm với và là hai hàm số thực không âm. Nếu một thuật toán tiêu tốn bộ nhớ thì ta nói thuật toán đó có không gian lưu trữ cấp . Một cách đơn giản hơn, sẽ biểu diễn tổng dung lượng bộ nhớ cần sử dụng trong thuật toán với một bộ dữ liệu đầu vào cấp . Trong bài toán kiểm tra tính nguyên tố của số mỗi biến khai báo ra đều đóng góp vào vì chúng đều tiêu tốn bộ nhớ của chương trình.

Keywords searched by users: khái niệm thuật toán

Categories: Phát hiện thấy 49 Khái Niệm Thuật Toán

See more here: kientrucannam.vn

See more: https://kientrucannam.vn/vn/