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)
?Ký hiệu Big Oh
10
A
Trả lời
15
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)
5
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
.
3
Có:
n(n-1)/2 = (n2-n)/2 = O(n^2)
2
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.
Các vấn đề liên quan
- 1. Tại sao mã này được coi là O (N^6) trong ký hiệu Big Oh?
- 2. Ký hiệu Big Oh O ((log n)^k) = O (log n)?
- 3. Big Oh for (n log n)
- 4. Ký hiệu Big O cho số tam giác?
- 5. Ký hiệu Java Big O của 3 vòng lặp lồng nhau của nhật ký (n)
- 6. Đệ quy và Big O
- 7. Thỏa thuận lớn về ký hiệu Big-O trong khoa học máy tính là gì?
- 8. Có danh sách tổng thể về ký hiệu Big-O cho mọi thứ không?
- 9. Ký hiệu big-O là gì? Làm thế nào để bạn đưa ra con số như O (n)?
- 10. Sum của ký hiệu O lớn
- 11. Oh Zsh My - Vô hiệu hoá 'Bạn có muốn kiểm tra cập nhật' nhắc
- 12. Big-O của danh sách cắt
- 13. Big-O của .GetProperties()
- 14. Tricky Big-O complexity
- 15. Hiểu Big O
- 16. kiến, tệp jar và Class-Path oh
- 17. plugins oh-my-zsh không hoạt động
- 18. Ký hiệu "#" ký hiệu có nghĩa là gì trong clojure?
- 19. chuyển đổi ký hiệu khoa học ký hiệu bash
- 20. Tiện ích mở rộng ký hiệu có ký hiệu dài
- 21. Tính phức tạp của tiêu chuẩn :: find_end là Big-O
- 22. Confused về Big O notation
- 23. Nút.JS Big-Endian UCS-2
- 24. Ký hiệu cắt giảm hiệu lực LaTeX
- 25. Ký hiệu xác suất
- 26. Ký hiệu Khung Java?
- 27. Ký hiệu con trỏ
- 28. Ký tự hoặc ký tự không ký hiệu là char32_t`?
- 29. Ký hiệu điểm trong R
- 30. Ký hiệu # 4 là gì?
Thanks for the help! – Jay
@Jay, bạn nên chấp nhận câu trả lời nếu bạn tin rằng đó là đáp ứng câu hỏi của bạn – dgraziotin