자바로 구현하고 배우는 자료구조

들어가기 전에

빅 오 표기법을 활용하여 알고리즘의 효율성을 비교해봅시다.

학습 목표

빅 오 표기법을 올바르게 사용하여 알고리즘의 효율성을 비교할 수 있습니다.

핵심 단어

강의 듣기

빅 오 표기법 예시

아래의 식이 옳은지 판단해봅시다.

문제 1.

$n\textstyle ^4\textstyle ^/\textstyle ^3$ = O( $n l o g n$ )

힌트) 알고리즘에서는 n이 무한으로 커진 경우를 가정하고 비교한다는 규칙과 log 함수를 포함할 경우 밑은 무시한다는 규칙을 사용하여 풀 수 있습니다.

문제 2.

$3n^3+4n^2+5n+6$ = θ( $n^3)$

힌트) 낮은 차수의 항들은 무시한다는 규칙과 모든 상수를 삭제한다는 규칙을 사용하여 풀 수 있습니다.

문제 3.

$O(n^2)$

문제 4.

$2^n = w(n)$

문제 5.

$n^3 = O(n^2)$

문제 6.

$n^2 = O(n^3)$

풀이)

문제 1.

적당히 큰 수인 1000을 n에 대입하면, 좌변은 10000이고 우변은 log의 밑이 10일 때 O(3000)입니다. 그래프를 그리면 아래와 같고, 10000은 3000 이하가 아니기 때문에 이 식은 잘못되었습니다.

문제 2.

낮은 차수의 항들을 무시하면, $3n^3$ =θ( $n^3$ )입니다. 그리고 모든 상수를 삭제하면 $n^3$ =θ( $n^3$ ). 따라서, 이 식은 참입니다.

문제 3.

낮은 차수의 항들을 무시하면, $n^2/2$ =θ( $n^2$ )입니다. 그리고 모든 상수를 삭제하면 $n^2$ =θ( $n^2$ ). 따라서, 이 식은 참입니다.

문제 4.

적당히 큰 수인 1000을 n에 대입하면, 좌변은 2^1000이고 우변은 ω(1000)입니다. 그래프를 그리면 아래와 같고, 1000은 1000 이상이기 때문에 이 식은 참입니다.

문제 5, 6.

$n^2$ 은 $n^3$ 보다 느리게 증가합니다. 따라서, 문제 5는 거짓, 문제 6은 참입니다.

문제 1과 문제 3의 경우, 엄밀하게 풀기 위해서는 로피탈 규칙을 사용해야 합니다. 하지만 본 강의에서는 적당히 큰 수를 대입하는 방법으로도 풀 수 있는 문제들만 다룹니다.

생각해보기

1) 문제 1에서 n=1을 대입하면 어떻게 되나요? 적당히 큰 수를 대입해야 하는 이유는 무엇인가요?

1-4. 빅 오 표기법 예시