Các thuật toán bằng tiếng Anh đơn giản: độ phức tạp thời gian và ký hiệu Big-O

Mọi nhà phát triển giỏi đều có thời gian trong tâm trí của họ. Họ muốn cung cấp cho người dùng nhiều hơn nữa, để họ có thể làm tất cả những điều họ thích. Họ làm điều này bằng cách giảm thiểu sự phức tạp về thời gian .

Trước khi bạn có thể hiểu được độ phức tạp về thời gian trong lập trình, bạn phải hiểu nơi nó được áp dụng phổ biến nhất: trong thiết kế các thuật toán .

Vậy thuật toán là gì?

Nói một cách đơn giản, thuật toán là một chuỗi các bước có sẵn, mà bạn làm theo để đạt được một số mục tiêu hoặc để tạo ra một số đầu ra. Hãy lấy ví dụ về công thức làm bánh của bà bạn. Chờ đã, đó có tính là một thuật toán không? Chắc chắn rồi!

function BakeCake(flavor, icing){ " 1. Heat Oven to 350 F 2. Mix flour, baking powder, salt 3. Beat butter and sugar until fluffy 4. Add eggs. 5. Mix in flour, baking powder, salt 6. Add milk and " + flavor + " 7. Mix further 8. Put in pan 9. Bake for 30 minutes 10." + if(icing === true) return 'add icing' + " 10. Stuff your face " } BakeCake('vanilla', true) => deliciousness

Các thuật toán rất hữu ích trong việc kiểm tra độ phức tạp của thời gian vì chúng có đủ hình dạng và kích thước.

Theo cách tương tự, bạn có thể cắt miếng bánh theo 100 cách khác nhau, bạn có thể giải một bài toán duy nhất bằng nhiều thuật toán khác nhau. Một số giải pháp chỉ hiệu quả hơn, tốn ít thời gian hơn và yêu cầu ít không gian hơn những giải pháp khác.

Vì vậy, câu hỏi chính là: làm thế nào để chúng ta đi phân tích các giải pháp nào là hiệu quả nhất?

Toán học để giải cứu! Phân tích độ phức tạp thời gian trong lập trình chỉ là một cách toán học cực kỳ đơn giản để phân tích thời gian một thuật toán với một số đầu vào nhất định (n) sẽ mất để hoàn thành nhiệm vụ của nó. Nó thường được định nghĩa bằng ký hiệu Big-O .

Bạn hỏi ký hiệu Big O là gì?

Nếu bạn hứa rằng bạn sẽ không bỏ cuộc và ngừng đọc, tôi sẽ nói với bạn.

Ký hiệu Big-O là một cách chuyển đổi các bước tổng thể của một thuật toán thành các thuật ngữ đại số, sau đó loại trừ các hằng số và hệ số bậc thấp hơn không có tác động lớn đến độ phức tạp tổng thể của bài toán.

Các nhà toán học có thể sẽ hơi chùn bước trước giả định “tác động tổng thể” của tôi ở đó, nhưng để các nhà phát triển tiết kiệm thời gian, đơn giản hóa mọi thứ theo cách này sẽ dễ dàng hơn:

Regular Big-O 2 O(1) --> It's just a constant number 2n + 10 O(n) --> n has the largest effect 5n^2 O(n^2) --> n^2 has the largest effect

Tóm lại, tất cả những gì ví dụ này đang nói là: chúng ta chỉ xem xét yếu tố trong biểu thức của chúng ta có tác động lớn nhất đến giá trị mà biểu thức của chúng ta sẽ trả về. (Điều này thay đổi khi hằng số trở nên cực lớn và n trở nên nhỏ, nhưng chúng ta đừng lo lắng về điều đó ngay bây giờ).

