재귀 계승 프로그램의 복잡성

Question

숫자 n의 계승을 찾는 재귀 프로그램의 복잡성은 무엇입니까? 나의 직감은 그것이 O(n)일지도 모른다라는 것이다.

Answer 1

곱하기를 O(1)으로 설정하면 예 : O(N)이 올바른 것입니다. 그러나 임의의 길이의 두 숫자를 곱하면 x이 이 아니며 유한 하드웨어의 경우O(1)이 아니므로 x이 무한 할 경우 곱셈에 필요한 시간이 길어집니다 (예 : Karatsuba multiplication 인 경우는 O(x ** 1.585)).

Schönhage-Strassen으로 충분히 큰 숫자를 이론적으로 더 잘 수행 할 수는 있지만 실제 경험이 없다고 고백합니다. x "길이"또는 "자릿수"(물론 N의 big-O는 중요하지 않음)는 O(log N)과 함께 자랍니다.

질문의 계승을 의미하는 경우 충분히 짧은 번호는 "무한대로 경향이있다"수있는 방법 N 없다, O(1)에 거는 때문에 큰 O 표기법은 부적절한

Answer 2

을 가정 이제까지 가장 순진 계승 알고리즘에 대해 얘기하고 :.

factorial (n): 
    if (n = 0) then return 1 
    otherwise return n * factorial(n-1) 

예, 알고리즘은 선형이며 O (n) 시간으로 실행됩니다 .T 그 경우는 값 n을 감소시킬 때마다 한 번 실행하고 값이 에 도달 할 때까지 값 n을 감소 시키므로이 함수는 재귀 적으로 n 번 호출됩니다. 물론 이것은 감소 및 곱셈이 모두 일정한 연산이라고 가정합니다.

물론 계승을 다른 방법으로 구현하면 (예를 들어, 곱셈 대신에 덧셈을 사용하는 등) 훨씬 복잡한 알고리즘으로 끝날 수 있습니다. 그래도 그런 알고리즘을 사용하는 것은 권장하지 않습니다.

Answer 3

알고리즘의 복잡성을 표현할 때 항상 입력 크기의 함수로 사용됩니다. 곱하는 숫자가 고정 크기 인 경우 곱셈이 O(1)이라고 가정하는 것이 유효합니다. 예를 들어, 행렬 곱을 계산하는 알고리즘의 복잡성을 결정하려면 행렬의 개별 구성 요소가 고정 크기라고 가정합니다. 그런 다음 두 개의 개별 행렬 구성 요소를 곱하면 O(1)이라고 가정하면 각 행렬의 항목 수에 따라 복잡성을 계산할 수 있습니다. 그러나

, 당신은 당신이 N 임의로 커질 수 있다고 가정해야 N!를 계산하는 알고리즘의 복잡성을 파악하려면, 그래서 그 곱셈을 가정하는 유효하지 않은 O(1) 작업입니다.

n 비트 숫자에 m 비트 숫자를 곱하려면 순진한 알고리즘 (손으로하는 종류)에 시간이 O(mn) 걸리지 만 더 빠른 알고리즘이 있습니다. 만약 루프 용의 k 번째 단계에서 다음

factorial(N) 
     f=1 
     for i = 2 to N 
      f=f*i 

     return f 

N!을 계산 쉬운 알고리즘의 복잡성을 분석 할 경우

, 넌 k 의해 (k-1)! 승산된다.(k-1)!을 나타내는 데 사용되는 비트 수는 O(k log k)이고 k을 나타내는 데 사용되는 비트 수는 O(log k)입니다. 따라서 (k-1)!과 k을 곱하기 위해 필요한 시간은 O(k (log k)^2)입니다 (순진한 곱셈 알고리즘을 사용한다고 가정). 당신은 Schönhage-처럼 빠른 곱셈 알고리즘을 사용하여 성능을 향상시킬 수

sum k = 1 to N [k (log k)^2] <= (log N)^2 * (sum k = 1 to N [k]) =
O(N^2 (log N)^2)

: 그런 다음 알고리즘에 의해 걸리는 시간의 총량은 각 단계에서 걸리는 시간의 합이다 Strassen은 2 n 비트 숫자에 대해 O(n*log(n)*log(log(n))) 시간이 걸립니다.

성능을 향상시키는 다른 방법은 더 나은 알고리즘을 사용하여 N!을 계산하는 것입니다. 가장 빠른 것은 먼저 N!의 소수 분해를 계산 한 다음 모든 소수 요소를 곱합니다.