알고리즘 분석, 알고리즘의 시간 복잡도

Question

m=1; 
for(i=1;i<=n;i++){ 
    m=m*2; 
    for(j=1;j<=m;j++){ 
     do something that is O(1) 
    } 
} 

위 코드의 시간 복잡도는 어떻게됩니까 ?? 이러한 유형의 문제를 해결하는 방법을 알려주십시오.

Answer 1

내부 루프는 1 회 반복하고, 2 회 반복 한 다음 2 회 반복합니다. 그래서 우리는 내부 반복의 1 + 2 + 4 + ... + 2^n = 2^(n + 1) - 1 = O(2^n) 반복을가집니다.

내부 루프의 반복에는 일정한 복잡성이 있으므로 summed_inner_loop_complexity = O(2^n)입니다.

전체 복잡도는 O(2^n)입니다.

Answer 2

나는 내부에서 이러한 문제를 보는 것을 선호합니다. m 제거, 우리는이 :

for(i=1;i<=n;i++){ 
    for(j=1;j<=2^i;j++){ 
     do something that is O(1) 
    } 
} 

또는 :

for(i=1;i<=n;i++){ 
    O(2^i) 
} 

그래서 전체 : sum_1^n O(2^i)=O(2^(n+1))=O(2^n)합니다. 공식적으로 그리고 조직적으로

Answer 3

, 당신은 시그마 표기법을 사용할 수 있습니다 : 당신은 n``곱, 또는 (더 나은) 합산 된 내부 루프의 복잡성을 얻을 수 있지만, 모두 당신이 이상있어 의미 할 수