Dưới đây là một số phức tạp về thời gian phổ biến với các định nghĩa đơn giản. Tuy nhiên, vui lòng xem Wikipedia để biết các định nghĩa chuyên sâu hơn.

  • O (1) - Thời gian không đổi: Cho một đầu vào có kích thước n, chỉ cần một bước duy nhất để thuật toán hoàn thành nhiệm vụ.
  • O (log n) - Logarit thời gian: cho đầu vào có kích thước n, số bước cần thiết để hoàn thành nhiệm vụ được giảm đi một số yếu tố với mỗi bước.
  • O (n) - Thời gian tuyến tính: Cho đầu vào có kích thước n, số bước cần thiết có liên quan trực tiếp (1 đến 1)
  • O (n²) - Thời gian bậc hai: Cho đầu vào có kích thước n, số bước cần thực hiện để hoàn thành một nhiệm vụ là bình phương của n.
  • O (C ^ n) - Thời gian theo cấp số nhân: Cho đầu vào có kích thước n, số bước cần thực hiện để hoàn thành một nhiệm vụ là một hằng số đối với lũy thừa n (số khá lớn).

Với kiến ​​thức này trong tay, hãy xem số bước mà mỗi sự phức tạp về thời gian này đòi hỏi:

let n = 16; O (1) = 1 step "(awesome!)" O (log n) = 4 steps "(awesome!)" -- assumed base 2 O (n) = 16 steps "(pretty good!)" O(n^2) = 256 steps "(uhh..we can work with this?)" O(2^n) = 65,536 steps "(...)"

Như bạn có thể thấy, mọi thứ có thể dễ dàng trở thành những thứ tự phức tạp hơn tùy thuộc vào độ phức tạp của thuật toán của bạn. May mắn thay, máy tính đủ mạnh để xử lý các công việc phức tạp thực sự lớn một cách tương đối nhanh chóng.

Vậy làm cách nào để phân tích mã của chúng ta với ký hiệu Big-O?

Đây là một số ví dụ nhanh chóng và đơn giản về cách bạn có thể áp dụng kiến ​​thức này vào các thuật toán mà bạn có thể gặp phải trong tự nhiên hoặc tự viết mã.

Chúng tôi sẽ sử dụng các cấu trúc dữ liệu bên dưới cho các ví dụ của chúng tôi:

var friends = { 'Mark' : true, 'Amy' : true, 'Carl' : false, 'Ray' : true, 'Laura' : false, } var sortedAges = [22, 24, 27, 29, 31]

O (1) - Thời gian không đổi

Giá trị tra cứu khi bạn biết khóa (đối tượng) hoặc chỉ mục (mảng) luôn thực hiện một bước và do đó là thời gian không đổi.

//If I know the persons name, I only have to take one step to check: function isFriend(name){ //similar to knowing the index in an Array return friends[name]; }; isFriend('Mark') // returns True and only took one step function add(num1,num2){ // I have two numbers, takes one step to return the value return num1 + num2 }

O (log n) - Thời gian lôgarit

Nếu bạn biết mặt nào của mảng để tìm một mục, bạn sẽ tiết kiệm thời gian bằng cách cắt bỏ nửa còn lại.

//You decrease the amount of work you have to do with each step function thisOld(num, array){ var midPoint = Math.floor( array.length /2 ); if( array[midPoint] === num) return true; if( array[midPoint]  only look at second half of the array if( array[midpoint] > num ) --> only look at first half of the array //recursively repeat until you arrive at your solution } thisOld(29, sortedAges) // returns true //Notes //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation. //This solution works because our Array is sorted //Recursive solutions are often logarithmic //We'll get into recursion in another post!

O (n) - Giờ tuyến tính

Bạn phải xem mọi mục trong mảng hoặc danh sách để hoàn thành nhiệm vụ. Các vòng lặp for đơn hầu như luôn luôn là thời gian tuyến tính. Ngoài ra các phương thức mảng như indexOf cũng là thời gian tuyến tính. Bạn chỉ được tóm tắt khỏi quy trình lặp.

//The number of steps you take is directly correlated to the your input size function addAges(array){ var sum = 0; for (let i=0 ; i < array.length; i++){ //has to go through each value sum += array[i] } return sum; } addAges(sortedAges) //133

O (n²) - Giờ bậc hai

