x^y 계산의 실행 시간

Question

(y − 1) 곱셈을 수행하는 x을 수행하는 기본 알고리즘의 실행 시간 (Big-O 표기법)을 찾으려면 어떻게해야합니까? x^y을 찾으십니까?

편집 : 또한 각 곱셈의 실행 시간을 염두에 두어야합니다. "n-bit 번을 m-bit 번으로 곱하는 시간을 O(mn)으로 가정하십시오."

Answer 1

글쎄, 각 연산의 비트 수를 고려한 다음 합하면됩니다. 물론 big-O 표기법 응답에는 영향을 미치지 않기 때문에 간단히하기 위해 약간의 반올림을 수행합니다.

따라서 x의 비트 수가 ceiling (log2 (x)) (즉, x의 대수 2 위의 다음 정수)입니다. 간단히하기 위해이 번호를 b라고 부릅니다. 이것은 x가 2^(b-1)보다 크고 2^b보다 작음을 의미합니다. 따라서 x^2는 2^(2 (b-1))보다 크고 2^(2b)보다 작습니다. 따라서 x^2는 크기가 약 2b이고, 일반적으로 x^n은 크기 nb라고 가정합니다. 이것은 n (b-1)과 nb 사이에 있기 때문에 정정에 거의 가깝습니다.

첫 번째 곱셈에는 b * b = b^2의 시간이 걸립니다. 두 번째 곱셈은 2b * b를 취합니다 (x^2는 크기가 2b이고 x는 여전히 크기 b 임). 우리의 세 번째는 3b * b가 될 것입니다 (x^3는 크기가 3b이고 x는 여전히 크기 b입니다). 따라서 일반적으로 n 번째 곱셈은 nb * b가됩니다.

그래서 우리의 합계는 b^2 + 2b^2 + 3b^2 + ... + (y-1) b^2와 같습니다. 우리는 (b^2) (1 + 2 + 3 + ... + (y-1))을주는 b^2를 배제 할 수 있습니다. 두 번째 항, 1 + 2 + 3 + ... + (y-1)은 1 + 2 + 3 + ... + n = n (n + 1)/2의 공통 수식을 사용할 수 있습니다. 따라서 (b^2) (y-1) (y)/2가됩니다.

이 시점에서 우리는 대답에 매우 가깝지만 두 가지 작업을 수행하고자합니다. 우리는 x와 y (b가 아닌)로 모든 것을 표현하기를 원하며 big-O 단순화를위한 표기. (y-1) (y)/2는 O (y^2)로 단순화 될 수있다. b = ceiling (log2 (x))이며 O (log (x))로 단순화 할 수 있습니다. 다시 대입하면 O ((log (x))^2 * y^2)이됩니다.

이 모든 물론, 우리는 다음과 같습니다 알고리즘을 사용하고 있다고 가정한다

:

product = 1 
for i = 1 to y 
    product = product * x 
return product 

우리는 이와 같은 일이 더 복잡하고 이상한 일을하는 경우 :

xs = empty list 
for i = 1 to y 
    xs.addItem(x) 
while xs is not empty 
    num1 = xs.removeRandomItem 
    num2 = xs.removeRandomItem 
    xs.addItem(num1*num2) 
return head(xs) 

타이밍 분석이 더욱 복잡해집니다. (이 알고리즘은 또한 Y-1 승산을 수행하고 정확한 결과를 얻을 수 있습니다.)

X^Y를 찾기위한 다른 일반적인 알고리즘이다 같이 작동 반복 제곱 알고리즘 : 그 내용

result = 1 
temp = x 
while y>0 
    if y mod 2 = 1 
    result = result * temp 
    y = y - 1 
    temp = temp * temp 
    y = y/2 
return result 

하나는 두 개의 숫자를 포함하는 두 개의 곱셈을하고, 각각은 크기 b (2^n)입니다. 여기서 n은 0부터 세는 라운드 숫자입니다 (즉, while 루프를 통과 한 횟수). 그래서 라운드 n에서, 각 곱셈은 b (2^n) * b (2^n) = (b^2) (2^(2n))의 비용이들 것입니다. 그러나 그것은 단지 천장 (log2 (y)) 라운드가됩니다. 따라서 실행 시간은 (b^2) (2^0) + (b^2) (2^2) + (b^2) (2^4) + ... +) (2^(2 * ceiling (log2 (y)))). 그래서 다시 우리는 (2^0 + 2^2 + 2^4 + ... + 2^2 (2 * ceiling (log2 (y))))를 떠나는 b^2를 배제 할 수 있습니다. 복잡 해 보이지만, 두 번째 용어는 실제로 O (y^2)입니다. 우리가 다시 b를 대입하면,이 또한 O ((log (x))^2 * y^2)라는 것을 알 수 있습니다. 따라서 곱셈이 일정 시간 연산 일 때이 알고리즘이 더 빠르지 만 BigInteger 또는 기타 임의 정밀도 유형을 사용할 때 반드시 더 빠를 필요는 없습니다. 이것이 곱셈을하는 비용이 일정하지만 크기가 큰 행렬 곱셈과 같은 상황에서 가장 일반적으로 사용되는 이유입니다.

Answer 2

O 선택한 방법에 따라 (말의 뜻) 또는 O (Y), 당신은 시작할 가정, 단계 (Y-1) 곱셈의 O (Y) 번호를 귀하의 경우에는이 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4

을 읽는한다 곱셈은 ​​하나의 연산입니다. y의 크기를 두 배로 늘리면 필요한 연산량이 두 배로 늘어나므로이를 선형 프로세스라고합니다.

LE :이 경우 1 * n^2 + 2 * n^2 + ... + y * n^2가됩니다. 처음에 숫자를 곱하면 n * n = n^2 두 번째로 결과 n * n (크기 2n)을 숫자 n => 2n^2 등으로 곱합니다.

N^2 (1 + 2 + ... Y) = N^2 * 및 y * (Y + 1)/2

그래서 응답이 O 인 (N^2 * Y^2) 여기서, n = x의 비트 수 (또는 n = ceil (log (x))).

Answer 3

각 곱셈이 단일 연산으로 계산되는 경우 y - 1 단계가 필요한 알고리즘은 간단히 O(y - 1) = O(y)이며이 질문에 대한 가장 일반적인 대답입니다. 실제로, 곱셈은 일정 시간에 수행 될 수 없으므로 사용중인 multiplication algorithm의 속도로 곱해야합니다.

exponentiation by squaring을 사용하면 y - 1 개 미만의 작업을 수행 할 수 있고 지수 알고리즘은 O(log y)이 될 수 있습니다.