시간 복잡도 N^2

개념

• 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며, 주요로직의 반복횟수를 중점으로 측정된다.

---

시간복잡도를 시간을 기준으로 계산을 하면 안되는 이유

• 컴퓨터의 컨디션에 따라 시간이 달라지기때문에 위의 코드처럼 시간복잡도를 시간으로 설명하는 것이 아닌,
• 어떠한 알고리즘이 주어진 입력크기를 기반으로 어떠한 로직이 몇번 반복되었는가를 중점으로 설명을 한다.

for (int i = 0; i < 10; i++){ // 10번
	for(int j = 0; j < n; j++){ // n번
		for(int k = 0; k < n; k++){ // n번
			if(true) cout << i << '\n'; // 단순 로직
		}
	}
}
// 10 n ^ 2

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

// -> 시간복잡도 10 n ^ 2 + n 

---

Big-O 표기법

10 n ^ 2 + n → O(n^2)

---

1. 가장 큰 영향력을 가진 항(Term)만 남기기

입력값 n이 무한히 커진다고 가정해 보자.

• n=1,000일 때: 10n2은 1,000만, n은 1,000이다.
• n=1,000,000일 때: 10n2은 10조, n은 100만이다.

n이 커질수록 뒤에 붙은 +n은 전체 값에 거의 영향을 주지 못하는 아주 미미한 존재가 된다. 그래서 가장 높은 차수인 10n2만 남기고 나머지는 버린다.

10n2+n→10n2

---

2. 상수 계수(Coefficient) 제거하기

빅오 표기법은 “정확한 연산 횟수”가 아니라 “데이터 증가에 따른 처리 시간의 증가율(기울기)”을 보는 것이다. n2 앞에 붙은 10은 그래프의 기울기를 가파르게 할 뿐, n의 제곱에 비례해서 늘어난다는 성격(차원) 자체를 바꾸지는 못한다. 따라서 상수는 무시한다.

10n2→n2

---

3. 최종 표기

위의 과정을 거쳐 최종적으로 다음과 같이 표기한다.

O(n2)

\[O(n^2)\]

• 데이터가 10배 늘면 시간은 100배 늘어남