Các vòng lặp for lồng nhau là thời gian bậc hai, vì bạn đang chạy một phép toán tuyến tính trong một phép toán tuyến tính khác (hoặc n * n = n²).

//The number of steps you take is your input size squared function addedAges(array){ var addedAge = []; for (let i=0 ; i < array.length; i++){ //has to go through each value for(let j=i+1 ; j < array.length ; j++){ //and go through them again addedAge.push(array[i] + array[j]); } } return addedAge; } addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ] //Notes //Nested for loops. If one for loop is linear time (n) //Then two nested for loops are (n * n) or (n^2) Quadratic!

O (2 ^ n) - Thời gian theo cấp số nhân

Thời gian theo cấp số nhân thường dành cho những tình huống mà bạn không biết nhiều và bạn phải thử mọi cách kết hợp hoặc hoán vị có thể.

//The number of steps it takes to accomplish a task is a constant to the n power //Thought example //Trying to find every combination of letters for a password of length n

Bạn nên thực hiện phân tích độ phức tạp về thời gian bất cứ khi nào bạn viết mã chạy nhanh.

Khi bạn có nhiều lộ trình khác nhau để giải quyết một vấn đề, chắc chắn sẽ khôn ngoan hơn nếu tạo ra một giải pháp hiệu quả trước. Nhưng về lâu dài, bạn sẽ muốn một giải pháp chạy nhanh và hiệu quả nhất có thể.

Để giúp bạn trong quá trình giải quyết vấn đề, đây là một số câu hỏi đơn giản để hỏi:

1. Điều này có giải quyết được vấn đề không? =>

2. Bạn có thời gian để làm việc này không

=> chuyển sang bước 3

Không => Quay lại sau và chuyển sang bước 6 ngay bây giờ.

3. Nó có bao gồm tất cả các trường hợp cạnh không? =>

4. Mức độ phức tạp của tôi càng thấp càng tốt?

Không => viết lại hoặc sửa đổi thành giải pháp mới -> quay lại bước 1

=> chuyển sang bước 5

5. Mã của tôi có KHÔ không? =>

6. Hãy vui mừng!

No => Make it D.R.Y, then rejoice!

Analyze time complexity any and all times you are trying to solve a problem. It’ll make you a better developer in the log run. Your teammates and users will love you for it.

Again, most problems you will face as programmer — whether algorithmic or programmatic — will have tens if not hundreds of ways of solving it. They may vary in how they solve the problem, but they all still solve that problem.

You could be making decisions between whether to use sets or graphs to store data. You could be deciding whether or not to use Angular, React, or Backbone for a team project. All of these solutions solve the same problem in a different way.

Given this, it’s hard to say there is a single “right” or “best” answer to these problems. But it is possible to say there are “better” or “worse” answers to a given problem.

Using one of our previous examples, it might be better to use React for a team project if half your team has experience with it, so it’ll take less time to get up and running.

The ability to describe a better solution usually springs from some semblance of time complexity analysis.

In short, if you’re going to solve a problem, solve it well. And use some Big-O to help you figure out how.

Here’s a final recap:

  • O(1) — Constant Time: it only takes a single step for the algorithm to accomplish the task.
  • O(log n) — Logarithmic Time: The number of steps it takes to accomplish a task are decreased by some factor with each step.
  • O (n) - Thời gian tuyến tính: Số lượng các bước cần thiết có liên quan trực tiếp (1 đến 1).
  • O (n²) - Thời gian bậc hai: Số bước cần thực hiện để hoàn thành một nhiệm vụ là bình phương của n.
  • O (C ^ n) - Hàm mũ: Số bước cần thực hiện để hoàn thành một nhiệm vụ là một hằng số đối với lũy thừa n (một số khá lớn).

Và đây là một số tài nguyên hữu ích để tìm hiểu thêm:

  • Wikipedia
  • Big O Cheat Sheet là một nguồn tài nguyên tuyệt vời với độ phức tạp thời gian thuật toán phổ biến và biểu diễn đồ họa. Kiểm tra nó ra!