노트정리/자료구조
계산 복잡도 - 빅오 표기법(big O)
직접 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법으로 알고리즘의 복잡도 분석이 있다.이 방법에는 2가지 방법이 있는데 알고리즘의 수행시간을 분석하는 시간 복잡도 , 알고리즘이 사용하는 기억공간을 분석 하는공간 복잡도가 있다. 알고리즘 복잡도를 이야기할 떄는 대게 시간 복잡도를 뜻하며 시간 복잡도의 표시는 빅오 표기법(big-oh notation)으로 한다. 빅오 표기법(Big-Oh Notation) 1. 시간 복잡도 표기법시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시함.O(3n+2) = O(3n) = O(n)이 된다.2. 수학적 정의모든 N >= N0 에 대해서 f(N) n0인 모든 n에 대해 f(n) < c g (n)을 만족하는 2개의 양의 상수 c, n0 이 존재하면 ..