본문 바로가기

IT/ETC

Algorithm time complexity

반응형

There are three things to consider when choosing which code to use

1. Time complexity(Big o)

2. Space complexity(How much memory it would consume)

3. Code readability

 

면접날 빅오 대해서 질문을 받았는데 답변을 못해서 집에서 찾아보니 코드를 선택할 때 세가지 요소가 있다는걸 발견했다.

간단하게 첫번째인 빅오에대해서 설명을 적어보도록 하겠습니다

 

입출력 상관없이 똑같은 속도를 유지하는 것은 O(1), 파라미터, 값에 변화에 영향을 받지 않고 똑같은 속도(constant complexity)
O(n)는 증가하는 값에 따라 같이 변화하는 것, linear complexity ex. for loop
O(n^2)는 제일 오래 걸리는 속도, quadratic complexity ex·이중 포문


O(1) = 주방장이 손님 수 상관없이 대량으로 조리해주는 속도  

O(log n) = 주방장이 주문들어온 음식들을 한번에 같이 조리해서 주는 속도
O(n) = 주방장이 손님마다 하나의 음식을 조리해서 주는 속도
O(n^2) = 주방장이 각 손님이 한에 모든 요리를 하나씩 다 조리해 주는 속도

 

 

반응형

'IT > ETC' 카테고리의 다른 글

Garbage Collector  (0) 2019.12.01
Comparable vs Comparator  (0) 2019.12.01
자바 메모리 구조  (0) 2019.11.23
various query  (0) 2019.11.14
Various html  (0) 2019.11.14