Thời gian chạy của thuật toán A ít nhất là O (n²) - Tại sao nó lại vô nghĩa?

Question

Tại sao là tuyên bố:

Thời gian chạy của thuật toán A là ít nhất O (n ²)

là vô nghĩa?

Thời gian chạy của thuật toán sắp xếp Insertion là tại hầu hết các O (n ²)

Có đúng không?

Tôi đã thử mạng nhưng không thể có giải thích tốt.

Tôi có một câu hỏi khác:

Tôi biết rằng bất kỳ chức năng a⋅n tuyến tính + b là O (n) và cũng O (n ²). Nó cũng là O (n³)?

Answer 1

T(n): thời gian chạy của Algo A.Chúng tôi chỉ quan tâm đến giới hạn trên và dưới của T(n) Tuyên bố: T(n) >= O(n^2)

Upper ràng buộc: Bởi vì T(n) >= O(n^2), sau đó không có thông tin về giới hạn trên của T(n) thấp hơn bị ràng buộc: Giả sử f(n) = O(n^2), sau đó báo cáo kết quả: T(n) >= f(n), nhưng f(n) có thể là bất cứ điều gì đó là "nhỏ" hơn n^2, Ex: constant, n,..., vì vậy, không có kết luận về dưới của T(n) quá

=> Những tuyên bố là vô nghĩa

Answer 2

Một lý do có thể là giới hạn dưới mà không có giới hạn trên không phải là rất hữu ích. "ít nhất" có nghĩa là nó có thể là mũ trong một trường hợp bình thường. Nếu bạn không biết giới hạn trên, bạn có thể không thể sử dụng thuật toán trong một ứng dụng thực vì bạn không thể biết chương trình có kết thúc trước khi vũ trụ thực hiện hay không.

Ký hiệu O lớn khi được sử dụng đúng cho biết giới hạn trên. Vì vậy, nói một giới hạn thấp hơn như O lớn là lạm dụng ký hiệu.

Điều đó nói "vô nghĩa" là một từ mạnh mẽ. Đó chắc chắn là thông tin hữu ích ngay cả khi nó không đủ. Với bối cảnh nhiều hơn một chút cho câu hỏi của bạn, bạn có thể nhận được trợ giúp tốt hơn.

Answer 3

"Thời gian chạy của thuật toán A ít nhất là O (n2)" tương đương với "Thời gian chạy của thuật toán A là Big Omega (n2)", vì vậy nó không vô nghĩa.

Answer 4

O-ký hiệu, hay nói cách khác có nghĩa là: f (x) thuộc thiết O (g (x)) nếu f (x) < C * g (x), cho tất cả các C (những người là Bất số)

tức là thuật toán của bạn không phát triển hơn một hàm bậc hai

Answer 5

nó không vô nghĩa, nó có thể được sử dụng ví dụ nếu bạn không biết thuật toán chính xác, nhưng bạn chắc chắn biết rằng nó sẽ đòi hỏi O (n^2) hoạt động. Ví dụ, nếu người ta không biết về các thuật toán sắp xếp, nhưng hiểu rằng, để sắp xếp một mảng chúng ta cần ít nhất để xem mọi phần tử, người ta có thể nói rằng "sắp xếp một mảng ít nhất là O (n) ".

Answer 6

Vì không ai quan tâm nó hoạt động nhanh như thế nào trong trường hợp tốt nhất, trường hợp xấu nhất là quan trọng. Thông thường mọi người quan tâm để biết nó sẽ mất bao nhiêu trong trường hợp xấu nhất.

Answer 7

Gọi f(n) là thời gian chạy của thuật toán.

=> f(n) >= O(n2) 
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2) 

Điều này luôn đúng đối với f(n), vì thời gian chạy luôn không âm. Do đó, tuyên bố là thừa.

Answer 8

O (n^2) là trường hợp xấu nhất, có nghĩa là thời gian chạy của A sẽ là n^2 hoặc nhanh hơn. Nếu thời gian chạy của nó ít nhất là O (n^2) thì đó có nghĩa là thời gian chạy nhanh nhất A có thể có, ít nhất là O (n^2). Điều này có nghĩa là nó cũng có thể chậm hơn O (n^2). Các câu lệnh này có nghĩa là A có thể có bất kỳ thời gian chạy nào có thể.

Answer 9

Tôi biết rằng bất kỳ hàm tuyến tính nào là + b là O (n) và cũng O (n^2). Có phải nó là cũng O (n^3)?

Vâng, đúng vậy. Ký hiệu big-O biểu thị toàn bộ các hàm. Nhưng chúng ta nên sử dụng nó để mô tả một chức năng càng chặt chẽ càng tốt. Mặc dù đúng là f(n) = an+b là O(n^2) hoặc thậm chí O(n^3), chính xác hơn là nói rằng f(n) = O(n).

Answer 10

Một loại suy:

Những tuyên bố là một chút giống như nói: "Mái nhà của tôi là ở độ cao đó là ít nhất tầng trệt" Đúng, nhưng hoàn toàn không thông tin.