Ký hiệu Big O: Nó là gì và tại sao nó lại quan trọng?

Đây là một niềm vui! Giao tiếp với Big O là một trong những quá trình chuyển đổi gây kinh ngạc đầu tiên đối với những nhà phát triển mới bắt đầu sự nghiệp.

Hãy xem tại sao.

Nhưng trước tiên, một điểm dừng chân. Bạn có nhớ những bài toán đố hoàn toàn lố bịch ở trường tiểu học không?

Sally đến cửa hàng tạp hóa và mua 37 quả dưa hấu. Cô ấy có 20 đô la. Mỗi quả dưa hấu có giá 0,7 đô la. Sally có bao nhiêu tiền khi cô ấy về nhà?

Bạn có tự hỏi, "Làm thế quái nào mà Sally về nhà được? Với 37 quả dưa hấu?! $6,00 sẽ không đủ để bắt một chiếc Uber có đủ chỗ cho dưa... Sally đang làm gì vậy?!"

Sally ngốc nghếch.

Một số người nói rằng điều này đang làm mất rừng vì cây. Tôi nói rằng đó chỉ là một cách cực kỳ lười biếng để xây dựng các vấn đề thực hành.

Mục đích của Big O Notation là để có thể nói chuyện, giao tiếp theo nghĩa đen với người khác , về chất lượng nghề thủ công của chúng tôi. Trọng tâm cụ thể ở đây là cho phép so sánh giữa các giải pháp trong trường hợp xấu nhất khi kích thước của đầu vào tăng lên.

Chúng tôi muốn có thể nói về các giải pháp tiềm năng ( giống như nói: thuật toán ) trong bản tóm tắt. Đây là một điểm quan trọng: trong bản tóm tắt . Chúng tôi hoàn toàn không quan tâm đến dữ liệu chúng tôi có . Khi chúng tôi chơi với những ý tưởng này, chúng tôi giả sử một tập dữ liệu khổng lồ nhưng hữu hạn về mặt lý thuyết.

Khi chúng tôi nghĩ về dữ liệu chúng tôi có , đây là lý do cụ thể. Khi chúng ta nghĩ về Ký hiệu Big O, chúng ta đang lý luận một cách trừu tượng. Thật DỄ DÀNG để quay trở lại lý luận cụ thể. Đây là nơi chúng ta dành phần lớn cuộc đời. Thật dễ dàng, thường rõ ràng và thoải mái.

Tôi có nên băng qua đường bây giờ không? Có xe không? KHÔNG? Được rồi, vượt qua.

Đừng làm vậy khi lý luận trừu tượng!

Định nghĩa, nhanh chóng

Bạn có phiền không nếu tôi giúp bạn một việc ở đây? Có một loạt các thuật ngữ toán học cũng có thể gây cản trở. Đây là hình ảnh, theo thứ tự, từ trường hợp tốt nhất đến trường hợp xấu nhất, đối với một số thuật ngữ Big O phổ biến. Chúng tôi cần những thứ này để chúng tôi có thể suy nghĩ và học hỏi thay vì bị mắc kẹt trong thuật ngữ.

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

Không quan trọng đầu vào lớn như thế nào, hệ thống luôn trả về kết quả trong cùng một khoảng thời gian.

O(log n) - "Thời gian đăng nhập"

Khi giải pháp (hoặc thuật toán) lặp lại trên đầu vào, mỗi lần lặp sẽ nhanh hơn!

O(n) - "Thời gian tuyến tính"

Khi thuật toán lặp lại, mỗi lần lặp lại mất cùng một khoảng thời gian như lần lặp trước.

O(n log n) - không có thuật ngữ ưa thích nào ở đây

Cho thấy rằng các ý tưởng có thể được kết hợp (yike). Khi chúng tôi lặp lại, mỗi lần lặp lại chậm hơn nhưng chậm hơn khá chậm.

O(n^2) - "n bình phương"

