빅 오 표기법 예시

들어가기 전에

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

 

학습 목표

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

 

핵심 단어

• 알고리즘 비교
• 빅 오 표기법

 

빅 오 표기법 예시

 

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

 

문제 1. 

 n\textstyle ^4\textstyle ^/\textstyle ^3n​4​​​/​​​3​​  = O( nlognnlogn )

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

 

문제 2. 

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

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

 

문제 3.

 n(n-1)/2 = O(n^2)n(n−1)/2=O(n​2​​) 

 

문제 4.

 2^n = w(n)2​n​​=w(n)  

 

문제 5.

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

 

문제 6.

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

---

 

풀이)

 

문제 1.

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

 

 

문제 2.

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

 

문제 3.

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

 

문제 4.

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

 

 

문제 5, 6.

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

 

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

 

---

 

생각해보기

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

 

나의 생각 : 1처럼 작은 숫자를 대입하면 실제 시간복잡도와 동떨어진 결과가 나올 수 있다.

 

출처  : https://www.boostcourse.org/cs204/lecture/480419?isDesc=false 네이버커넥트재단