给定一个整数x和一个正数y，编写一个计算x的函数 Y 在下列情况下。 a） 函数的时间复杂度应为O（logy） b） 额外的空间是O（1）
null
例如：
Input: x = 3, y = 5Output: 243Input: x = 2, y = 5Output: 32
我们强烈建议您在继续解决方案之前单击此处并进行练习。
我们讨论过 电源的递归O（对数y）解决方案 .递归解决方案通常不是首选方案，因为它们需要调用堆栈上的空间，并且涉及函数调用开销。
下面是计算x的实现 Y .
C++
// Iterative C program to implement pow(x, n) #include <iostream> using namespace std; /* Iterative Function to calculate (x^y) in O(logy) */ int power( int x, unsigned int y) { int res = 1; // Initialize result while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = res * x; // y must be even now y = y >> 1; // y = y/2 x = x * x; // Change x to x^2 } return res; } // Driver program to test above functions int main() { int x = 3; unsigned int y = 5; cout<< "Power is " <<power(x, y); return 0; } // this code is contributed by shivanisinghss2110 |
C
// Iterative C++ program to implement pow(x, n) #include <stdio.h> /* Iterative Function to calculate (x^y) in O(logy) */ int power( int x, unsigned int y) { int res = 1; // Initialize result while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = res * x; // y must be even now y = y >> 1; // y = y/2 x = x * x; // Change x to x^2 } return res; } // Driver program to test above functions int main() { int x = 3; unsigned int y = 5; printf ( "Power is %d" , power(x, y)); return 0; } |
JAVA
// Iterative Java program // to implement pow(x, n) import java.io.*; class GFG { /* Iterative Function to calculate (x^y) in O(logy) */ static int power( int x, int y) { // Initialize result int res = 1 ; while (y > 0 ) { // If y is odd, // multiply // x with result if ((y & 1 ) == 1 ) res = res * x; // y must be even now y = y >> 1 ; // y = y/2 x = x * x; // Change x to x^2 } return res; } // Driver Code public static void main (String[] args) { int x = 3 ; int y = 5 ; System.out.println( "Power is " + power(x, y)); } } // This code is contributed // by aj_36 |
Python3
# Iterative Python3 program # to implement pow(x, n) # Iterative Function to # calculate (x^y) in O(logy) def power(x, y): # Initialize result res = 1 while (y > 0 ): # If y is odd, multiply # x with result if ((y & 1 ) = = 1 ) : res = res * x # y must be even # now y = y/2 y = y >> 1 # Change x to x^2 x = x * x return res # Driver Code x = 3 y = 5 print ( "Power is " , power(x, y)) # This code is contributed # by ihritik |
C#
// Iterative C# program // to implement pow(x, n) using System; class GFG { /* Iterative Function to calculate (x^y) in O(logy) */ static int power( int x, int y) { int res = 1; // Initialize result while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) == 1) res = res * x; // y must be even now y = y >> 1; // y = y/2 x = x * x; // Change x to x^2 } return res; } // Driver Code static public void Main () { int x = 3; int y = 5; Console.WriteLine( "Power is " + power(x, y)); } } // This code is contributed // by aj_36 |
PHP
<?php // Iterative php program // to implement pow(x, n)> // Iterative Function to // calculate (x^y) in O(logy) function power( $x , $y ) { // Initialize result $res = 1; while ( $y > 0) { // If y is odd, multiply // x with result if ( $y & 1) $res = $res * $x ; // y must be even now // y = y/2 $y = $y >> 1; // Change x to x^2 $x = $x * $x ; } return $res ; } // Driver Code $x = 3; $y = 5; echo "Power is " , power( $x , $y ); // This code is contributed by ajit ?> |
Javascript
<script> // Iterative Javascript program to implement pow(x, n) /* Iterative Function to calculate (x^y) in O(logy) */ function power(x, y) { // Initialize result let res = 1; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = res * x; // y must be even now y = y >> 1; // y = y/2 x = x * x; // Change x to x^2 } return res; } // Driver program to test above functions let x = 3; y = 5; document.write( "Power is " + power(x, y)); // This code is contributed by Mayank Tyagi </script> |
输出：
Power is 243
时间复杂性： O（对数y）
辅助空间： O（1）
本文由 乌迪特·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
