Имеется такой метод:
template<class RandomIt>
static auto SelectionSort(RandomIt first, RandomIt last)
-> typename std::remove_reference<decltype(first)>::type {
// Declare a base type for RandomIt
typedef std::remove_reference_t<decltype(*first)> BaseType;
int length = std::distance(first, last);
BaseType* res = new BaseType[length];
auto limits = std::numeric_limits<BaseType>();
auto lastMin = limits.min();
for (int i = 0; i < length;) {
int count = 0;
auto min = limits.max();
for (auto j = first; j != last; ++j) {
auto v = (*j);
if (v > lastMin) {
if (v < min) {
min = v;
count = 1;
} else if (v == min){
++count;
}
}
}
for (; count > 0; --count, ++i) {
res[i] = min;
}
lastMin = min;
}
return res;
}
Пытаюсь понять, как оценить его сложность... Конкретно, не понимаю, как оценить сложность (стоимость, количество выполнений) в этом участке кода:
if (v > lastMin) {
if (v < min) {
min = v;
count = 1;
} else if (v == min){
++count;
}
}
P.S. Мне не нужен ответ вида O(n^2). Я хочу понять, как я должен рассуждать в этом блоке, проставляя стоимость (просто c1, c2, ..., cm) и количество выполнений?