클라우드 낚시꾼

시간 복잡도의 분류 위의 모토에 따르면, 시간 복잡도는 아래와 같이 3가지로 분류된다. 1. 최악 경우 시간 복잡도(worst case) 모든 입력에 대해서 기본 연산이 수행되는 최대 횟수 2. 최선 경우 시간 복잡도(best case) 모든 입력에 대해서 기본 연산이 수행되는 최소 횟수 3. 평균 경우 시간 복잡도(average case) 모든 입력에 대해서 기본 연산이 수행되는 평균 횟수 예제로 순차 탐색 알고리즘 각 시간 복잡도를 구해보자. 1. 최악 경우시간 복잡도(worst case) 모든 입력에 대해 가장 마지막에 탐색을 성공하는 N 2. 최선 경우 시간 복잡도(best case) 모든 입력에 대해 가장 첫 번째에 탐색을 성공하는 1 3. 평균 경우 시간 복잡도(average case) 평균 ..

대표적인 점근적 표기 대표적인 점근적 표기는 위와 같다. 사실, 말로는 이해하기 너무 어렵다. 점근적 표기에 대해서 더 알아보자. O(Big-O)-표기 (최악의 시간 복잡도) - O(Big-O) 표기의 정의 모든 n >= n0에 대해서 cg(n) >= f(n)인 양의 상수 n0와 c가 존재한다면, f(n) = O(g(n))이다. - O(Big-O) 표기의 의미 n0와 같거나 큰 모든 n에 대해서 f(n)은 cg(n)보다 크지 않다는 의미이다. 즉, f(n)은 cg(n)에 절대 미치지 못하며, 이때 g(n)을 f(n)의 상한이라고 한다. - f(n) = O(g(n))의 의미 n이 증가함에 따라 g(n)은 f(n)이 절대 미치지 못하는 점근적 상한이다. - Big-O 표기법을 찾는 방법 다항식에서 계수를 제..