Big-O 표기밥

04 Dec 2018

Reading time ~2 minutes

알고리즘은 무엇인가

알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미

예를 들어 할머니가 케이크를 만드는 과정을 알고리즘으로 표현하면,

function BakeCake(flavor,icing) {
// 1.Heat Oven to 350 F
// 2. Mix flour, baking powder, salt
// 3. Beat butter and sugar until fluffy
// 4. Add eggs.
// 5. Mix in flour, baking powder, salt
// 6. Add milk and " + flavor + "
// 7. Mix further
// 8. Pur in pan
// 9. Bake for 30 minutes
// 10. " + if(icing === true) return 'add icing'
// 11. Stuff your face
}
BakeCake('vanilla', true) => deliciousness

시간복잡도를 분석하는 것은 input n에 대하여 알고리즘이 문제를 해결하는데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것과 같다. 이는 Big-O 표기를 이용하여 정의할 수 있다.

Big-O

Regular     Big-O
2           O(1)    --> It's just a constamt number
2n + 10     O(n)    --> n has the largest effect
5n^2        O(n^2)  --> n^2 has the largest effect

시간복잡도에서 중요한 것은 정해진 표현식에 가장 큰 영향을 미치는 n의 단위이다.

O(1) - 상수 시간: 입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.
O(log n) - 로그 시간: 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
O(n) - 직선적 시간: 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1관계를 가진다.
O(n^2) - 2차 시간: 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
O(C^n) - 지수 시간: 문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n제곱

시간복잡도 적용해보자면,

const friends = {
  'Mark': true,
  'Carl' : false,
  'Ray' :  true,
  'Laura' : false,
}
const sortedAges = [22, 24, 27, 29, 31]
}
// O(1) - constant time(상수 시간)
// If I know the persons name, I only have to take one step to check
function isFriend(name) { //similar to knowing the index in an Array
  return friends[name];
}
isFriend('Mark') // returns True and only took on step
function add(num1,num2) {
// I have two numbers, takes one step to return the value
  return num1 + num2;
} 
// O(LOG N) - logarithmic time(로그 시간)
// You decrease the amount of work you have to do with each step
function thisOld(num,array) {
  const midPoint = Math.floor(array.length /2)
  if(array[midPoint] === num) return true;
  if(array[midPoint] only look at second half of the array)
  if(array[midPoint] > num) --> only look at first half of the array
  // recursively repeat until you arrive at your solution
}
thisOld(29, sortedAges) //returns true