Thời gian chạy thực tế và lý thuyết của các giải thuật sắp xếp

[anon10499953]

Mình có một thắc mắc là tại sao thời gian chạy thực tế của các giải thuật sắp xếp lại khác với thời gian khi tính bằng Big-O? Và tại sao các giải thuật có độ phức tạp như nhau nhưng thời gian chạy thực tế lại không giống nhau. Giả sử tất cả giải thuật đều sử dụng chung 1 input.

[Itachi_Citus]

Big-O chỉ nói lên mức độ tương quan giữa kích thước dữ liệu và thời gian chạy, chứ nó không nói lên gì nhiều về tốc độ chạy thực tế cả ^^. Chẳng hạn như có 2 đoạn mã nguồn:

Đoạn (a)

for i = 1 -> n
   for j = 1 -> n
       a += 1
       b += 2
       c = a + b
       d = a + c

và 1 đoạn mã nguồn (b)

for i = 1 -> n
   for j = 1 -> n
       a += 1

Rõ ràng, thời gian chạy của (a) sẽ lớn hơn ~ 4 lần so với (b), nhưng Big-O của cả hai là bằng nhau. Mặt khác, Big-O chỉ là chặn trên chứ không phải là chặn chính xác độ phức tạp của một thuật toán.

Một vấn đề khác đó là sự chênh lệch thời gian giữa phép so sánh và phép gán. Khi phân tích độ phức tạp dựa trên Big-O, ta xem hai phép tính này tương đương nhau (và đôi khi không quan tâm phép gán), nhưng trên thực tế phép gán gây tốn thời gian hơn phép so sánh vài lần. Do đó 2 thuật toán có cùng Big-O, nhưng 1 thuật toán có sử dụng phép gán nhiều hơn sẽ chậm hơn rất nhiều.