CSㅣ복잡도

휘Bin·2024년 1월 15일

복잡도

복잡도

복잡도는 '시간 복잡도'와 '공간 복잡도'로 나뉜다.

시간 복잡도

시간 복잡도

빅오 표기법

시간 복잡도는, '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 뜻한다. 어떤 알고리즘의 로직이 '얼마나 오랜 시간' 걸리는지 나타내는 데 쓰이고, 보통 '빅오 표기법'으로 나타낸다. 만약, '입력 크기 n'의 모든 입력에 대한 알고리즘에 필요한 시간이 10n제곱 + n이라고 하면 아래와 같은 코드가 짜여질 수 있다.

C++

for(int i=0; i<10; i++){
	for(int j=0; j<n;j++){
    	for(int k=0; k<n; k++){
        	if(true) cnt << k << '\n';
        }
    }
}
for(int i=0; i<n; i++){
	if(true) cnt << i << '\n';
}

'빅오 표기법'이란, 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것인데, 위 코드의 시간 복잡도를 빅오 표기법으로 나타내면 O(n제곱)이 된다.

즉, '가장 영향을 많이 끼치는'항의 상수 인자를 빼고 나머지 항을 없앤 것이다. 다른 항들은? 이라고 할 수 있지만, 증가 속도를 고려하면 그렇지 않다. 입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고, 다른 것은 이에 비해 미미하기 때문에 이것만 신경 쓰면 된다는 이론인 것이다.

시간 복잡도의 존재 이유

시간 복잡도는 왜 필요할까? 효율적인 코드로 개선하는데 쓰이는 척도가 되기 때문이다. 버튼을 누르고 화면이 나타나는 로직이 O(n제곱)의 시간 복잡도를 가지고 9초가 걸린다고 했을 때, O(n)의 시간 복잡도를 가지는 알고리즘으로 개선함녀 3초가 걸리게 되기 때문이다.

따라서, O(n제곱)보다는 O(n), O(n)보다는 O(1)의 알고리즘을 지향해야 한다.