계산 복잡도?

Question

나는 다음과 같은 기능의 복잡성을 계산하기 위해 노력했습니다 : 특히

k=n; 
while(k>0) 
    g(n); 
    k=k/2; {Comment: this is integer division, so 1/2=0} 
end while; 
for(j=0;j<m;j++) 
    f(m); 

를, 그동안의 loop.I의 복잡성은 g (N)의 복잡도는 O (N), 그러나 것을 듣는다 나는 그 복잡성이 무엇인지, 그리고 어떻게 해결할 수있을 지 확신하지 못한다. 나는 복잡성이 O (0.5n^2)가 아닐 것이라는 것을 깨닫게되었지만, 매번 반으로 자르기 때문에 그것을 계산하는 방법을 확신 할 수 없다. 누구든지 아이디어가 있습니까? g (n은)

더 설명하기 위해 (n)이 O, 당신의 복잡도는 O (N N * 로그()) 인 경우

Answer 1

, 우리가 순간

k = n; 
while(k > 0) { 
    k = k/2; 
} 

에 대한 g (N)를 무시하자

하자 말 N = 1000

그럼 우리가

Pass | k 
------------- 
0 | 1000 
1 | 500 
2 | 250 
3 | 125 
4 | 62 
5 | 31 
6 | 15 
7 | 7 
8 | 3 
9 | 1 
10 | 0 (stopped) 

로그 (1000) = 9.96K의 다음과 같은 값을 얻을 것이다k를 0으로 낮추는 데 10 번만 걸렸습니다. 이것은 log (n) 계산 복잡성의 예입니다. 당신은 (N * 로그 (N))

Answer 2

의 미국 O의 총합을주는 모든 반복에 대한 O (N)를 추가 수단 루프 내부 g (N)를 추가이어서

while 루프의 복잡성은 분명히 O(n log n)입니다. 각 반복 끝에 k을 2로 나눈 값이므로 log n 반복이 있습니다. 반복 횟수를 얻으려면 n을 2의 제곱으로 표현하십시오 (예 : 2^x). 2^x=n, then x = log n. 이것이 while 루프의 복잡성이 O(n log n) 인 이유입니다. n은 2의 거듭 제곱이 아니기 때문에 혼동하지 마십시오. log n은 항상 정수가 아니므로 로그 n 대신 [log n]을 써야합니다. 여기서 [y]은 y의 정수 부분입니다. [log n]을 항상 c* log n으로 표현할 수 있습니다. 여기서 c는 알고리즘의 복잡성을 변경하지 않는 상수입니다. 따라서 [] 함수가 필요하지 않으며 O(n log n)이 적합하고 정답입니다.

for 루프의 복잡도는 f(m)의 복잡도에 따라 다릅니다. O (f (m))가 O(1)이면 루프는 O (m)이지만, O(f(m))이 O(m)이면 루프는 O(m^2)입니다. f(m)도 알고리즘의 일부이기 때문에 전체 코드의 복잡성을 확실하게 알고 싶다면 f(의 복잡성을 알아야합니다.

Answer 3

알고리즘의 복잡성은 다음과 같습니다

첫 번째 루프는 O (logn) 시간을 실행하고 각 반복은 g (N)를 수행한다. 따라서 걸릴

O(sum{i from 0 to log(n)}{O(g(i))}). 

두 번째 루프는 m 번 실행됩니다.그것은 취 알고리즘의

O(sum{j from 0 to m}{O(f(i))}) 

총 복잡성은 다음과 같습니다 문제의 크기는 각각의 반복을 절반으로되어있는 경우

이

O(sum{i from 0 to log(n)}{O(g(i))}) + O(sum{j from 0 to m}{O(f(i))})