Nếu có 2 algorthims tính kết quả tương tự với độ phức tạp khác nhau, O (log n) có luôn nhanh hơn không? Nếu vậy hãy giải thích. BTW đây không phải là một câu hỏi chuyển nhượng.O (log n) luôn luôn nhanh hơn O (n)
No. Nếu một thuật toán chạy trong N/100 và một thuật toán khác trong (log N)*100, thì thuật toán thứ hai sẽ chậm hơn đối với kích thước đầu vào nhỏ hơn. Sự phức tạp tiệm cận là về hành vi của thời gian chạy khi kích thước đầu vào đi đến vô cùng.
để O (n) có thể nhanh hơn O (log n) cho đầu vào cực nhỏ? – Varkolyn
1 * n là O (n). 10000000000000000000000000000000 * (log n) là O (log n). Trong trường hợp này, O (n) sẽ không chỉ nhanh hơn trên đầu vào cực nhỏ. Nhưng khi "n" phát triển theo hướng vô cùng, * cuối cùng * O (log n) sẽ nhanh hơn. –
@Varkolyn: Không nhất thiết * cực kỳ *. Tùy thuộc vào thuật toán, điểm giao cắt có thể rất lớn trong * n *! – kkm
Không, nó sẽ không phải lúc nào cũng nhanh hơn. NHƯNG, khi kích thước vấn đề lớn dần và lớn hơn, cuối cùng là bạn sẽ luôn đạt đến điểm mà thuật toán O (log n) nhanh hơn so với O (n).
Trong các tình huống thực tế, thường là điểm mà thuật toán O (log n) vượt qua thuật toán O (n) sẽ đến rất nhanh. Có sự khác biệt lớn giữa O (log n) và O (n), giống như có sự khác biệt lớn giữa O (n) và O (n^2).
Nếu bạn có cơ hội đọc Ngọc trai lập trình bởi Jon Bentley, có một chương tuyệt vời ở đó, trong đó có một thuật toán O (n) so với O (n^2) cho O (n^2) lợi thế. (Anh ta mã hóa thuật toán O (n^2) trong C trên Alpha và thuật toán O (n) trong diễn giải BASIC trên một Z80 cũ hoặc thứ gì đó, chạy ở khoảng 1MHz.) Thật đáng ngạc nhiên khi O (n) nhanh đến mức nào thuật toán vượt qua O (n^2) một.
Thỉnh thoảng, bạn có thể tìm thấy một thuật toán rất phức tạp có độ phức tạp tốt hơn một chút so với một thuật toán đơn giản hơn. Trong trường hợp như vậy, đừng mù quáng chọn thuật toán với một big-O tốt hơn - bạn có thể thấy rằng nó chỉ nhanh hơn trên các vấn đề cực lớn.
Sẽ luôn nhanh hơn nếu đủ lớn * n *. – Phonon