어떤 문제를 논리적 사고 과정을 통해 논리적인 비약이나 오류가 없는 정답을 도출해내는 것은 문제를 해결하고자 하는 사람에게 있어 최우선적인 목표임과 동시에 쉽지만은 않은 일입니다. 그런데 우리에게는 정답을 도출해내는 것 못지않게, 어쩌면 더 중요한 문제가 하나 더 있습니다.

얼마나 효율적으로 문제를 해결했는가?

잘 공감이 되지 않으시는 분들을 위해 예를 하나 들어드리겠습니다.

1. 1부터 5까지의 합을 구하시오.
2. 1부터 100까지의 합을 구하시오.
3. 1부터 2,147,483,648까지의 합을 구하시오.

1번은 보자마자 문제를 푸셨을 겁니다.
1부터 5까지 하나씩 더해나가기만 하면 되니까요.

2번은 어떤가요?
힘들고 번거롭더라도, 1번을 풀 때와 같은 방식으로 구할 수 있습니다.

그렇다면 3번은 1번 문제를 풀때와 같은 방식으로 풀 수 있을까요?
이론적으로는 가능합니다만, 현실적인 측면에서는 불가능하다고 해도 과언이 아닙니다.

1번을 풀 때 사용한 방식을 사용해 1부터 n까지의 합을 구하는 코드를 작성해봅시다.
여기서 n은 1 이상의 자연수이며 사용 언어는 파이썬입니다.

total = 0
n = int(input())
for i in range(1,n+1):
	total += i

이 방식의 경우 대입 연산 n+2회, 덧셈 연산 n회로 총 연산 횟수는 2n+2입니다.
n이 5일 경우 총 연산 횟수는 12, 100일 경우는 202, 2,147,483,648일 경우는 4,294,967,298가 되겠네요.
n이 증가할수록 연산 횟수도 늘어나는 것을 알 수 있습니다.

이번에는 등차수열의 개념을 도입해 새로운 코드를 작성해보겠습니다.
마찬가지로 n은 1 이상의 자연수이며 사용 언어는 파이썬입니다.

n = int(input())
total = n * (n+1) / 2

이 방식의 경우 대입 연산 2회, 곱셈 연산 1회, 나눗셈 연산 1회로 총 연산 횟수는 4입니다.
이 경우에는 n의 값에 관계없이 항상 연산 횟수가 4로 고정되네요.

놀라운건 이는 한 가지 예시에 불과하며, 이보다 더 기하급수적으로 연산 횟수가 늘어나는 예시도 존재한다는 것인데요. 이 정도면 효율적인 알고리즘의 필요성에 대해서 충분히 인식했다고 생각하고 본론으로 넘어가도록 하겠습니다.

---

알고리즘의 복잡도를 표현하는 방법에 대해서 알아봅시다.
$n$이 무한대로 커질 때의 알고리즘(함수)의 실행 시간의 추이를 표현하는 표기법인 점근적 표기법을 이용해 $lim_{n \to \infty}T(n)$의 형태로 복잡도를 표현할 것입니다.
여기서 $n$은 입력값을 의미하며, $T(n)$은 알고리즘(함수)의 총 실행 시간을 의미합니다.

점근적 표기법은 빅오 표기법, 빅오메가 표기법, 빅세타 표기법이 존재합니다.

• 빅오 표기법(Big-oh notation): 최악인 경우의 알고리즘 수행 시간을 나타냄.
  $n$이 충분히 클 때 차수가 가장 큰 항이 가장 큰 영향을 미치고 다른 항들은 상대적으로 무시할 수 있을 정도로 작다는 사실을 이용함. $T(n)$의 최고차항 차수가 $k$일 경우 $T(n)$의 복잡도를 빅오 표기법으로 표기하면 $O(n^k)$.

• 빅오메가 표기법(Big-omega notation): 최소한의 수행시간을 나타냄.
  빅오 표기법과 반대되는 개념. $T(n)$의 복잡도가 빅세타 표기법으로 표기했을 때 $\Omega(n^k)$일 경우 $T(n)$은 아무리 빨라도 $n^k$이상의 복잡도를 가진다는 것을 의미함.

• 빅세타 표기법(Big-theta notation): 빅오와 빅오메가를 동시에 만족시키는 증가함수. $T(n)=O(f(n))$이면서 $T(n) = \Omega(f(n))$이면 $T(n) = \theta(n)$.

시간 복잡도의 크기는 $O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<\cdot\cdot\cdot<O(2^n)<O(3^n)<\cdot\cdot\cdot<O(n!)$ 순입니다.
알고리즘(함수)의 시간 복잡도가 $O(n^2)$을 초과하는 경우, 우리는 더 나은 알고리즘을 모색해야 합니다.

빅오 표기법 외의 표기법은 통상적으로 거의 사용되지 않으므로 아래 연습 문제에서는 빅오 표기법만 다룹니다.

연습 문제
다음을 시간 복잡도 함수인 빅오 표기법으로 표기
1) $T(n) = n^2 + n + 1$
2) $T(n) = n^3 + 10000n^2 + 50n$
3) $T(n) = n^2log_2n + n^3 + 3$
4) $T(n) = 7(2^n) + 3^n$
5) $T(n) = 3^n + n!$

정답
1) $O(n^2)$ 2) $O(n^3)$ 3) $O(n^3)$ 4) $O(3^n)$ 5) $O(n!)$

다음 알고리즘의 시간 복잡도를 빅오 표기법으로 표기
1)

multi = 1
for i <- 1 to n do:
	for j<- i+1 to n step 2 do:
    	multi = multi*j

2)

sum_one = 0
while n > 1:
	n = n // 2
    sum_one = sun_one + 1

정답
1) $O(n^2)$ 2) $O(logn)$