Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень:int fastPow(double a, int n) { // дано: основание a и показатель степени n >= 0 // надо: вычислить a в степени n double b = a, p = 1.0; int k = n; while (k > 0) { // Invariant: b^k * p == a^n if (k%2 == 0) { // k четное k /= 2; b *= b; } else { // k нечетное --k; p *= b; } } return p;}
(Отметьте один правильный вариант ответа.)
Варианты ответа
Время работы не больше, чем C*r, где C - некоторая константа, r - квадратный корень из числа n (т.е. время пропорционально квадратному корню из n).
Время работы не больше, чем C*log2 n, где C - некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи числа n). (Верный ответ)
Время работы не больше, чем C*n, где C - некоторая константа (т.е. время пропорционально числу n).