[알고리즘] 효율성, 시간복잡도 (빅오표기법,Big O Notation)

안녕하세요, Jude 입니다.

 

오늘은 코드의 효율성에 대한 이야기를 해볼까 합니다.

 

효율성은 크게, 시간과 공간으로 구분 되는데요. 일반적으로 시간은 연산횟수, 공간은 메모리할당으로 이야기를 합니다.

(오늘은 시간복잡도에 대해서만 알아보겠습니다.)

 

이러한 연산횟수와, 메모리할당에 대해 평가하기위해서, 표기법을 지정했는데, 그것이 바로 빅오표기법(Big O Notation) 입니다.

 

시간복잡도에서의 Big-O 표기법의 가장 큰 특징은, 입력값에 따른 전체 알고리즘의 연산횟수를 점근적으로 접근하여, 최악의 경우를 지정한다는 것 입니다.

 

예제 코드를 통해 살펴볼까요?

예제 코드 1

의미가없는 라인은 제외하고, 실제 코드 동작부분만을 가지고 line 1 ~ 6 까지 번호를 메겨 두었습니다.

한줄씩 실행 과정을 살펴보겠습니다.

line 1 : 입력을 받기위해 Scanner 클래스의 인스턴스를 하나 생성하였습니다. 실행횟수는 1번입니다.
line 2 : a 에 값을 입력합니다. 실행횟수는 1 입니다.
line 3 : b 에 0 값을 대입합니다. 실행횟수는 1 입니다.
line 4,5 : line 5의 연산을 a번 만큼 실행합니다. (ex. a = 100, 100번실행) ( n * 1)
line 6 : b값을 콘솔창에 출력합니다. 

위 예제코드의 연산횟수를 방정식화 해보면 n(a) + 4 입니다. 이 n(a) 값이 무한대로 증가할 경우, 미적분학을 배우신분들은 n 으로 발산한다는 것을 이해하실 수 있을겁니다. 따라서 이 코드의 시간복잡도는 O(n)입니다. 사실 이 경우 최악의 경우만 따진다는 것이, 와 닿지 않으실텐데요, 다음코드 살펴보도록 하겠습니다.

예제 코드 2

2번 예제코드를 살펴보시면 line 3에 코드에서 5에 해당하는 값에 따라 연산횟수가 바뀔 것입니다. array 에 1 부터 10까지 오름차순으로 들어있음으로, 5일경우 는 5번 실행할것이고, 1이라면 1번, 10이라면 10번을 시행하게 되겠네요. 이처럼 입력값에 따라 나올수있는 경우의수중 가장 큰값이 이코드의 시간복잡도 입니다. 만약 배열이 1부터 매우큰 수 n 까지 오름차순으로 입력이 되어있고, 특정한 값을 찾는 경우, 가장 오래걸릴경우는 k = n 인 경우일것 입니다. 하지만 1을 찾는경우는 실행횟수가 1이겠죠? 하지만 빅오표기법으로는 최악의 경우만을 표기하기로 약속했으니, 위코드의 시간복잡도는 예제코드 1과 마찬가지로 O(n)이 됩니다.

 

알고리즘을 설명하기위해 간략하게만 적기위해서, O(n)의 경우대해서만 자세하게 알아봤는데요, 흔히 복잡도가 작은 순서대로 코드를 

O(1) < O(logN) < O(n) < O(N logN) < O(N^2) < O(2^N) < O(N!) 등으로 표기합니다.

 

본글은 알고리즘 코드리뷰에 이해를 돕기위해 간략하게 개념에대해서만 설명하고 있습니다.

댓글에 추가설명 필요하신 부분 있으시면 댓글 남겨주십시오.