Имплементация функции возведения в степень

Средняя
medium , math , recursion
28 September 2023

Описание задачи #

Напишите функцию, которая будет возводить число x в степень n.

Входные данные: x (float64), n (int)

Выходные данные: float64 (результат возведения числа x в степень n)

Ограничения #

Примеры #

  • Входные данные

    x = 2.00000
n = 10

    Ответ: 1024.00000

  • Входные данные

    x = 2.10000
n = 3

    Ответ: 9.26100

  • Входные данные

    x = 2.00000
n = -2

    Ответ: 0.25000

Брутфорс решение #

Так как возведение в степень — результат умножения числа x само на себя n раз, брутфорс решение можно написать используя обычный цикл (пока предположим, что n всегда > 0):

res := x

for ; n > 1; n-- {
    res *= x
}

return res

Для того чтобы учесть кейсы с отрицательным n, вспомним свойство степеней.

$$ x^{-n} = {1 \over x^n} $$

Таким образом, вынесем возведение в положительную степень в отдельную функцию.

func powAbsNBruteforce(x float64, n int) float64 {
	if n == 0 {
		return 1
	}

	if n == 1 {
		return x
	}

	res := x

	for ; n > 1; n-- {
		res *= x
	}

	return res
}

А в основной функции добавим проверку на отрицательность n.

if n < 0 {
    return 1 / powAbsNBruteforce(x, -1*n)
}

return powAbsNBruteforce(x, n)

Итоговое решение.

  • package main

func myPowBruteforce(x float64, n int) float64 {
	if x == 1 {
		return 1
	}

	if x == -1 {
		if n%2 == 0 {
			return 1
		}

		return -1
	}

	if n < 0 {
		return 1 / powAbsNBruteforce(x, -1*n)
	}

	return powAbsNBruteforce(x, n)
}

func powAbsNBruteforce(x float64, n int) float64 {
	if n == 0 {
		return 1
	}

	if n == 1 {
		return x
	}

	res := x

	for ; n > 1; n-- {
		res *= x
	}

	return res
}

  • const powAbsNBruteforce = (x: number, n: number): number => {
    if (n === 0) {
        return 1
    }

    if (n === 1) {
        return x
    }

    let res = x

    for (n; n > 1; n--) {
        res *= x
    }

    return res
}

export const myPowBruteforce = (x: number, n: number): number => {
    if (x === 1) {
        return 1
    }

    if (x == -1) {
        if (n % 2 === 0) {
            return 1
        }

        return -1
    }

    let res: number

    if (n < 0) {
        res = 1 / powAbsNBruteforce(x, -1 * n)
    } else {
        res = powAbsNBruteforce(x, n)
    }

    return parseFloat(res.toFixed(5))
}

Оценка сложности #

По времени

Для вычисления степени нам нужно произвести n умножений, то есть сложность - O(n).

По памяти

O(1) — дополнительная память константна.

Оптимальное решение #

Мы можем сократить кол-во умножений, если вспомним одно из свойств степеней.

$$ x^n = {(x * x)^{n \over 2}} $$

Например: 28 = 44 = 162 = 256.

Таким образом, мы можем переписать нашу функцию на рекурсивную, не забывая отдельно обработать кейс с нечетной степенью:

  • package main

func myPow(x float64, n int) float64 {
	if x == 1 {
		return 1
	}

	if x == -1 {
		if n%2 == 0 {
			return 1
		}

		return -1
	}

	if n < 0 {
		return 1 / powAbsN(x, -1*n)
	}

	return powAbsN(x, n)
}

func powAbsN(x float64, n int) float64 {
	if n == 0 {
		return 1
	}

	if n == 1 {
		return x
	}

	if n%2 != 0 {
		return powAbsN(x*x, n/2) * x
	}

	return powAbsN(x*x, n/2)
}

  • const powAbsN = (x: number, n: number): number => {
    if (n === 0) {
        return 1
    }

    if (n === 1) {
        return x
    }

    if (n % 2 != 0) {
        return powAbsN(x * x, Math.floor(n / 2)) * x
    }

    return powAbsN(x * x, Math.floor(n / 2))
}

export const myPow = (x: number, n: number): number => {
    if (x === 1) {
        return 1
    }

    if (x === -1) {
        if (n % 2 === 0) {
            return 1
        }

        return -1
    }

    let res: number

    if (n < 0) {
        res = 1 / powAbsN(x, -1 * n)
    } else {
        res = powAbsN(x, n)
    }

    return parseFloat(res.toFixed(5))
}

Оценка сложности #

По времени

В этом подходе на каждой итерации рекурсии мы возводим число в квадрат, вдвое снижая количество требуемых умножений. То есть итоговая сложность — O(log n).

По памяти

O(1) — дополнительная память константна.

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >