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

import sys


def main():
    input = sys.stdin.readline

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

    if a1 * n0 + a0 <= c * n0 and a1 <= c:
        print(1)
    else:
        print(0)


main()

아래는 $O(g(n))$ 집합의 조건을 다시 적은 것입니다.

모든 $n \ge n_0$에 대하여 $f(n) \le c g(n)$인 양의 상수 $c$와 $n_0$가 존재한다.

문제에서 $f(n) = a_1 n + a_0$이 주어졌고, $O(n)$의 정의를 만족하는지 알아보자고 하였으므로 $g(n) = n$입니다. 또한, $c$와 $n_0$의 값이 고정되므로 뒤의 "...존재한다"를 "...이다"로 바꾸면 됩니다.

모든 $n \ge n_0$에 대하여 $a_1 n + a_0 \le c n$이다.

$a_1 n + a_0$와 $cn$은 그래프상에서 두 직선으로 표현됩니다. 위 문장이 참이려면

• $n = n_0$을 대입했을 때의 부등식인 $a_1 n_0 + a_0 \le c n_0$가 참이어야 합니다.
• 두 직선의 기울기가 $a_1 \le c$를 만족해야 합니다.

정답 코드는 이 두 조건을 검사하고 있습니다.