1.시간 복잡도 빅오 표기법 O(N)

시간 복잡도(time complexity)란 가장 널리 사용되고 있는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 ㄴ수행하는 기본적인 연산의 수를 입력 크기에 대한 함수로 표한한 것이다.

 

그리고 표현을 할때 O표기를 하는데

역기서 O표기를 할때 변수의 차수가 큰 것을 따라간다.

n^2+5n => O(n^2)

n^3+100n^2 => O(n^3)

n^2*m+m^2*n+3 => O(n^2*m+m^2*n)

 

근데 시간복잡도가 낮다고 해서 언제나 더 빠르게 작동하는 것은 아니다. 

밑에 그래프를 보면 알 수 있듯이. 복잡도가 낮다고해서 더 빠르게 작동하는 것이 아니라

일정 구간 이상부터 빠르게 작동하는 것을 알 수 있다. 

 

우리가 1부터 n까지의 합을 구할 때 

int sum=0; 

for(int i=0; i <n; i++){

    sum=sum+i;

}

printf("합:%d", sum);

 

시간 복잡도는 O(n) 

 

그렇지만  n까지의 합공 식이 n*(n+1)/2 인 것을 알고

 

for문을 지우고 sum=n*(n+1)/2 이렇게 쓰면 시간 복잡도는 O(1)이 된다.

 

 

공간 복잡도도 설명해주고 싶은데 시간 복잡도랑 거의 같아서 어떻게 설명해야 될지 모르겠어가지고

설명을 못하겠습니다. 그리고 실력이 뭘 알려줄 실력이 아니라서 이거 하면서 정리하는 거라 ㅎㅎ 

참고가 됐다면 감사합니다. ㅎㅎ