13. [11단계] 제목: 시간 복잡도 (3~7챕터)

시간 복잡도에 대한 개념은 다음 글을 참고하길 바람)

https://codingworld2002.tistory.com/100

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

---

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

답: n=int(input())
print(n*n)
print(2)

빅오 표기법에 의해 n의 제곱의 시간 복잡도를 가지고 있는 문제이다. 고로 n을 입력받고, n의 제곱을 출력한다.

차수는 2차이니 2도 출력해야 한다.

---

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

답: n = int(input())
print(int( n*(n-1) - (n-1)*n/2))
print(2)

3단계와 비슷하지만, for문이 -i + 1만큼 돌아가는 것이 다르다.

문제 예제 입력에 있는 7을 n이라고 했을 때,

i = 1 일 때 j는 2 ~ 7
i = 2일 때 j 는 3 ~ 7
...
i = 7 일 때 j 는 8이 되어 반복하지 않는다.

n을 n-1번 더한 수에서 첫째항이 1 ~ 마지막 항이 n - 1 등차수열의 합을 빼면 위와 같은 코드가 나오게 된다.

이후 차수가 2차이니 2를 출력해 준다.

---

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

답: n = int(input())
print(n**3)
print(3)

이번 문제는 3중 for문이다. 고로 n의 차수를 가지게 된다.

입력을 받고, 이후 n의 3 제곱을 출력한다.

차수는 3차이니 3도 출력해 준다.

---

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

답: n = int(input())
print((n*(n-1)*(n-2)) // 6)
print(3)

1부터 7까지의 정수를 중복되지 않게 조합, 즉 7C3을 구하면 되는 문제이다. 그리고 이 7C3은 공식이 존재한다.

공식은 

(이것도 5단계처럼 3중 for문)

---

7단계.
알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.
함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

f(n), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.

답: a1, a2 = map(int, input().split())
c = int(input())
n = int(input())
if ((a1*n + a2) <= (c*n) and (a1 <= c)):
    print(1)
else:
    print(0)

이 문제는 점근적 표기에 대하여 알고 있는지를 물어보는 문제이다.

일단, 먼저 입력을 받을 a1 ,  a0을 입력한다. 이후 c를 입력받고, n을 입력받는다.

빅오 표기법에서 n 함수 공식을 이용해서 크기를 비교하는 것이다. 

https://en.wikipedia.org/wiki/Big_O_notation

Big O notation - Wikipedia

이건 구글링 안하면 절대로 모른다. 즉, 특정 자료구조(알고리즘 공식)를 알아야 풀 수 있는 문제다.

결론

시간 복잡도는 특정 알고리즘에 대한 공식 및 공부가 있어야 풀 수 있음.