Ký hiệu big-O là gì? Làm thế nào để bạn đưa ra con số như O (n)?

Question

thể trùng lặp:
Plain english explanation of Big O

Tôi muốn tưởng tượng này có lẽ là một cái gì đó dạy trong lớp học, nhưng như tôi một lập trình viên tự học, tôi đã chỉ nhìn thấy nó hiếm khi.

Tôi đã tập hợp nó là một cái gì đó để làm với thời gian, và O (1) là tốt nhất, trong khi những thứ như O (n^n) là rất xấu, nhưng ai đó có thể chỉ cho tôi một lời giải thích cơ bản về những gì nó thực sự đại diện, và những con số này đến từ đâu?

Answer 1

Big O là thứ tự thời gian chạy trường hợp xấu nhất. Nó được sử dụng để hiển thị một thuật toán quy mô tốt như thế nào dựa trên kích thước của tập dữ liệu (n-> số lượng các mục).

Vì chúng tôi chỉ quan tâm đến thứ tự, các hệ số không đổi bị bỏ qua và bất kỳ cụm từ nào tăng nhanh hơn so với cụm từ thống trị cũng bị loại bỏ. Một số ví dụ:

Một hoạt động hoặc tập hợp hoạt động là O (1), vì phải mất một khoảng thời gian cố định (không thay đổi dựa trên kích thước tập dữ liệu).

Vòng lặp là O (n). Mỗi phần tử trong tập dữ liệu được lặp lại.

Vòng lặp lồng nhau là O (n^2). Một vòng lặp lồng nhau lồng nhau là O (n^3), và trở đi.

Những thứ như tìm kiếm cây nhị phân là log (n), khó hiển thị hơn, nhưng ở mọi cấp độ trong cây, số lượng giải pháp có thể giảm đi một nửa, do đó số lượng cấp là nhật ký (n) cây được cân bằng).

Điều gì đó giống như tìm tổng của một tập hợp các số gần nhất với một giá trị đã cho là O (n!), Vì tổng của mỗi tập con cần được tính toán. Thật tồi tệ.

Answer 2

Đó là cách thể hiện sự phức tạp về thời gian.

O(n) có nghĩa là đối với n yếu tố trong danh sách, phải mất n tính toán để sắp xếp danh sách. Mà không phải là xấu cả. Mỗi tăng trong n làm tăng độ phức tạp về thời gian một cách tuyến tính.

O(n^n) là xấu, vì số lượng tính toán cần thiết để thực hiện sắp xếp (hoặc bất kỳ thứ gì bạn đang làm) sẽ tăng theo cấp số nhân khi bạn tăng n.

O(1) là tốt nhất, vì nó có nghĩa là 1 tính toán để thực hiện một hàm, hãy nghĩ về bảng băm, tra cứu giá trị trong bảng băm có độ phức tạp thời gian O(1).

Answer 3

Ký hiệu Big O như được áp dụng cho thuật toán đề cập đến cách thời gian chạy của thuật toán phụ thuộc vào lượng dữ liệu đầu vào. Ví dụ, một thuật toán sắp xếp sẽ mất nhiều thời gian hơn để sắp xếp một tập dữ liệu lớn hơn một tập dữ liệu nhỏ. Nếu ví dụ về thuật toán sắp xếp, bạn vẽ đồ thị thời gian chạy (trục dọc) so với số giá trị để sắp xếp (trục ngang), cho số giá trị từ 0 đến số lớn, bản chất của đường hoặc đường cong mà kết quả sẽ phụ thuộc vào thuật toán sắp xếp được sử dụng. Ký hiệu Big O là một phương pháp viết tắt để mô tả đường thẳng hoặc đường cong.

Trong ký hiệu O lớn, biểu thức trong dấu ngoặc là hàm được vẽ đồ thị.Nếu một biến (nói n) được bao gồm trong biểu thức, biến này đề cập đến kích thước của tập dữ liệu đầu vào. Bạn nói O (1) là tốt nhất. Điều này đúng bởi vì đồ thị f (n) = 1 không thay đổi với n. Thuật toán O (1) mất cùng một khoảng thời gian để hoàn thành bất kể kích thước của bộ dữ liệu đầu vào. Ngược lại, thời gian chạy của thuật toán O (n^n) tăng lên với bình phương kích thước của bộ dữ liệu đầu vào.

Đó là ý tưởng cơ bản, để được giải thích chi tiết, hãy tham khảo trang wikipedia có tiêu đề 'Big O Notation'.