파이썬 알고리즘 수업 - 점근적 표기(백준 BOJ 24313)

문제

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.

이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.

함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

입력

다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)

다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

출력

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

예제 입력 1

7 7
8
1

예제 출력 1

0

f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다.

예제 입력 2

7 7
8
10

예제 출력 2

1

f(n) = 7n + 7, g(n) = n, c = 8, n0 = 10이다. 모든 n ≥ 10에 대하여 7n + 7 ≤ 8n 이므로 O(n) 정의를 만족한다.

📝풀어보기

📌 위의 원소나열법으로 제시된 조건을 풀어보자

1. O(g(n))은
2. 모든 n0보다 크거나 같은 n에 대해
3. f(n) 보다 크거나 같은 c*g(n)인 양의 상수 c와 n0가 존재한다.

에 대한 증명이다.

입력한 값을 예를들어보자.

a1, a0 = 7, 7

c = 8

n0 = 1

모든 n0보다 크거나 같은 n의 값은 1~100이 될것이다.

그렇다면 함수 f(n) = a1n + a0 보다 크거나 같은 c*(g(n))의 값을 비교하는식을 풀어보면

7*(1…100) + 7 <= 8(1…100) 이 나오고, 이 값은 참이 아니므로 0이 된다.

이 정의를 증명하려면 for 반복문에 n0 부터 100까지의 값을 돌아가면서 함수 f(n)과 c*(g(n))에 대입하여 비교하고 참이면 1, 거짓이면 0을 출력하면 된다.

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


def fn(a1, a0, c, n0):
    ans = 1
    for n in range(n0, 101):
        f = (a1*n) + a0
        cg = c*n

        if f > cg:
            ans = 0
            break

    return ans

print(fn(a1, a0, c, n0))


# 7 7
# 8
# 1
# fn = 7n + 7, g(n) = n, c = 8, n0 = 1
# f(1) = 14, c*g(1) = 8