Когда я был еще студентом Queens College, я собирался изучать алгоритмы компьютерных наук. Я столкнулся с этим конкретным вопросом, где меня просили вычислить число, возведенное в степень за время O (log N), и я был сбит с толку, потому что не мог понять, как это возможно.
Первое, что я сделал, - решил решить эту проблему так, как это было для меня понятно, и посмотреть, смогу ли я улучшить ее. Лучше иметь решение, чем в конце концов его не решать. Допустим, мы хотим вычислить 2⁵, тогда все это означает, что мне нужно умножить 2 * 2 * 2… пять раз.
function calculateExponent(base, exponent) { // 2,5
let result = 1;
let absExponent = Math.abs(exponent);
for (let i = 1; i <= absExponent; ++i) { // 1,2,3,4,5
result *= base; // 2,4,8,16,32
}
return exponent < 0 ? 1 / result : result;
}
}
Пока этот код работает. Он выполняется только за время O (N), где N - показатель степени. Поскольку большинство решений O (log N) можно решить с помощью метода «разделяй и властвуй», я должен попробовать применить его к этой проблеме. Разделить и победить, по сути, означает разделить проблему на две и решить второстепенные проблемы и продолжать делить эти второстепенные проблемы на две, пока вы не сможете это сделать. Например, если мы хотим вычислить, что это 2⁸, мы можем разделить эту задачу на две, и тогда она будет в результате на 2⁴ и 2⁴, а затем снова разделить эту проблему на две, 2² и 2², пока мы в конечном итоге не дойдем до 1.
2^8 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256 2^4 * 2^4 = 2^8 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256 2^4 = 2 * 2 * 2 * 2 = 16 2^2 * 2^2 = 2^4 = 2 * 2 * 2 * 2 = 16 2^2 = 2 * 2 = 4 2^1 * 2^1 = 2^2 = 2 * 2 = 4 2^1 = 2 = 2
В приведенном выше фрагменте мы можем решить для 2⁸, зная только 2¹, 2² и 2⁴, поскольку 2¹ * 2¹ = 2² и 2² * 2² = 2⁴ и 2⁴ * 2⁴ = 2⁸. Это намного лучше, чем умножение 2 * 2… 8 раз. В математике это называется «степенным законом». Если два числа умножаются друг на друга с одинаковым основанием, мы можем сложить показатели. Применяя этот закон, мы можем увидеть, как «разделяй и властвуй» может помочь нам в решении этой проблемы, чтобы получить время O (log N).
Что делать, если показатель нечетный? Если показатель имеет нечетную степень, тогда мы все равно можем использовать «разделяй и властвуй», но тогда мы также должны умножить подзадачи на основание. Например, 2⁷ все еще можно разделить на 2, чтобы получить 2³ * 2³, и все, что нам нужно сделать, это умножить этот результат на основание, потому что 2³ * 2³ * 2¹ = 2⁷.
2^7 = 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128 2^3 * 2^3 * 2^1 = 2^7 = 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128 2^3 = 2 * 2 * 2 = 8 2^1 * 2^1 * 2^1 = 2^3 = 2 * 2 * 2 = 8 2^1 = 2 = 2
Видно, что большинство проблем «разделяй и властвуй» решаются с помощью рекурсии. Я придумал следующее рекурсивное решение.
function calculateExponent(base, exponent) {
if (exponent < 0) {In this // exponent is negative
return 1 / calculateExponent(base, exponent * -1);
}
if (exponent === 0) { // base case
return 1;
}
let result = calculateExponent(base,Math.floor(exponent / 2));
return exponent % 2 === 0 ? result * result : result * result
base;
}
Пример: 2⁹
a) calculateExponent(2,9)
|
b) calculateExponent(2,4)
|
c) calculateExponent(2,2)
|
d) calculateExponent(2,1)
|
e) calculateExponent(2,0)
|
f) return 1; // 1, (2,0)
|
g) return 1 * 1 * 2; // 2, (2,1)
|
h) return 2 * 2; // 4, (2,2)
|
i) return 4 * 4; // 16, (2,4)
|
j) return 16 * 16 * 2; // 512, (2,9)
Существует также нерекурсивное решение со временем выполнения O (log N), и я настоятельно рекомендую вам решить его таким образом. Поэтому в следующий раз, когда вы столкнетесь с решением, требующим времени O (log N), всегда проверяйте, можно ли применить «разделяй и властвуй».
