Мобильная версияПочему std::upper_bound() имеет линейную сложность? ⇐ C++
-
Anonymous
Почему std::upper_bound() имеет линейную сложность?
Я читал руководство по USACO Silver, в котором говорилось об отсортированных наборах, и наткнулся на это предупреждение (s — это std::set целых чисел): Внимание!
Предположим, что мы заменим s.upper_bound(7) на upper_bound(begin(s),end(s),7) — синтаксис, который мы использовали для векторов в обязательный модуль. Это по-прежнему даст ожидаемые результаты, но его временная сложность будет линейной в зависимости от размера набора s, а не логарифмической, поэтому избегайте этого!
Что они означают?
Upper_bound(s.begin(), s.end(), 7 ); // На) ? s.upper_bound(7); // O(логарифм N) ?
Я читал руководство по USACO Silver, в котором говорилось об отсортированных наборах, и наткнулся на это предупреждение (s — это std::set целых чисел): Внимание!
Предположим, что мы заменим s.upper_bound(7) на upper_bound(begin(s),end(s),7) — синтаксис, который мы использовали для векторов в обязательный модуль. Это по-прежнему даст ожидаемые результаты, но его временная сложность будет линейной в зависимости от размера набора s, а не логарифмической, поэтому избегайте этого!
Что они означают?
Upper_bound(s.begin(), s.end(), 7 ); // На) ? s.upper_bound(7); // O(логарифм N) ?
