[구현/수학] 백준 24313 알고리즘 수업 - 점근적 표기 1 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

2. 문제 풀이

 빅오표기법 O(n)의 증명 문제입니다.

 시간복잡도를 계산하는 방법에는 빅 오메가(최적), 빅 세타(평균) 표기법도 있지만 압도적으로 빅 오(최대) 표기법을 많이 사용합니다. 가장 구하기 쉽기도 하고, SW설계에서 최악의 상황을 많이 가정하기 때문입니다.

 (최악의 상황에서 정상적으로 작동하느냐가 중요하죠.)

 

 

 

3. 코드

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

# f(n) = a1*n + a0, g(n) = n
# 판별식 f(n) ≤ c × g(n)
# a1*n + a0 <= c*n
# (a1-c)*n0 + a0 <= 0
if a1*n0 + a0 <= c*n0 and a1-c<=0:
    print(1)
else:
    print(0)

 문제에서 제시한 판별식으로 구별하되, a1-c <= 0 조건도 추가해줘야 합니다.

 (a1-c)*n0 + a0 <= 0 에서 기울기가 양수일 경우에는 무조건 성립하지 않기 때문입니다.