Các cấu trúc dữ liệu tích hợp trong Python như danh sách, bộ, từ điển cung cấp một số lượng lớn các thao tác giúp viết mã ngắn gọn dễ dàng hơn nhưng không nhận thức được sự phức tạp của chúng có thể dẫn đến hành vi chậm không mong muốn của mã python của bạn.
Prerequisite: List, Dictionaries, Sets
Ví dụ.
Tra cứu từ điển đơn giản Hoạt động có thể được thực hiện bởi một trong hai.
if key in d:
hoặc là
if dict.get[key]
Cái đầu tiên có độ phức tạp về thời gian là O[N] cho Python2, O[1] cho Python3 và cái sau có O[1] có thể tạo ra nhiều khác biệt trong các câu lệnh lồng nhau.
Thuật toán là một tập hợp các hướng dẫn được xác định rõ ràng để giải quyết một vấn đề cụ thể. Bạn có thể giải quyết những vấn đề này theo nhiều cách khác nhau
Điều này có nghĩa là phương pháp bạn sử dụng để đi đến cùng một giải pháp có thể khác với phương pháp của tôi, nhưng cả hai chúng ta sẽ nhận được cùng một kết quả
Vì có nhiều cách khác nhau để giải quyết một vấn đề, nên phải có một cách để đánh giá các giải pháp hoặc thuật toán này về hiệu suất và hiệu quả [thời gian để thuật toán của bạn chạy/thực thi và tổng dung lượng bộ nhớ mà nó sẽ tiêu thụ]
Điều này rất quan trọng đối với các lập trình viên để đảm bảo rằng các ứng dụng của họ chạy đúng cách và giúp họ viết mã sạch.
Đây là nơi Ký hiệu Big O đi vào hình ảnh. Ký hiệu Big O là thước đo để xác định hiệu quả của thuật toán. Nó cho phép bạn ước tính thời gian mã của bạn sẽ chạy trên các bộ đầu vào khác nhau và đo lường mức độ hiệu quả của mã của bạn khi kích thước đầu vào của bạn tăng lên
Big O là gì?
Big O, còn được gọi là ký hiệu Big O, thể hiện độ phức tạp trong trường hợp xấu nhất của thuật toán. Nó sử dụng các thuật ngữ đại số để mô tả độ phức tạp của một thuật toán
Big O xác định thời gian chạy cần thiết để thực thi thuật toán bằng cách xác định hiệu suất của thuật toán sẽ thay đổi như thế nào khi kích thước đầu vào tăng lên. Nhưng nó không cho bạn biết thời gian chạy thuật toán của bạn nhanh như thế nào
Ký hiệu Big O đo lường hiệu quả và hiệu suất của thuật toán của bạn bằng cách sử dụng độ phức tạp về thời gian và không gian
Thời gian và không gian phức tạp là gì?
Một yếu tố cơ bản chính ảnh hưởng đến hiệu suất và hiệu quả của chương trình là phần cứng, hệ điều hành và CPU bạn sử dụng
Nhưng bạn không xem xét điều này khi bạn phân tích hiệu suất của thuật toán. Thay vào đó, độ phức tạp về thời gian và không gian như một hàm của kích thước đầu vào mới là điều quan trọng
Độ phức tạp về thời gian của thuật toán xác định thời gian cần thiết để thực hiện thuật toán dưới dạng một hàm của kích thước đầu vào của nó. Tương tự, độ phức tạp không gian của thuật toán chỉ định tổng dung lượng hoặc bộ nhớ cần thiết để thực thi thuật toán dưới dạng hàm của kích thước đầu vào
Chúng tôi sẽ tập trung vào độ phức tạp của thời gian trong hướng dẫn này. Đây sẽ là một cheatsheet chuyên sâu giúp bạn hiểu cách tính toán độ phức tạp thời gian cho bất kỳ thuật toán nào
Tại sao độ phức tạp của thời gian là một chức năng của kích thước đầu vào của nó?
Để nắm bắt hoàn hảo khái niệm "là một hàm của kích thước đầu vào", hãy tưởng tượng bạn có một thuật toán tính tổng các số dựa trên đầu vào của bạn. Nếu đầu vào của bạn là 4, nó sẽ thêm 1+2+3+4 vào đầu ra 10;
const calculateSum = [input] => {
let sum = 0;
for [let i = 0; i {
return array[0];
};
let score = [12, 55, 67, 94, 22];
console.log[firstElement[score]]; // 12
Hàm trên sẽ chỉ yêu cầu một bước thực hiện, nghĩa là hàm này ở dạng thời gian không đổi với độ phức tạp thời gian O[1]
Nhưng như tôi đã nói trước đó, có nhiều cách khác nhau để đạt được giải pháp trong lập trình. Một lập trình viên khác có thể quyết định lặp qua mảng trước khi trả về phần tử đầu tiên
const firstElement = [array] => {
for [let i = 0; i < array.length; i++] {
return array[0];
}
};
let score = [12, 55, 67, 94, 22];
console.log[firstElement[score]]; // 12
Đây chỉ là một ví dụ – có thể sẽ không ai làm điều này. Nhưng nếu có vòng lặp thì đây không còn là thời gian cố định nữa mà bây giờ là thời gian tuyến tính với độ phức tạp thời gian O[n]
Thời gian tuyến tính. Trên]
Bạn nhận được độ phức tạp thời gian tuyến tính khi thời gian chạy của thuật toán tăng tuyến tính với kích thước của đầu vào. Điều này có nghĩa là khi một hàm có một phép lặp lặp lại trên kích thước đầu vào là n, thì nó được cho là có độ phức tạp về thời gian theo thứ tự O[n]
Ví dụ: nếu một thuật toán trả về giai thừa của bất kỳ số nào đã nhập. Điều này có nghĩa là nếu bạn nhập 5 thì bạn phải lặp lại và nhân 1 với 2 với 3 với 4 và với 5 rồi xuất ra 120
const calcFactorial = [n] => {
let factorial = 1;
for [let i = 2; i {
let firstIndex = 0;
let lastIndex = array.length - 1;
while [firstIndex target] {
lastIndex = middleIndex - 1;
} else {
firstIndex = middleIndex + 1;
}
}
return -1;
};
let score = [12, 22, 45, 67, 96];
console.log[binarySearch[score, 96]];
Trong đoạn mã trên, vì đây là tìm kiếm nhị phân, trước tiên bạn lấy chỉ mục ở giữa của mảng, so sánh nó với giá trị đích và trả về chỉ mục ở giữa nếu nó bằng. Nếu không, bạn phải kiểm tra xem giá trị mục tiêu lớn hơn hay nhỏ hơn giá trị ở giữa để điều chỉnh chỉ mục đầu tiên và cuối cùng, giảm một nửa kích thước đầu vào
Bởi vì với mỗi lần lặp, kích thước đầu vào giảm đi một nửa, độ phức tạp thời gian là logarit với thứ tự O[log n]
Thời gian bậc hai. O[n^2]
Khi bạn thực hiện phép lặp lồng nhau, nghĩa là có một vòng lặp trong một vòng lặp, độ phức tạp của thời gian là bậc hai, điều này thật kinh khủng
Một cách hoàn hảo để giải thích điều này là nếu bạn có một mảng có n phần tử. Vòng lặp bên ngoài sẽ chạy n lần và vòng lặp bên trong sẽ chạy n lần cho mỗi lần lặp của vòng lặp bên ngoài, điều này sẽ cho tổng số n^2 bản in. Nếu mảng có mười phần tử, mười phần tử sẽ in 100 lần [10^2]
Đây là một ví dụ của Jared Nielsen, trong đó bạn so sánh từng phần tử trong một mảng để xuất chỉ mục khi hai phần tử giống nhau
________số 8_______Trong ví dụ trên, có một vòng lặp lồng nhau, nghĩa là độ phức tạp thời gian là bậc hai với thứ tự O[n^2]
Thời gian theo cấp số nhân. O[2^n]
Bạn nhận được độ phức tạp theo cấp số nhân khi tốc độ tăng trưởng tăng gấp đôi với mỗi lần thêm vào đầu vào [n], thường lặp qua tất cả các tập hợp con của các phần tử đầu vào. Bất cứ khi nào một đơn vị đầu vào tăng lên 1, số lượng hoạt động được thực hiện sẽ tăng gấp đôi
Dãy Fibonacci đệ quy là một ví dụ điển hình. Giả sử bạn được cho một số và muốn tìm phần tử thứ n của dãy Fibonacci
Dãy Fibonacci là một dãy toán học trong đó mỗi số là tổng của hai số liền trước, trong đó 0 và 1 là hai số đầu tiên. Số thứ ba trong dãy là 1, số thứ tư là 2, số thứ năm là 3, v.v. [0, 1, 1, 2, 3, 5, 8, 13,…]
Điều này có nghĩa là nếu bạn chuyển vào số 6, thì phần tử thứ 6 trong dãy Fibonacci sẽ là 8
const recursiveFibonacci = [n] => {
if [n < 2] {
return n;
}
return recursiveFibonacci[n - 1] + recursiveFibonacci[n - 2];
};
console.log[recursiveFibonacci[6]]; // 8
Trong đoạn mã trên, thuật toán chỉ định tốc độ tăng gấp đôi mỗi khi bộ dữ liệu đầu vào được thêm vào. Điều này có nghĩa là độ phức tạp thời gian là cấp số nhân với thứ tự O[2^n]
kết thúc
Trong hướng dẫn này, bạn đã tìm hiểu tất cả về độ phức tạp của thời gian, cách xác định hiệu suất bằng cách sử dụng ký hiệu Big O và các độ phức tạp thời gian khác nhau tồn tại cùng với các ví dụ
Bạn có thể tìm hiểu thêm qua giáo trình Thuật toán JavaScript và Cấu trúc dữ liệu của freeCodeCamp
học tập vui vẻ
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
Nhà phát triển Frontend & Người viết kỹ thuật
Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn
Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu