c++ - Cppreference 的复杂性？

Question

我开始理解算法时间复杂度的表示法，例如“大 O”。但是cppreference上很多关于不同算法复杂度的描述我都看不懂，like for std::search .它不涉及我好不容易学会的符号，例如“big O”和“big Omega”。。我应该如何理解这样的复杂性描述？

At most S*N comparisons where S = std::distance(s_first, s_last) and N = std::distance(first, last).

Answer 1

这就是所写的意思。对于长度为 S 和 N 的输入，它不会做更多的 S*N 比较。例如，如果你有长度为 5 和 3 的数组，它不会做超过 15 次比较:

std::array<char, 3> a;
std::array<char, 5> b;
std::search(b.begin(), b.end(), a.begin(), a.end());