시간복잡도 관련질문요.
심플포텐
2023.04.01
§ Big-Oh(O) 표현§Big-Oh 표현의 예§큰 값 n에 대하여 g(n) 함수의 값은 항상 f(n) 함수 값 보다 같거나 큰 상한 값 함수임§f(n) 함수는 g(n) 함수 보다 더 작게 증가함(1) f(n) = 3n +2 : f(n) = O(n) (a=4, b=2)
(2) f(n) = 1000n2 + 100n + 6 : f(n)=O(n2) (a=1001, b=4)
(3) f(n) = 6*2n + n2 : f(n) = O(2n) (a=7, b=4)
(4) f(n) = 100 : f(n) = O(1) (a=100, b=1)
이것들은 뭘 나타내고 있는건가요? 책을봐도 이해를 못하겠습니다..
-
먹딸기
n이 자료수입니다
왼쪽 식은 어떤 처리의 예시문이고 오른쪽은 걸리는 시간을 축약했다고 해야하나.. 일반화를 했다고 해야하나..
아 일단 내용은..
첫번째는 선형
두번째는 제곱..(이름 모르는..)
세번째는 모르겠고..(단순히 2배는 아닌것 같네요.. 왼쪽식을 보면..)
네번째는 고정이네요.. -
비
오오오오오 동지여..ㅠ
저 대신 글을 올려주신 것 같아 감사합니다 ^^;;;