코드의 시간 복잡성 분석
https://stackoverflow.com/questions/1433530
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
int foo(int n)
{
int x=2;
while (x<n)
{
x = x*x*x;
}
return x;
}
시간 복잡성을 분석해야합니다. 나는 그것이 도달하는 것을 보았다 n 단지보다 훨씬 빠릅니다 log(n). 내 말은, 그것은보다 적은 단계를 수행합니다 O(log(n)) 할것이다. 나는 대답을 읽었지만 그들이 어떻게 그것에 도달했는지 전혀 모른다 : 그것은 O(log(log(n)). 이제 그런 질문에 어떻게 접근합니까?
해결책
허락하다
L3 =베이스 3에 로그L2 =베이스 2에 로그
그러면 정답이 있습니다 O (l3 (l2 (n)) 그리고 O가 아님 (L2 (l2 (n)).
시작합니다 x = x * 2. X는 n에 도달 할 때까지 기하 급수적으로 증가하여 시간 복잡성 O (l2 (n))가됩니다.
이제 고려하십시오 x = x * x. x는 위보다 빠르게 증가합니다. 모든 반복에서 X 값은 이전 값의 제곱으로 점프합니다. 간단한 수학을하면 여기에 우리가 얻는 것이 있습니다.
x = 2 n = 4의 경우, 반복이 취해졌다 = 1 n = 16, 반복은 = 2 n = 256, 반복이 찍은 = 3 n = 65536, 반복을 취했다 = 4
따라서 시간 복잡성은입니다 O (L2 (L2 (N)). n에 대한 값 위의 값을 올려서 이것을 확인할 수 있습니다.
이제 당신의 문제에오고 있습니다. x = x * x * x. 이것은 x = x * x보다 훨씬 빠르게 증가합니다. 테이블은 다음과 같습니다.
x = 2 n = 8의 경우, 반복이 찍은 = 1 n = 512, 반복은 = 2 n = (512*512*512), 반복은 = 3 등
이것을주의 깊게 보면 이것은 O (l3 (l2 (n)). L2 (n)는 두 가지의 힘을 얻을 수 있지만, 모든 반복에서 X의 큐브를 복용하고 있으므로 올바른 반복 수를 찾으려면 기본 3에 로그를 가져 가야합니다.
그래서 나는 정답이라고 생각합니다 o (로그-투-베이스 -3 (log-to-base-2 (n))
이것을 일반화합니다 x = x * x * x * x * .. (k Times), 시간 복잡성은입니다 o (로그-투-베이스 -K (로그-투-베이스 -2)
다른 팁
그것을 재귀 기능으로 생각하십시오.
f(i) = f(i-1)^3
확장하면 :
f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)
함수는 전원의 힘으로 성장합니다. 따라서 특정 숫자 (즉, 함수의 역수를 계산하는)에 도달하는 시간 (반복)은 로그의 로그입니다.
당신의 예에서와 같이 f(0) = 2, 우리는 언제 알고 싶습니다 f(i) >= n 존재 n 입력 매개 변수 (및 i 반복 수) :
f(i) = 2^(3^i) >= n
3^i >= log_2(n)
i >= log_3(log_2(n))
따라서 값에 도달합니다 n, 그것 takes log_3(log_2(n)) 반복 (정수를 다루는 동안 반올림).
함수가 다음과 같은 경우 :
f(i) = 2*f(i-1) //e.g. x=2*x
그런 다음 패턴은 다음과 같습니다.
f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)
그리고이 경우, 함수의 역수는 기본 2의 단일 로그가 될 것입니다.
내 수학은 그다지 엄격하지는 않지만 아이디어를 얻을 수 있기를 바랍니다.
루프를 통한 반복 횟수에 따라 X가 어떻게 변하는 지 생각해보십시오. 매번, 당신은 그것을 큐브합니다. 반복 후에는 값이 2 입방체가되고 다시 큐브가됩니다. x (i)를 사용 하여이 표현을 나타냅니다. x (0) = 2, x (1) = 2라고 가정 해 봅시다3 등 (a를 사용하고 있습니다B는 Bth 파워로 올라간 것을 의미합니다).
우리는 x (i)> = n 때 끝났습니다. 얼마나 시간이 걸려요? 내가 해결합시다.
First, we take a log on both sides: ln(x(i))>=ln(n) ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i) (the above uses [this property][1]: ln(x**b)==ln(x)*b) so, 3**i * 2 >=ln(n). Let's take another logarithm: ln(3**i * 2) = ln(2) + ln(3)*i so ln(2) + ln(3)* i >= ln(ln(n)) Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)
우리는 지속적인 요인을 무시할 수 있으며 로그 (로그 (N)) 단계를 수행 할 것이라는 결론이 남아 있습니다. 그것이 당신의 알고리즘의 복잡성입니다.
바라건대, 그런 모든 단계를 세분화하면 도움이됩니다.
내부의 코드가 while 루프 인 경우
x = 2*x;
x는 O (log (n)) 반복에서 n에 도달합니다. X를 일정하게 곱하는 대신 X를 큐빙하기 때문에 더 빨리 N에 도달하게됩니다.
주어진
log ( A * x ) == log ( A ) + log ( x )
log ( x * x * x ) == 3 * log ( x )
그래서
log ( log ( x * x * x ) ) == log ( 3 * log ( x ) )
== log ( 3 ) + log ( log ( x ) )
이 함수는 기능보다 얼마나 빠르거나 느리게 (루프의 반복 수로 측정)?
int log_foo ( int n )
{
double log_x = log ( 2 );
const double log_n = log ( n );
while ( log_x < log_n )
{
log_x = 3 * log_x;
}
return exp ( log_x );
}
그리고이 기능은 당신의 기능보다 얼마나 빠르거나 느리게됩니까?
int log_log_foo ( int n )
{
double log_log_x = log ( log ( 2 ) );
const double log_log_n = log ( log ( n ) );
const double log_3 = log ( 3 );
while ( log_log_x < log_log_n )
{
log_log_x += log_3;
}
return exp ( exp ( log_log_x ) );
}
그러나이 함수는 증가합니다 log_log_x 상수적으로는 반복의 수를 쉽게 해결할 수 있습니다.
허락하다 i 반복 단계의 수와 x(i) 의 가치 x ~ 후에 i 단계. 우리는 가지고 있습니다
x(0) = 2
x(i) = x(i-1)³
총 단계 수가 가장 크다 i ~하도록 하다 x(i) < n.
우리는 가지고 있습니다
log x(i) = log x(i-1)³
= 3·log x(i-1)
= 3·log x(i-2)³
= 3²·log x(i-2)
= 3^i·log x(0)
= 3^i·log 2
⇒ log log x(i) = log (3^i·log 2)
= log 3^i + log log 2
= i·log 3 + log log 2
로그가 엄격하게 증가하고 있습니다
x(i) < n ⇔ log log x(i) < log log n
⇔ i·log 3 + log log 2 < log log n
⇔ i < (log log n - log log 2) / log 3 ∈ O(log log n)
루프의 반복 수를 계산하기 위해 카운터 변수를 추가하지 않겠습니까? 함수가 돌아 오기 직전에 인쇄하십시오.
그런 다음 기능을 호출하여 다양한 값, 예를 들어 3 ~ 1,000,000으로 시작하십시오. 그런 다음 같은 것을 사용하여 결과를 표시하십시오 gnuplot.
그런 다음 그래프가 알려진 곡선과 일치하는지 확인하십시오.
