Tôi đang học một khóa học Coursera về độ phức tạp của thời gian. Tôi gặp điều này trong một video và tôi nghĩ có gì đó không ổn. “Vì vậy, giả sử rằng chúng ta có một thuật toán có thời gian chạy gần như tỷ lệ với n và chúng ta muốn nó chạy nó trên một máy chạy ở tốc độ khoảng gigahertz. Chúng ta có thể xử lý đầu vào lớn đến mức nào để có thể hoàn thành việc tính toán trong một giây.” ? ” (CPU 1GHZ (10^9 chu kỳ mỗi giây))
“Chà, nếu nó chạy ở kích thước n, bạn có thể xử lý khoảng một tỷ đầu vào có kích thước, trước khi mất hơn một giây” (10^9 / 10^9)
“Nếu nó chạy như n bình phương thì tệ hơn nhiều. Bạn chỉ có thể xử lý đầu vào có kích thước khoảng 30.000 trước khi bắt đầu mất hơn một giây.” n = 30000, (30000)^2/10^9 = 0,9 giây ~ 1 giây
“Nếu đầu vào có kích thước từ 2 đến n thì điều đó cực kỳ tệ, bạn chỉ có thể xử lý đầu vào có kích thước khoảng 30 trong một giây” 2^30/10^9 ~ 1,07 giây
Với độ phức tạp n log(n), nếu kích thước đầu vào n là 10^9 thì sẽ mất 10^9 * log(10^9) / 10^9 = 9 giây, phải không? Bằng cách nào đó nó hiển thị 30 giây trong video. Nó cũng nói rằng nếu n = 10^7,5 thì thời gian chạy là 1 giây, điều này cũng sai với tính toán của tôi.
Tôi đã tính toán mọi trường hợp với độ phức tạp n, n^2, 2^n và mọi thứ đều đúng, chỉ có trường hợp nlog(n) bị sai
Đây là bức ảnh để biết thêm chi tiết: https://i.upanh.org/2022/04/11/nlogn.jpg[^]
Link video khóa học (phần 3:40 đến 5:00): https://www.coursera.org/lecture/algorithmic-toolbox/asymptotic-notation-zI8dH[^]
Tôi đã chỉnh sửa câu hỏi sao cho giống như trong video khóa học tôi đã xem
Những gì tôi đã thử:
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
Giải pháp 1
Trích dẫn:Nếu kích thước đầu vào n là 10^9 thì sẽ mất 10^9 * log(10^9) / 10^9 = 9 giây, phải không?
KHÔNG ! Bạn không tính toán thời gian chạy từ ký hiệu Big O, ít nhất là không phải riêng nó.
Ký hiệu Big O cho bạn biết mức độ phức tạp của thuật toán, không phải thời gian chạy, không trực tiếp.
Khi bạn có thời gian chạy cho kích thước dữ liệu nhất định, độ phức tạp Big O cho phép bạn đánh giá thời gian chạy cho kích thước dữ liệu khác.
thời gian 1 giây của bạn cho dữ liệu từ 20 đến 10^6 có nghĩa là bạn cần chuyển sang thời gian mili giây để có được thời gian có ý nghĩa.
Giải pháp 2
Cái lớn O không đưa ra thời gian thực hiện chính xác. Hãy xem, ví dụ Ký hiệu Big O – Wikipedia[^] (Của cải phần, nhân với một hằng số).
Giải pháp 3
Để thêm vào những gì người khác nói, dù sao thì bạn cũng không thể đánh đồng trực tiếp chu kỳ đồng hồ với thời gian thực hiện – một số thao tác máy mất n chu kỳ để thực thi, một số thao tác khác có thể là n * 2. Để thêm vào đó, các bộ xử lý hiện đại được sắp xếp theo đường dẫn – vì vậy một số hướng dẫn có thể bắt đầu trong khi các lệnh khác đang thực thi, được lưu vào bộ nhớ đệm – vì vậy thời gian thực thi có thể phụ thuộc vào khoảng thời gian lệnh được thực hiện lần cuối và liệu dữ liệu của nó có sẵn trong bộ nhớ đệm L1, L2 hoặc L3 hay không, tính sẵn có của các lõi trống để thực thi, ‘cộng với một loạt các lõi khác chi tiết.
Bạn không thể chỉ nói “tốc độ đồng hồ của tôi là X, vì vậy thời gian thực hiện của tôi là X * Y” – có quá nhiều yếu tố khác sẽ ảnh hưởng đến nó.
Giải pháp 5
30 giây là đúng nếu đó là nhật ký2(N). nhật ký2(1000) ~= 10.
BIÊN TẬP: Thuật toán O(n log(n)) thường chia bài toán một cách đệ quy, giải từng phần riêng biệt rồi kết hợp các lời giải. Đây là lý do tại sao đăng nhập2 thường được ngụ ý. Mergesort là một ví dụ điển hình.
Giải pháp 6
ký hiệu O lớn chỉ cho bạn biết thời gian thực hiện sẽ như thế nào thay đổi khi “quy mô” của vấn đề thay đổi, nó không cung cấp ước tính thực tế cho một trường hợp cụ thể.
Nói cách khác, có một yếu tố chưa biết, ví dụ như O(n2) có thể có nghĩa
time_needed = constant * n * n
trong đó không ai cho biết giá trị của hằng số là gì, do đó không có giá trị cụ thể cho time_ Need.
Ví dụ này chỉ cho bạn biết rằng một vấn đề lớn gấp đôi sẽ mất thời gian gấp bốn lần để giải quyết.
コメント