Временная сложность счетчика
enum class COLOR
{
Blue,
Red,
Green,
Purple,
First=Blue,
Last=Purple
};
COLOR operator++( COLOR& x ) { return x = (COLOR)(((int)(x) + 1)); }
COLOR operator*(COLOR c) {return c;}
COLOR begin(COLOR r) {return COLOR::First;}
// end iterator needs to return one past the end!
COLOR end(COLOR r) {return COLOR(int(COLOR::Last) + 1);}int main()
{
for (const auto& color : COLOR()) std::cout << int(color); //0123
return 0;
}
Я взял этот кусок кода от SO ссылка на сайт.
Меня спросили временную сложность подобного куска кода. Насколько я понимаю, это O(n) так как все элементы перечислителя повторяются.
Но правильный ответ на некоторых платформах говорит O(1) без каких-либо объяснений.
Может кто-нибудь подтвердить, правда? O(1) и почему?
Решение
Когда вы выполняете анализ асимптотической сложности, всегда важно определить размер ввода является. Потому что это то, что сложность определяется с точки зрения. Только тогда анализ имеет смысл в любом случае.
Например, если этот алгоритм определен как не имеющий входных данных, то мы можем утверждать, что число перечислителей фиксировано и равно Last - First, Таким образом, тело цикла будет выполняться фиксированное количество раз, и для него будет O (1).
Я могу только догадываться, что часть «некоторой платформы» может относиться к способности компиляторов оптимизировать. Когда компилятор видит цикл, который будет предварительно сформирован ровно 4 раза, он вполне может предпочесть развернуть его, вместо того, чтобы выдавать код для реального цикла.
Сказав это, оптимизации на самом деле не влияют на асимптотическую сложность алгоритмов. Они могут в наибольшей степени влиять на коэффициент, скрытый за обозначением big-Oh. Цикл равен O (1) в любом случае, согласно анализу, который мы сделали выше, но коэффициент меньше после оптимизации развертывания, так как код, который относится к циклу, возможно, пропал.
Другие решения
Других решений пока нет …