Độ phức tạp của find trong string c++?

Nguyen_Cong_Cuong · October 7, 2019, 9:38am

Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case).
Root: http://www.cplusplus.com/reference/string/string/find/

Mình dốt tiếng anh, nên muốn hỏi các bạn có phải dpt là O(n) ko ? (với n là độ dài của xâu)

vanhieu · December 5, 2019, 8:57am

linear là tuyến tính, bạn hiểu là 1 lượt duyệt từ đầu tới cuối: O(n) trong trường hợp xấu nhất (worst case)