[Algorithm] 시간복잡도(Time complexity)란?

시간복잡도(Time complexity)란?

작성한 코드의 실행 시간을 말합니다.

 

작성한 코드의 반복문, 입력 값 등을 통해 대략적으로 실행 시간을 추측할 수 있습니다.

 

 

아래 그래프는 

자료의 수가 증가함에 따라 소요되는 처리시간 증가율을 나타내는 그래프입니다.

 

 

하나하나 살펴보도록 하겠습니다!

 

 

O(1)

---

printf("Hello world!")

O(1)은 일정한 복잡도(constant complexity)이며, 입력값이 증가하더라도 시간이 증가하지 않습니다.

 

o(n)

---

for(int i = 0; i<10; i++){
	printf("%d\n". i);
}

O(n)은 선형 복잡도(linear complexity)이며, 입력값이 증가함에 따라 시간이 같은 비율로 증가합니다.

 

 

 O(logn)

---

int i = 0, j = n;
while(j>0){
	i+=j;
    j/=2;
}

O(log n)은 로그 복잡도(logarithmic complextify)라고 부르며, 알고리즘을 수행할 때마다 찾아야할 대상이 절반으로 줄게됩니다.

→  O(1) 다음으로 빠른 시간 복잡도를 갖습니다.

 

O(n²)

---

for(int i = 0; i<10; i++){
	for(int j = 0; j<10; j++){
    	printf("%d x %d = %d\m", i, j, i*j);
    }
}

O(n²)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가합니다.

 

O(2ⁿ)

---

int fib(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
 
    return fib(n - 1) + fib(n - 2);
}

O(2ⁿ)는 기하급수적 복잡도(exponential complexity)라고 부르며, 가장 느린 시간 복잡도를 가지고 있습니다.

 

 

◡̈