Асимптотическая оценка для целочисленного деления
k = n; //integer division
while(k > 1) {
std::cout << k;
k=k/2;
}
Мне нужно выяснить асимптотическую оценку как функцию от n.
Решение
Сложность логарифмическая.
Предполагая, что K неотрицательно, деление на два эквивалентно сдвигу вправо на один бит. Поэтому максимальное количество итераций до k становится 0 это количество бит в k, В частности, положение самого значительного бита в k это установлено (то есть, 1) определит количество итераций, выполненных в цикле.
Поскольку операции в цикле (предположительно) имеют постоянную сложность, логарифмическое число итераций приводит непосредственно к логарифмической сложности.
Другие решения
Других решений пока нет …