24313번
·
CS 이론/알고리즘
https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 이 문제는 점근적 표기법에 대한 문제이다. 시간복잡도의 빅오 함수를 정의하는 것인데, 처음에는 너무 쉽다 생각해서 바로 구현하여 돌렸는데, 91퍼에서 틀려서 뭐가 문제인가 생각하게 만든 문제이다. 이유는 생각보다 간단했다. 내가 생각한 로직은 g(n0)>=f(n0)이 성립하면 된다고 생각했다. 하지만 여기서 생각할 것은 f(n)=fn && a1