Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняСтатья 31 ЛитКодексаВ статье рассмотрим 50-й вопрос LeetCode, найдем степень числа.
смысл названия
Смысл этого вопроса только в одном предложении, то есть заданы два числа x и n, спросить
.
С точки зрения смысла вопроса, этот вопрос обычный и в принципе ничего особенного. Но мы продолжаем смотреть на его примечание и найдем задачу, где x — число с плавающей запятой и его диапазон от -100 до 100. и диапазон n32-битное целоедиапазона, здесь есть проблема.
Потому что, если n велико, мы используем цикл для вычисления
Время точно истечет. Мы обсуждали этот вопрос раньше, даже самый быстрый C++, количество операций в секунду составляет всего около 10 в 8-й степени. 32-битное целое число достигает 10 в степени 9. Если это Python, эта операция будет медленнее, поэтому мы не сможем получить результат с помощью цикла.
быстрая сила
Эта проблема ограничивает сложность до смерти Мы не можем думать о результате насильственного метода, и необходимо ввести новый алгоритм. Алгоритм решения этой задачи таков.быстрая сила.
Алгоритм быстрого возведения в степень также существеннодвоичная арифметикаДеформация , должна быть основана на нашем полном понимании бинарности, и в некоторой степени она похожа на бинарное расщепленное решение в задаче о нескольких рюкзаках. Оба целых числа нужно разбить, но разница заключается в суммировании результатов разбиения в задаче о рюкзаке, а здесь - суммировании.
Если вы не видели проблему с несколькими рюкзаками, ничего страшного, я объясню с самого начала.
Алгоритм быстрого питания легко понять, но его легко забыть, когда вы его поймете, особенно если вы новичок. Я понимаю это, когда изучаю, но забываю через два дня, иначе не могу написать код, это нормально. Итак, давайте начнем с фундаментальной проблемы и поймем ее в корне, а не только как она работает.
Первый вопрос: мыВ чем причина использования быстрых сил?
На этот вопрос легко ответить, потому чтобыстрыйАх, иначе мы можем использовать цикл для вычисления мощности. ноПочему быстрая сила — это быстроШерстяная ткань? Почему это быстрее, чем зацикливание?
На этот вопрос можно ответить, даже если мы не изучили алгоритм быстрого возведения в степень, и ответ на него тоже очень прост, потому что мыПреобразовать количество, которое нелегко найти, в количество, которое легко решить, тем самым уменьшая сложность. Звучит как ерунда, но на самом деле это суть многих алгоритмов. Алгоритмы не с неба свалились, и люди, которые их придумали, не просто так погладили себя по головке, в основе лежит принцип. Основной принцип многих алгоритмов заключается в использовании метода преобразования и подстановки для поиска значений, которые не особенно удобно находить. Этот метод не толькообычно используется в математике, и алгоритм тот же.
После того, как мы понимаем это ядро, остальное просто, мы знаем
Спросить непросто, потому что сейчас у нас нет хорошего решения, так какое же количество легко запросить? Как это преобразовать? Следуя этой линии мышления, мир перед нами становится намного яснее.
Изначально мы решили
Метод состоит в том, чтобы пройти цикл, умножить каждый цикл на x и получить результат после n циклов. Если мы понаблюдаем за этим процессом, мы обнаружим, что когда мы зацикливаемся, каждый цикл фактически представляет собойПоказатель x увеличивается на 1. То есть он растет линейно и, конечно, медленно. Что растет быстрее? Экспоненциальный рост относительно быстр, например, если мы удваивали и удваивали, это будет очень быстро. Есть известная история об экспоненциальном росте, что кто-то когда-то изобрел шахматы. Местный король очень любит играть в шахматы, поэтому он подозвал к себе изобретателя и сказал, ваше изобретение очень хорошее, я готов вознаградить вас, говорите, чем хотите, лишь бы я мог это дать.
Мужчина сказал: «Ваше величество, все, что мне нужно, — это просто немного риса». Я хочу 1 зернышко риса в первом ящике, 2 зерна во втором ящике и 4 зерна в третьем ящике. Каждая сетка в два раза больше предыдущей Пожалуйста, Ваше Величество, раздайте этот рис бедным в деревне.
Король был потрясен, подумав, что этот человек бессердечен, как такая хорошая возможность может нуждаться только в такой награде. Но все мы знаем, что в шахматах 88 864 клетки.
зерно риса. Это, очевидно,астрономический, не говоря уже о стране, риса в мире не так много. В рассказе не упоминается окончательный исход этого человека, весьма вероятно, что он был зарублен за то, что дразнил короля. Но каким бы ни был результат, по крайней мере он показывает проблему, экспоненциальный рост не соответствует нашей интуиции,меняется очень быстро.
Итак, мы надеемся, что было бы неплохо, если бы наш показатель степени мог расти экспоненциально, как здесь, а не просто увеличиваться на 1 каждый раз, так как же сделать так, чтобы показатель степени рос экспоненциально? Это очень просто,Просто квадрат.
Возводим в квадрат x, чтобы получить
, снова возводим его в квадрат, чтобы получить
, каждый раз, когда мы возводим в квадрат, индекс удваивается, как на шахматной доске в только что рассказанной истории. Таким образом, нам нужно только небольшое количество раз, чтобы показатель степени был очень большим.
Мы решили проблему экспоненциального роста, но столкнулись с новыми проблемами, мы так быстро растем, но он удвоился и удвоилсяне обязательно получать нА?
Эта проблема также проста, просто найдите способ получить ее напрямую.Минатоповторять Например, если наше n=15, мы сначала находим наибольшую степень числа 2 меньше 15 и обнаруживаем, что она равна 8. Итак, мы получили
, откладываем в сторону и у нас остается 7, снова делаем 7, находим 4, так что откладываем, у нас осталось 3, снова делаем 3... и так далее, пока не будет n. , n может быть составлен таким образом, потому что это, по сути, процесс преобразования в двоичный код.
Весь процесс я нарисовал на картинке, давайте посмотрим на следующую картинку:
Сначала мы вычисляем все степени числа 2, а затем вычисляем все степени числа 2 для x. Затем разбейте n на двоичные, умножьте значение соответствующей позиции 1 в двоичном формате и получите результат.
Некоторые учащиеся могут быть незнакомы с двоичными и битовыми операциями, поэтому я предоставлю две версии кода, чтобы помочь вам понять. Сначала рассмотрим простой код:
class Solution:
def myPow(self, x: float, n: int) -> float:
base = []
# 标记n是否为负数
flag = n < 0
# 把n置为正数
n = abs(n)
base.append(x)
# 我们算出所有的x^2^i
for i in range(32):
base.append(base[-1] * base[-1])
ret = 1.0
# 遍历32个二进制位
# 如果i位为1，那么答案乘上base[i]
for i in range(32):
if ((1 << i) & n) > 0:
ret *= base[i]
# 如果n为负数返回1/ret
return 1/ret if flag else ret
В приведенном выше коде мыРассчитать каждый
, а затем перемножаем их между собой в соответствии с результатом преобразования n в двоичное. Конечно, после того, как мы освоились, мы не можем быть такими трудоемкими, мы можем объединить эти два шага вместе, давайте посмотрим на кусок кода:
class Solution:
def myPow(self, x: float, n: int) -> float:
base = []
flag = n < 0
n = abs(n)
base = x
ret = 1.0
# 我们在遍历二进制位的时候顺便求出x^2^i
for i in range(32):
if ((1 << i) & n) > 0:
ret *= base
# x^2^i = x^2^(i-1) * x^2^(i-1)
base *= base
return 1/ret if flag else ret
Суммировать
Объяснение быстрой мощности здесь закончилось. Я лично считаю, что оно должно быть относительно ясным. Основная основа алгоритма по-прежнемубинарный, если концепция двоичного кода освоена, алгоритм быстрого возведения в степень тривиален.
Вам может показаться странным,Почему вы должны использовать двоичный код вместо троичного и четвертичного?, разве не быстрее? На это есть две причины: во-первых, нижний слой компьютера основан на двоичном коде, а мы не нашли хорошего материала для реализации троичного кода, потому что двоичный код очень прост.Логический вентиль открывается и закрывается, и для индикации состояния хорошо использовать высокий и низкий уровни., но какие материалы используются для реализации трех состояний? Вторая причина в том, что это не обязательно, мультибаза действительно быстрее, но она очень ограничена, так что в этом нет необходимости.
Я не боюсь шуток.Когда я только начинал, я всегда использовал глупый метод, описанный выше. И глядя на решение, я не нашел никого, кто так глупо писал fast power. ноНе имеет значения, если код глупый, чтобы быть в состоянии работать, чтобы быть в состоянии переменного тока, чтобы быть в состоянии понять это ключ. Это нормально — писать глупый код в начале, пока вы продолжаете совершенствоваться, вы, естественно, будете становиться все лучше и лучше в будущем.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.