[BAEKJOON] 11단계_시간 복잡도

julia319 정보

 

24262번 알고리즘 수업 - 알고리즘의 수행 시간 1

계산을 한 번만 한다. 또한 언제해도 1번이므로 다항식으로 표현하는 경우 O(n) = c 이므로 다항식 최고 차항 차수는 0이다.

# MenOfPassion(A[], n) {
#     i = ⌊n / 2⌋;
#     return A[i]; # 코드1
# }


N = int(input())

# 수행횟수
cnt = 1
# 수행횟수 다항식 표현 최고차항 차수
ans = 0

print(cnt)
print(ans)

 

24263번 알고리즘 수업 - 알고리즘의 수행 시간 2

for문을 1부터 n까지 수행하므로, 계산을 n번 한다. 다항식으로 표현하는 경우 O(n) = n 이므로 다항식 최고 차항 차수는 1이다.

# MenOfPassion(A[], n) {
#     sum <- 0;
#     for i <- 1 to n
#         sum <- sum + A[i]; # 코드1
#     return sum;
# }


N = int(input())

# 수행횟수
cnt = N
# 수행횟수 다항식 표현 최고차항 차수
ans = 1

print(cnt)
print(ans)

 

24264번 알고리즘 수업 - 알고리즘의 수행 시간 3

for문을 1부터 n까지 두 번 수행하므로, 계산을 n * n 번 한다. 다항식으로 표현하는 경우 O(n) = n^2 이므로 다항식 최고 차항 차수는 2이다.

# 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())

# 수행횟수
cnt = N ** 2
# 수행횟수 다항식 표현 최고차항 차수
ans = 2

print(cnt)
print(ans)

 

 

24265번 알고리즘 수업 - 알고리즘의 수행 시간 4

for문을 두 번 수행하는데, i의 for문에서 i가 하나씩 늘 때마다 j의 for문에서는 각 n-1번, n-2번, ... , 1번 수행하므로, 계산을 1부터 n-1을 다 더한 횟수만큼 한다. 다항식으로 표현하는 경우 O(n) = n(n-1) / 2 이므로 다항식 최고 차항 차수는 2이다.

# 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;
# }

# i: 1, j: 2~n 수행, i: 2, j: 3~n 수행 ... i: n-1, j: n~n 수행
# 총 시행 횟수: 1 + 2 + ... + n-2 + n-1
# 1~n-1까지 더하는 공식, n(n-1) / 2

N = int(input())

# 수행횟수
cnt = int(N*(N-1) / 2)
# 수행횟수 다항식 표현 최고차항 차수
ans = 2

print(cnt)
print(ans)

 

24266번 알고리즘 수업 - 알고리즘의 수행 시간 5

for문을 1부터 n까지 세 번 수행하므로, 계산을 n * n * n 번 한다. 다항식으로 표현하는 경우 O(n) = n^3 이므로 다항식 최고 차항 차수는 3이다.

# 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())

# 수행횟수
cnt = N ** 3
# 수행횟수 다항식 표현 최고차항 차수
ans = 3

print(cnt)
print(ans)

 

24267번 알고리즘 수업 - 알고리즘의 수행 시간 6

for문을 두 번 수행하는데, i의 for문에서 i가 하나씩 늘 때마다 j의 for문에서는 각 n-2번, n-3번, ... , 1번 수행하고, j의 for문에서 j가 하나씩 늘 때마다 k의 for문에서는 각 n-2번, n-3번, ... , 1번 수행한다.
따라서 sigma합 공식을 이용하여 계산하는 것이 훨씬 간단하다.
다항식으로 표현하는 경우 O(n) = n(n-1)(n-2) / 6 이므로 다항식 최고 차항 차수는 3이다.

# 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;
# }

# i: 1, j: 2 ~ n-1, n-2번 수행, i: 2, j: 3 ~ n-1, n-3번 수행 ... i: n-2, j: 1번 수행
# i의 총 시행 횟수 n-2번 일 때 j의 총 시행 횟수: n-2 + n-3 + ... + 2 + 1번

# j: 2, k: 3 ~ n, n-2번 수행, j: 3, j: 4 ~ n, n-3번 수행 ... j: n-1, k: 1번 수행
# j의 총 시행 횟수: n-2번일 때 k의 총 시행 횟수: n-2 + n-3 + ... + 2 + 1번

# sigma합 이용하여 풀면 훨씬 쉬운 문제
# n-2      n-1       n
# sigma   sigma    sigma   1 을 풀이한다.
# i = 1  j = i+1  k = j+1

# n-2      n-1
# sigma   sigma   {n - (j+1 - 1)} * 1
# i = 1  j = i+1

# n-2      n-1
# sigma   sigma   n-j
# i = 1  j = i+1

# n-2
# sigma  [{(n-1) - (i+1 - 1)} * n] - [n*(n-1) / 2 - i*(i+1) / 2]
# i = 1

# n-2
# sigma  {n(n -1 -i)} - {(n^2 - n - i^2 -i )/ 2}
# i = 1

# n-2
# sigma  (n^2 -n +i^2 -(2n-1)i) / 2
# i = 1

# [{(n-2) * (n^2-n)} + {(n-2)*(n-1)*(2*n-3)} / 6 - (2n-1) * (n-2)(n-1)/2] /2

# (n-2)*(n-1)*n/6

N = int(input())

# 수행횟수
cnt = int(N*(N - 1)*(N - 2) / 6)
# 수행횟수 다항식 표현 최고차항 차수
ans = 3

print(cnt)
print(ans)

 

24313번 알고리즘 수업 - 점근적 표기 1

f(n)과 c x g(n) 사이의 관계를 그래프로 그리면서 상황을 나누었다.

1. 기울기가 다르다면
   1. f(n)이 c x g(n)보다 클 때
   2. f(n)보다 c x g(n)이 클 때
      1. f(n)과 c x g(n)의 교점보다 기준점 n0가 더 크거나 같을 때
      2. f(n)과 c x g(n)의 교점보다 기준점 n0가 더 작을 때
2. 기울기가 같다면
   1. f(n)의 y절편인 a0가 0보다 작거나 같다
   2. f(n)의 y절편인 a0가 0보다 크다

# O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
# f(n) = a1 × n + a0
# g(n) = n

a1, a0 = map(int, input().split())
c = int(input())
n0 = int(input())

# f(n)과 c × g(n)의 기울기가 다르다면
if a1 != c:
    
    # 만약 f(n)의 기울기가 c × g(n)의 기울기보다 크다면 1보다 큰 n0에서는 항상 f(n)이 크다
    if c < a1:
        ans = 0
    else:
        # f(n) = c × g(n) 인 n을 구해
        n = a0 / (c - a1)
        # n0가 그 이상이라면 True
        if n <= n0:
            ans = 1
        else:
            ans = 0
# f(n)과 c × g(n)의 기울기가 같다면
else:
    # f(n)의 y절편인 a0가 0보다 작거나 0이어야 f(n) ≤ c × g(n)
    if a0 <= 0:
        ans = 1
    else:
        ans = 0
    
print(ans)