알고리즘, 시간 복잡도, Big-O 표기

 

- Big-O

: 대학교 수업 때, 이걸 왜 배우나 했었는데 돌이켜 생각해보면 작업 효율에 있어서 필수적인 개념이다.

	※ 7개의 값을 지닌 리스트가 있다고 가정
O(1)	리스트에 대한 어떠한 알고리즘을 수행하는데 있어서 딱 한 번의 작업으로 끝
O(log n)	로그
O(n)	예시로, 7개의 값을 다 한 번씩 훑어야 하는 iterator(start to end)
O(n log n)	선형 로그
O(n**2)
O(n**3)
O(2**n)	n개의 데이터에 대해 어떤 알고리즘 수행 시 총 사용된 작업 횟수가 2**n
	위에서 아래로 갈수록 효율이 나쁘고 작업시간이 오래걸리므로 이에 대한 개선은 필수적인 프로그래머의 고민거리라고 할 수 있다.

 

joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/

(번역) 알고리즘 쉽게 이해하기 : 시간 복잡도와 Big-O 표기