Những gì họ thường không dạy trong bootcamps. Triển khai thực tế của các thuật toán phổ biến trong JavaScript thành ngữ.

Tôi sẽ giới thiệu cho bạn cách nghĩ về các thuật toán, cách ước tính chúng, tối ưu hóa chúng, đệ quy và tất cả những thứ bạn cần biết với tư cách là một kỹ sư JavaScript đáng tin cậy . Những điều tôi ước tôi biết sớm hơn trong sự nghiệp của mình khi phỏng vấn.

Thư giãn, dành thời gian của bạn và tận hưởng.

Thuật toán là gì?

• Nó là một tập hợp các hướng dẫn để giải quyết một vấn đề.
• Là một kỹ sư, công việc / mục tiêu của bạn là giải quyết các vấn đề
• Khi giải quyết vấn đề, bạn xác định các mẫu / kỹ thuật hiệu quả hơn / hoạt động tốt hơn
• Hãy nhớ rằng có nhiều cách để giải quyết một vấn đề, nhưng cách nào là nhanh nhất khi lượng dữ liệu đầu vào để xử lý tăng lên?

• Độ phức tạp về thời gian là số lượng hoạt động nguyên thủy được thực thi trong một thuật toán khi dữ liệu được cung cấp cho nó
• Nó giúp suy luận về tốc độ của một thuật toán
  - Đó là ước tính về thời gian cần thiết để thực thi một thuật toán khi dữ liệu đầu vào tăng lên
  - Đó là ước tính gần đúng vì bạn không thể dự đoán chính xác thời gian một thuật toán sẽ thực thi trên mọi loại kiến trúc máy / môi trường / cấu hình phần cứng / v.v.
  Vì vậy, thay vì sử dụng giây hoặc mili giây, hệ số tăng trưởng được sử dụng để cho biết một thuật toán có xu hướng phát triển bao nhiêu khi bạn cung cấp dữ liệu cho nó.
• Tóm lại, độ phức tạp về thời gian là số lượng phép toán nguyên thủy được thực thi để giải quyết một vấn đề khi đầu vào tăng lên và trong trường hợp xấu nhất .
• Suy nghĩ về chi phí của các hoạt động được thực hiện. Thuật toán càng nhanh thì càng có nhiều dữ liệu có thể xử lý trong thời gian hợp lý.

• Độ phức tạp của không gian là lượng bộ nhớ được sử dụng đối với kích thước đầu vào khi thực thi một thuật toán

Giả sử bạn có một danh sách các nhà cung cấp VPN trên một nền tảng. Bạn muốn giải quyết cho những cái đắt nhất và rẻ nhất. Hãy nhớ rằng các nhà cung cấp tiếp tục được thêm vào hàng ngày, vì vậy danh sách tiếp tục tăng lên.

const vpnProviders = [
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 { name: 'tatoVpn', price: 99 },
 { name: 'tutoVpn', price: 54 },
 ...
];

Khi bạn xem qua danh sách, bạn sẽ theo dõi giá cao nhất và thấp nhất cho mỗi lần lặp lại.

Hãy xem mô tả khi tìm kiếm giá đắt nhất:

       |  234  |  321  |  99  |  54  |
--------------------------------------
  234  |  --   |  321  |  234 |  234 |
--------------------------------------
  321  |  321  |  --   |  321 |  321 |
--------------------------------------
   99  |  234  |  321  |  --  |  99  |
--------------------------------------
   54  |  234  |  321  |  99  |  --  |

 # of providers (n)  |   4  |  11  |  100     |  2000      |
------------------------------------------------------------
 # of operations     |  16  |  121 |  10,000  |  4,000,000 |

• khi số lượng n nhà cung cấp tăng lên, số lượng hoạt động tăng theo sức mạnh của hai (hoạt động 4², 11², 100²).
• vì vậy về cơ bản, dữ liệu của bạn càng phát triển, thì công việc càng lớn sẽ cần

      |  234  |  321   |  ...  |  99  |  54  |
----------------------------------------------
max?  |  234  |  321   |  ...  |  321 |  321 |

      |  234  |  321   |  ...  |  99  |  54  |
- --------------------------------------------
min?  |  234   |  234  |  ...  |  99  |  54  |

• Mỗi mục trong danh sách chỉ được xem một lần trong lần lặp vòng lặp và nó được lưu trữ nếu đáp ứng điều kiện (là tối đa, là tối thiểu)
• ở đây, độ phức tạp về thời gian là tuyến tính ( ở đây, 2n) vì hai vòng lặp khác nhau xem xét tất cả các mục một lần
• số lượng các thao tác cần thực hiện gấp đôi số lượng mục hay nói một cách đơn giản là khi dữ liệu phát triển, công việc sẽ tăng lên 2.

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   8  |   22 |  200  |  4,000 |

const vpnProviders = [
 { name: 'tutoVpn', price: 54 },
 { name: 'tatoVpn', price: 99 },
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 ...
];

• không cần vòng lặp, chỉ cần 2 thao tác, đặt giá trị đầu tiên là giá trị nhỏ nhất và đặt giá trị cuối cùng là giá trị lớn nhất
• do đó, độ phức tạp về thời gian của thuật toán có sự tăng trưởng không đổi bởi vì bất kể số lượng n mục nào, số lượng hoạt động vẫn như nhau

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   2 |    2  |    2  |   2    |

• Sự tăng trưởng độ phức tạp về thời gian được biểu thị bằng ký hiệu O lớn
• cho đến nay, chúng ta đã thấy:
  - Độ phức tạp thời gian bậc hai được biểu thị bằng O (n²)
  - Độ phức tạp thời gian tuyến tính được biểu thị bằng O (n)
  - Độ phức tạp thời gian không đổi được biểu thị bằng O (1)
• Vì độ phức tạp tme là một phép gần đúng, các số không đáng kể bị loại bỏ do đó độ phức tạp thời gian của 2n chỉ là O (n) chứ không phải O (2n)
• Các yếu tố bị loại bỏ:
  - 5n là O (n) [phát âm là "o của n"]
  - 24n² là O (n²) [phát âm là "o của n hình vuông"]
• đây là một biểu diễn đồ họa của sự tăng trưởng:

• biết độ phức tạp về thời gian giúp bạn hiểu giới hạn của một thuật toán về lượng dữ liệu mà nó có thể chịu được trước khi mất một triệu năm để hoàn thành
• Nó cũng giúp cân bằng giữa việc chọn một thuật toán so với các thuật toán khác dựa trên các điều kiện nhất định
• khái niệm về tính đúng của thuật toán là về sự lựa chọn của bạn về một thuật toán, nó có phải là giải pháp tối ưu / đúng nhất không?

• chú ý với độ phức tạp thời gian logarit (O (log n)) , bạn càng cung cấp nhiều dữ liệu thì thuật toán càng phải làm ít công việc hơn, nhưng cũng lưu ý rằng lúc đầu nó mất nhiều thời gian hơn độ phức tạp thời gian bậc hai
• do đó, từ rất hiệu quả đến cực kỳ chậm, bạn có:
  - Độ phức tạp thời gian nhanh chóng C được biểu thị bằng O (1)
  - Độ phức tạp thời gian hàm số L được biểu thị bằng O (log n)
  - Độ phức tạp thời gian tuyến tính được biểu thị bằng O (n)
  - Độ phức tạp thời gian bậc hai được biểu thị bằng O (n²)
  - Độ phức tạp thời gian C được biểu thị bằng O (n³)
  - Độ phức tạp thời gian hàm mũ được biểu thị bằng O (k)