Ký hiệu Big O Bảng cheat Python
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. Show
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;
Trong đoạn mã trên, chúng ta có ba câu lệnh Nhìn vào hình trên, chúng ta chỉ có ba câu lệnh. Tuy nhiên, do có vòng lặp nên câu lệnh thứ hai sẽ được thực hiện dựa trên kích thước đầu vào, vì vậy nếu đầu vào là bốn thì câu lệnh thứ hai (câu lệnh 2) sẽ được thực hiện bốn lần, nghĩa là toàn bộ thuật toán sẽ chạy sáu lần (4 + Nói một cách đơn giản, thuật toán sẽ chạy đầu vào + 2 lần, trong đó đầu vào có thể là bất kỳ số nào. Điều này cho thấy rằng nó được thể hiện dưới dạng đầu vào. Nói cách khác, nó là một chức năng của kích thước đầu vào Trong Big O, có sáu loại độ phức tạp chính (thời gian và không gian)
Trước khi xem xét các ví dụ về độ phức tạp của từng thời điểm, hãy tìm hiểu biểu đồ độ phức tạp của thời gian Big O Biểu đồ độ phức tạp của Big OBiểu đồ Big O, còn được gọi là biểu đồ Big O, là một ký hiệu tiệm cận được sử dụng để biểu thị độ phức tạp của thuật toán hoặc hiệu suất của thuật toán dưới dạng hàm của kích thước đầu vào Điều này giúp các lập trình viên xác định và hiểu đầy đủ về tình huống xấu nhất cũng như thời gian thực hiện hoặc bộ nhớ mà thuật toán yêu cầu Biểu đồ sau minh họa độ phức tạp của Big O Biểu đồ Big O ở trên cho thấy O(1), viết tắt của độ phức tạp thời gian không đổi, là tốt nhất. Điều này ngụ ý rằng thuật toán của bạn chỉ xử lý một câu lệnh mà không có bất kỳ bước lặp nào. Sau đó, có O(log n), cái này tốt và những cái khác thích nó, như hình bên dưới
Bây giờ bạn đã hiểu các độ phức tạp thời gian khác nhau và bạn có thể nhận ra những cái tốt nhất, tốt và công bằng, cũng như những cái xấu và tồi tệ nhất (luôn tránh độ phức tạp thời gian xấu và tồi tệ nhất) Câu hỏi tiếp theo xuất hiện trong đầu bạn là làm thế nào bạn biết được thuật toán nào có độ phức tạp về thời gian, với điều kiện đây là một trò gian lận 😂
Hãy bắt đầu bằng cách mô tả độ phức tạp của từng thời điểm bằng các ví dụ. Điều quan trọng cần lưu ý là tôi sẽ sử dụng JavaScript trong các ví dụ trong hướng dẫn này, nhưng ngôn ngữ lập trình không quan trọng miễn là bạn hiểu khái niệm và độ phức tạp của mỗi lần. Ví dụ về độ phức tạp của thời gian Big Othời gian không đổi. Ô(1)Khi thuật toán của bạn không phụ thuộc vào kích thước đầu vào n, nó được cho là có độ phức tạp thời gian không đổi với thứ tự O(1). Điều này có nghĩa là thời gian chạy sẽ luôn giống nhau bất kể kích thước đầu vào Ví dụ: nếu một thuật toán trả về phần tử đầu tiên của một mảng. Ngay cả khi mảng có 1 triệu phần tử, độ phức tạp về thời gian sẽ không đổi nếu bạn sử dụng phương pháp này
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
Đâ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
Thực tế là thời gian chạy phụ thuộc vào kích thước đầu vào có nghĩa là độ phức tạp của thời gian là tuyến tính với thứ tự O(n) Thời gian logarit. O(log n)Điều này tương tự với độ phức tạp của thời gian tuyến tính, ngoại trừ thời gian chạy không phụ thuộc vào kích thước đầu vào mà phụ thuộc vào một nửa kích thước đầu vào. Khi kích thước đầu vào giảm trên mỗi lần lặp hoặc bước, một thuật toán được cho là có độ phức tạp thời gian logarit Phương pháp này là phương pháp tốt thứ hai vì chương trình của bạn chạy với một nửa kích thước đầu vào chứ không phải kích thước đầy đủ. Rốt cuộc, kích thước đầu vào giảm với mỗi lần lặp lại Một ví dụ tuyệt vời là các hàm tìm kiếm nhị phân, phân chia mảng đã sắp xếp của bạn dựa trên giá trị đích Ví dụ: giả sử bạn sử dụng thuật toán tìm kiếm nhị phân để tìm chỉ mục của một phần tử đã cho trong một mảng
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
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úcTrong 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 Ký hiệu Big O với ví dụ là gì?Như đã đề cập ở trên, ký hiệu Big O không hiển thị thời gian thuật toán sẽ chạy. Thay vào đó, nó hiển thị số lượng thao tác mà nó sẽ thực hiện.
. Ký hiệu Big O hiển thị số lượng hoạt động Ký hiệu Big O cho người mới bắt đầu là gì?Ký hiệu Big-O là ngôn ngữ chúng tôi sử dụng để nói về thời gian chạy một thuật toán (độ phức tạp về thời gian) hoặc lượng bộ nhớ được sử dụng bởi một thuật toán (độ phức tạp về không gian) . Ký hiệu Big-O có thể biểu thị thời gian chạy tốt nhất, tệ nhất và trường hợp trung bình của một thuật toán. . Big-O notation can express the best, worst, and average-case running time of an algorithm.
Chúng ta có thể bỏ qua ký hiệu Big O không?Độ phức tạp về thời gian của thuật toán này có thể được phân loại là O(n), nghĩa là khi n tăng, thời gian chạy tăng theo tuyến tính. Chúng ta có thể bỏ qua câu lệnh if bên trong vòng lặp for, vì độ phức tạp về thời gian O(1) của nó không phụ thuộc nhiều vào kích thước đầu vào .
Ký hiệu Big O hiệu quả nhất là gì?Như bạn có thể thấy, thuật toán với ký hiệu O(1) có khả năng mở rộng tốt nhất khi kích thước đầu vào ngày càng lớn hơn, trong khi . |