goddragonucan   1년 전

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

srand   1년 전

입력:

첫줄에 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

댓글을 작성하려면 로그인해야 합니다.