вот думаю, что Օ(n^2), но не уверен․
https://www.geeksforgeeks.org/writing-power-function-for-large-numbers/
Что означает "количество умножений" и почему ты предполагаешь что количество это асимптотика?
Сказали, нужно посчитать количество шагов умножений․ И намекнули на Օ();
Именно этого алгоритма? Про нормальные алгоритмы подведения в степень можешь почитать тут https://seriouscomputerist.atariverse.com/media/pdf/book/Art%20of%20Computer%20Programming%20-%20Volume%202%20(Seminumerical%20Algorithms).pdf 474 страница в пдф, или 461 страница в самой книге. Раздел 4.6.3
А разве другие алгоритмы смогут посчитать такие большие числа?
почему n^2?
Из-за циклов, я так думаю
Обсуждают сегодня