1. 시간 복잡도

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 입력 크기에 따라 나타낸 것이다.

주로 최악의 경우에 대한 수행 시간을 분석하며, 알고리즘의 효율성을 평가하는 중요한 척도다.

1-1) 빅오 표기법

시간 복잡도란 “문제를 해결하는 데 걸리는 시간과 입력의 함수 관계”를 가리킨다.

어떠한 알고리즘 로직이 “얼마나 오랜 시간”이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다.

e.g. 입력크기 n의 모든 입력에 대한 알고리즘에 필요한 시간 10n² + n이라고 하면 다음과 같은 코드를 상상할 수 있다.

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

for (int i = 0; i < n; i++) {
		if (true) count << i << '\\\\n';
}

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

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

1-2) 시간 복잡도의 존재 이유

효율적인 코드로 개선하는 데 쓰이는 척도가 된다.

e.g. 버튼을 누르고 화면이 나타나는데 이 로직이 O(n²)의 시간 복잡도를 가지고 9초가 걸린다고 했을 때 이를 O(n)의 시간 복잡도를 가지는 알고리즘으로 개선한다면 3초가 걸리게 된다.

1-3) 시간 복잡도의 속도 비교