12. [11단계] 제목: 시간 복잡도 (1~2챕터)

챕터를 풀기 전에, "시간 복잡도"에 대한 공부가 필요하다. 그래서 시간 복잡도가 무엇인지 먼저 이야기하고자 한다.

시간 복잡도는 무엇인가?

시간 복잡도란 "입력 크기에 대해 어떤 알고리즘이 실행되는 데 걸리는 시간"을 뜻한다.

https://youtu.be/08TB5ZLTPu4?si=R55Fl49-sMovqdlm

관련 영상

또한 시간 복잡도에서 "빅오 표기법"이라는 것이 존재한다.

빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다.

이런 시간 복잡도가 필요한 이유는 간단하다. 바로 효율적인 코드를 개선하기 위한 척도가 되어주기 때문이다.

다음은 시간 복잡도의 속도를 비교한 그래프이다. 그래프의 그림처럼 n의 크기가 커질수록 시간 복잡도는 더욱 커지게 된다. 그래서 우리는 O(n**2)보다는 O(n), O(n)보다는 O(1)을 지향해야 한다.

자료구조를 나중에 쓸 때, 시간 복잡도를 생각하면서 짜야하기에, 필수적으로 알아야 하는 지식이다.

따라서 시간 복잡도의 값이 작을수록 좋다고 말할 수 있다.

이를 기반으로 문제를 풀어보자.

---

1단계.
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.
MenOfPassion(A[], n) { i = ⌊n / 2⌋; return A[i]; # 코드1 }

답: print(1)
print(0)

답이 굉장히 심플하게 나온 거 같지만, 이는 시간 복잡도에 관한 이야기이기도 하다.

이 문제의 시간제한은 1초이다. 이 제 한 시간 안에 알고리즘을 돌려야 한다.

MenOfPassion 알고리즘에서는 횟수를 출력하는 함수이다. 반복문도 없고 인덱스만 반환해서 초반 입력은 무조건 1을 반환해야 한다. 이후 빅오 표기법에서 O(1)는 상수항이다. (따로 함수가 아니라 값이 1로 일정함.) 상수항에서 차수는 0이라고 해석이 가능하다.

고로 0을 반환하면 된다. 그래서 코드의 답이 위와 같이 나오는 것이다.

---

2단계.
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.
MenOfPassion(A[], n) { sum <- 0; for i <- 1 to n sum <- sum + A[i]; # 코드1 return sum; }

답: n = int(input())
print(n)
print(1)

입력 값이 커질 때마다 시행 횟수가 늘어나는 것을 선형 복잡도라고 말한다.

그림에서 보이는 O(n)이라고 해석하면 편하다. 입력은 그냥 n을 받아주면 되고 반환은 n을 반환해 주면 된다.

그리고 함수는 1차식이다. 즉 차수는 1이기에 1을 반환하면 된다. 

---

결론

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

좀 더 디테일한 부분에 대한 글이다.

참고하자.