시간 복잡도 계산

정말 당연한 것인데 이 당연하게 때론 너무 헷갈리거나 까먹을때가 있다 ㅠㅠ

$O(1)$

정해진 상수 시간의 루프나 함수 호출은 o(1)만큼의 시간 복잡도를 가진다.

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

}

$O(n)$

함수나 프로그램이 입력 크기 n 을 탐색한다면, 시간 복잡도는 o(n) .

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

}

$o(nc)$

어떤 n 루프 안에서 n-루프가 실행된다면 중첩된 루프의 개수 c가 시간 복잡도가 된다. 예를 들어 2번 중첩된 경우 시간복잡도는 o(n^2)가 된다.

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

   for (int j=0;j<k;i++){
	}

}

$o(logn)$

함수(나 프로그램)이 입력 크기 n을 로그적으로(i가 상수 c를 곱하여 증가하거나 c를 나누어 감소한다면) 탐색한다면, 그것의 시간복잡도는 O(Logn)이다. 예를 들면, 아래의 프로그램은 O(Logn)이다.

for (int i=0;i<n;i*=c)
{
   O(1)의 알고리즘
}

참고