tìm kiếm nhị phân có một buổi biểu diễn trường hợp trung bình như O(log n) và Quick Sắp xếp với O(n log n) là O(n log n) là giống như O (n) + O (log n)Làm thế nào để bạn hình dung sự khác biệt giữa O (log n) và O (n log n)?
Hãy tưởng tượng cơ sở dữ liệu với mọi người trên thế giới. Đó là 6,7 tỷ mục. O (log n) là một tra cứu trên một cột được lập chỉ mục (ví dụ: khóa chính). O (n log n) đang trả về toàn bộ tập hợp theo thứ tự sắp xếp trên một cột không lập chỉ mục.
Một cách khác để tưởng tượng nó:
log n tỷ lệ với số chữ số trong n.
n log n lớn hơn n lần.
Hãy thử viết số 1000 một lần so với viết nó một nghìn lần. Lần đầu tiên lấy thời gian O (log n), lần thứ hai lấy thời gian O (n log n).
Bây giờ hãy thử lại lần nữa với 6700000000. Viết nó một lần vẫn còn tầm thường. Bây giờ hãy thử viết nó 6,7 tỷ lần. Ngay cả khi bạn có thể viết nó một lần mỗi giây bạn sẽ chết trước khi bạn kết thúc.
Không, O(n log n) = O(n) * O(log n)
Trong toán học, khi bạn có một biểu thức (tức là e = mc^2), nếu không có toán tử, thì bạn nhân lên.
Thông thường cách để hình dung O (n log n) là "thực hiện một việc cần thực hiện log n tính toán n lần".
Nếu bạn đã có một thuật toán mà đầu tiên lặp qua một danh sách, sau đó đã làm một tìm kiếm nhị phân của danh sách đó (đó sẽ là N + log N) bạn thể bày tỏ mà chỉ đơn giản như O(n) vì n sao lùn log n cho các giá trị lớn n
Bạn có thể hình dung nó trong một âm mưu, xem here ví dụ:
Cách tốt nhất để hình dung là sử dụng tầm nhìn. Làm tốt. –
Tuyệt vời. Cảm ơn bạn đã chỉ ra tài nguyên này. Tôi đã sử dụng Wolfram để vẽ 4 loại tính toán phức tạp phổ biến được thảo luận trong Tuần 3 của khóa học CS50 của Harvard. http://www.wolframalpha.com/input/?i=plot+log(n)+vs+n+vs+n%2Alog(n)+vs+n%5E2+from+1+to+10 https: //www.youtube.com/embed/IM9sHGlYV5A – squarecandy
Một cốt truyện (log n) tăng, nhưng là lõm xuống, có nghĩa là:
Một cốt truyện (n log n) tăng, và là (hơi) lõm trở lên, có nghĩa là:
Phụ thuộc vào việc bạn có xu hướng trực quan hóa n khi có va chạm cụ thể lue.
Nếu bạn có xu hướng để hình dung n như có một giá trị cụ thể, và các đơn vị của f(n) là thời gian hoặc hướng dẫn, sau đó O(log n) nhanh n lần so với O(n log n) cho một nhiệm vụ nhất định kích thước n. Đối với các đơn vị bộ nhớ hoặc không gian, thì O(log n) là n lần nhỏ hơn cho một tác vụ có kích thước n. Trong trường hợp này, bạn đang tập trung vào tên miền của f(n) cho một số được biết đến n. Bạn đang hình dung các câu trả lời cho các câu hỏi về thời gian sẽ mất bao lâu hoặc lượng hoạt động này sẽ sử dụng bao nhiêu bộ nhớ.
Nếu bạn có xu hướng hình dung n làm thông số có bất kỳ giá trị nào thì O(log n) là n lần có thể mở rộng hơn. O(log n) có thể hoàn thành n lần với nhiều tác vụ có kích thước n. Trong trường hợp này, bạn tập trung vào miền của f(n). Bạn đang hình dung các câu trả lời cho các câu hỏi về mức độ lớn như thế nào n có thể nhận được hoặc số lượng phiên bản f(n) bạn có thể chạy song song.
Không phối cảnh nào tốt hơn cái kia. Cái cũ có thể được sử dụng để so sánh các cách tiếp cận để giải quyết một vấn đề cụ thể. Sau này có thể được sử dụng để so sánh các hạn chế thực tế của các phương pháp đã cho.
+1 ví dụ hay. – tster