입력:
첫줄에 f(n)을 나타내는 정수 a1, a0 ( 0 <= |ai| <= 100 )
f(n) = a1 * n + a0
다음줄에 양의 정수 c
다음줄에 양의 정수 n0
문제 : 모든 n >= n0 에 대해서 O(n) 을 만족하는가?
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
O(n) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × n 인 양의 상수 c와 n0가 존재한다}
a1 * n + a0 <= c * n
ex>
a1 = 7, a0 = 7
c = 8
n0 = 1
=>
7 * n + 7 <= 8 * n ( for all n >= 1)
7 <= n ( for all n >= 1 )
=> n = 1, 2, 3, 4, 5, 6 일 때 만족하지 않습니다.
=> 답 0
ex>
a1 = 7, a0 = 7
c = 8
n0 = 10
=>
7 * n + 7 <= 8 * n ( for all n >= 10 )
7 <= n ( for all n >= 10 )
=> 항상 성립 합니다.
=> 답 1
ex>
a1 = 67 a0 = -90
c = 51
n0 = 2
67 * n - 90 <= 51 * n ( for all n >= 2 )
16 * n <= 90 ( for all n >= 2 )
=> 2 <= n <= 5 일때는 성립하나,
6 <= n 일때는 성립하지 않습니다.
=> 답 0

goddragonucan 1년 전
시간복잡도가 뭔지는 이해는 했는데 문제가 바라는게 뭔지 도저히 모르겠습니다