Ký hiệu Big Oh

Question

Chỉ cần xác nhận về điều gì đó thật nhanh. Nếu thuật toán mất n(n-1)/2 kiểm tra để chạy, là lớn oh O(n^2)?

Answer 1

n (n-1)/2 mở rộng để (n^2 -n)/2, đó là (n^2/2) - (n/2)

(n^2/2) và (n/2) là hai thành phần chức năng, trong đó n^2/2 chiếm ưu thế. Vì vậy, chúng tôi có thể bỏ qua phần - (n/2).

Từ n^2/2 bạn có thể xóa phần/2 một cách an toàn trong phân tích ký hiệu tiệm cận.

này đơn giản hóa để n^2

Vì vậy có, nó là trong thời gian O (n^2)

Answer 2

Vâng, đó là chính xác.

n(n-1)/2 mở rộng để n^2/2 - n/2:

Thuật ngữ tuyến tính n/2 giảm dần bởi vì nó là trật tự thấp hơn. Lá này xuất hiện n^2/2. Hằng số được hấp thụ vào big-O, để lại n^2.

Answer 3

Có:

n(n-1)/2 = (n2-n)/2 = O(n^2) 

Answer 4

Vâng, đó là. n(n-1)/2 là (n^2 - n)/2, mà rõ ràng là nhỏ hơn c*n^2 cho tất cả n>=1 nếu bạn chọn một c đó là ít nhất 1.