C++ : Интересны многие методы возведения в степень
Доброго дня интересуют частые способы возведения в степень. В особенности случай когда O(logn),O(n²),O(n).
Последний наверное обычное через цикл и арифметические действия.
O(n²) наверное через рекурсию.
А вот первая меня очень интересует,я думал что это может быть подключение библиотеки c.math,и использование функции pow.Но не уверен.
Впрочем подскажите и просвятите в эту.И да я новичок.
Ответы (1 шт):
Насчет алгоритма за O(n) вы правы. Обычное умножение числа m само на себя k раз.
Алгоритм работающий за O(logn) это например бинарное возведение в степень.
Его суть в том, что если показатель степени четный, то для любого основания верно тождество:
a ^ n = (a ^ (n / 2)) ^ 2 = (a ^ (n / 2)) * (a ^ (n / 2))
Если же показатель нечетный, то верно тождество:
a ^ n = a ^ (n - 1) * a, где n - 1 является четным показателем степени
Приведу лишь один пример с отличного сайта (который приведу ниже):
int binpow(int a, int n) {
int res = 1;
while (n) {
//Проверяем если n нечетное, то умножаем результат на a
if (n & 1)
res *= a;
a *= a;
n >>= 1;
}
return res;
}
Например пусть a = 2, n = 5, при обычном алгоритме мы бы делали так:
res = 2 * 2 * 2 * 2 * 2 = 32
При бинарном возведении в степени в данном случае на одну двойку сразу умножим, потом рассчитаем 2 * 2 = 4 и зная, что показатель степени четный (т.к. одну двойку сразу умножили) мы сразу посчитаем 4 * 4 = 16, а потом получим:
res = 2 * 2 * 2 * 2 * 2 = 2 * 4 * 4 = 2 * 16 = 32
Надеюсь понятно объяснил, но в любом случае на сайте будет еще понятней: ссылка
Так же есть алгоритм, которому требуется в среднем logn / 2 операций умножения в отличии от стандартного алгоритма, где требуется n - 1 операций умножения. Расписывать его не стану, лишь оставлю ссылку на статью в википедии.
А насчет алгоритм за O(n^2) честно не слышал о таком :), но и зачем только такой нужен.