Đối với mỗi lần lặp lại, các lần lặp lại chậm hơn khá nhanh.

O(n!) - "n giai thừa"

Đối với mỗi lần lặp lại, các lần lặp lại chậm hơn siêu nhanh.

Mục tiêu là cố gắng tránh càng xa "n giai thừa" càng tốt và cố gắng không tệ hơn nhiều so với Constant.

Với tất cả những gì đã hiểu, bây giờ chúng ta hãy cố gắng thu hẹp khoảng cách.

Thu hẹp khoảng cách giữa tư duy cụ thể và trừu tượng

Hiểu ký hiệu Big O

Ký hiệu Big O được sử dụng để mô tả hiệu suất hoặc độ phức tạp của một thuật toán (giải pháp). Nó cung cấp hiểu biết cấp cao về cách một thuật toán (giải pháp) sẽ hoạt động khi kích thước của đầu vào tăng lên.

Ví dụ: một thuật toán có độ phức tạp O(n) sẽ có thời gian chạy tăng tuyến tính với kích thước của đầu vào.

Tư duy cụ thể vs trừu tượng

Thách thức nảy sinh khi các nhà phát triển nhầm lẫn lý luận về dữ liệu cụ thể với lý luận về chính thuật toán. Các cụm từ như "nhưng dữ liệu này là có thật" có thể báo hiệu sự nhầm lẫn này.

Mặc dù lập luận về dữ liệu thực có thể giúp bạn bắt đầu, nhưng điều quan trọng là phải tách giải pháp khỏi đầu vào hiện tại.

Tại sao hiểu lầm?

Những người phát triển sự nghiệp ban đầu có thể mắc lỗi này do thiếu kinh nghiệm với các vấn đề quy mô lớn hơn hoặc quá mải mê với các chi tiết cụ thể của một vấn đề hiện tại. Điều cần thiết là tách các chi tiết cụ thể khỏi sự phức tạp trừu tượng để tạo ra các giải pháp có thể mở rộng.

Hậu quả thực tế

Khi đầu vào tăng gấp 100 hoặc 100.000 lần, điều gì xảy ra với thuật toán? Một giải pháp cực kỳ phức tạp phức tạp có thể sụp đổ với một tập dữ liệu lớn hơn.

Một thuật toán có vẻ ổn đối với các tập dữ liệu nhỏ có thể thất bại nghiêm trọng với các tập dữ liệu lớn hơn, dẫn đến các vấn đề về hiệu suất và các thách thức khác.

Học cách suy nghĩ trừu tượng

Phát triển khả năng suy nghĩ trừu tượng về các vấn đề đòi hỏi phải thực hành và hướng dẫn. Một số chiến lược bao gồm:

• Tạo mô hình trừu tượng : Trình bày các vấn đề theo cách tổng quát.

• Phân tích thuật toán riêng biệt với dữ liệu : Đánh giá cách thức hoạt động của thuật toán bất kể các điểm dữ liệu cụ thể.

• Xây dựng các kịch bản mở rộng quy mô : Tưởng tượng thuật toán sẽ hoạt động như thế nào với các kích thước đầu vào khác nhau.

Tư duy trừu tượng nói chung và Big O Notation nói riêng là những kỹ năng thiết yếu trong thiết kế thuật toán — nói cách khác, đưa ra giải pháp cho một vấn đề.

Bằng cách học cách tách độ phức tạp của vấn đề khỏi độ phức tạp của thuật toán , các nhà phát triển có thể tránh những cạm bẫy phổ biến và nâng cao khả năng giải quyết vấn đề của họ khi làm việc một mình VÀ nâng cao đáng kể khả năng làm việc cùng với những người khác đã đầu tư thời gian tương tự để học cách giao tiếp theo cách này.

Các vấn đề phức tạp thường không yêu cầu các giải pháp phức tạp. (Sally có lẽ không cần đến 37 quả dưa hấu ngay từ đầu… cô ấy sẽ làm gì với 37 quả dưa hấu?!)