.

그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork

# 알고리즘 평가 : 최악의 경우 몇번의 연산(비교)를 하는가?

알고리즘 평가 예시 ) 이 알고리즘은 최악의 경우라도 최소의 연산으로 연산을 완료하는 것을 보장한다.

==> 그래서 알고리즘 평가는 통상 최악의 경우를 기준으로 본다.

• 같은 기능을 하는 알고리즘이라도 성능이 얼마나 다를 수 있는지 그리고 그 성능 차이를 객관적으로 나타낼 수 있는 지표 그것을 big O라고 한다.

big O

• 데이터가 증가할 수록 연산의 수가 얼마나 증가하는 지를 나타내는 것

• 성능순을 나열하면 아래와 같다.

(좌측부터 성능이 좋은 것이다)

O(1) (상수시간) > O(log n) (로그시간) > O(n) (선형시간) > O(nlog n) > O(n의 2승) (지수증가)

1) 상수시간 : 말도 안되게 빠른 것이다. 데이터가 늘어나도 시간은 항상 정해져있는 것이다.

ex) 인덱싱 예를 들어 li[3] = 5

2) 로그시간 : 대표적인 예가 트리의 데이터의 삽입, 데이터의 탐색, 데이터의 삭제

3) 선형시간 : ex) linked-list의 탐색(단점인 특징이다)

4) O(nlog n) : ex) 퀵소트(정렬 알고리즘중에 제일 빠르다), merge sort(합병정렬)

5) 지수증가 : 버블소트 포함 단순 정렬. 성능이 매우 안좋은 것이다.

linear search

• 타겟을 리스트의 마지막 3을 찾는다고 하면 if문을 5번 수행하게 될 것이다.

• 데이터의 수가 N개 이면 최악의 경우 N번을 연산해야 한다.

• T(n) = N

binary search

• 리니어 서치와 동일한 기능을 하지만 성능은 훨씬 좋다.

• 데이터의 수가 N개 이면 최악의 경우 log 2의 N번을 연산해야 한다.

recursion

• 재귀 : 함수 정의를 할때 자기 자신의 호출 코드가 들어있다.

• 반드시 재귀의 탈출조건(base case)을 포함해야 한다.

Big-O 표기법은 보통 시간 복잡도 혹은 공간 복잡도를 나타내기 위해 주로 사용한다.

• O(n) = order of n이라고 부른다

• O(n)이 만약에 \(\ 2n^2+3n-n\) 이 나오면 n이나 상수들 다 버리고 \(\ O(n^2)\) 가 된다.

• 우리가 알고 싶은 것은 정확한 함수 비교 횟수가 아니라 데이터가 증가함에 따라서 연산 횟수의 증가율을 알고 싶은 것이다. 다시말해 증가추세를 알고 싶은것이다.

• 따라서 위의 O(n)을 보게 되면 자연스럽게 “그래 n의 제곱으로 증가하겠네”라고 생각하면 된다.

• 만약세 O(n) = 상수 일경우 그냥 빅오는 1이라고 생각하면 된다.

• ‘최선의 경우’와 ‘최악의 경우’

예를 들어서 이진탐색에서 최선의 경우(best case)는 한번에 찾는 경우인 것이다. 예를 들어서 li = [1,2,3,4,5,6,7,8,9,10] 일때 target이 5인 경우에는 한번에 타겟을 찾게 된다. 그런데 이진탐색 시 이렇게 한번에 찾는 경우는 드물다. 따라서 이렇게 최선의 경우를 성능평가의 기준으로 삼기에는 문제가 있다.

그래서 통상 빅오를 계산한다는 것은 계산하고자 하는 특정 알고리즘의 최악의 경우를 성능평가의 기준으로 하는 것이다.

• 언제 이 빅오를 사용하는가 => 시간복잡도는 곧 연산속도를 의미하는 것이기 때문에 이 연산속도를 계산하기 위해 쓴다.

• 공간복잡도는 참고로 메모리에 관한 얘기다.

[빅오 적용 예시]

예를들어서 이진탐색의 big-O를 계산해보자. 처음에 입력된 갯수를 N 이라하면 첫번째로 찾는 액션을 하면 N/2, 두번째 찾는 액션을 하면 그것의 반이 또 버려져서 1/2 * N/2가 되고, 세번째 찾는 액션을 하면 1/2 * 1/2 * N/2가 된다. 그런식으로 K번의 찾는 액션을 취하면 N * (1/2)의 k승개가 남게 된다. 이렇게 계속해서 탐색을 반복하다보면 탐색이 끝나는 시점에는 남은 자료가 1개가 남게 될것이다. 그러면 N * (1/2)의 k승 = 1이라고 표기할 수 있다. 그러면 이때 양변에 2의 k승을 곱해주면 2의 k승 = N 이 될 것이고 이를 양변에 2를 밑으로 하는 로그를 취해주면 K = log2의 N이 된다. 그래서 자료의 갯수 N개에 따른 시행횟수(K)는 log2의 N이다. 그래서 빅오로 표기하면 상수수분은 통상 무시하므로 O(logN)된다.

아래 그림은 이진탐색 시 최악의 조건에서 탐색과정 예시

시행횟수 = K = 3

입력된 데이터 개수 = 10

3(K) = log 2의 10

[빅오를 보고 의미를 파악하기]

1) O(1) = 상수시간

• 이런 경우에는 데이터의 수에 상관없이 상수시간이 걸린다.

• 데이터가 100만개여도 특정 상수시간이라는 엄청나게 빠른 속도이다.

• 예시) 배열의 인덱싱, 연결리스트의 삽입/삭제

• 참고로 그래서 삽입과 삭제가 빈번한 경우에는 연결리스트를 많이 쓴다.

2) O(log n) = 로그시간

• 예시) 이진탐색, 트리의 삽입/탐색/삭제(즉 트리의 연산, 이런 엄청나게 빠른 이유 때문에 트리를 많이 쓴다)

3) O(n) = 선형시간

• 예시) 배열의 삽입, 연결리스트의 탐색

4) O(nlogn) = 선형로그시간

• 선형시간보다 능력이 떨어진다.

• 예시) 퀵정렬 (정렬중에 가장 빠르고 현업에서 가장 많이 쓰이는 정렬법), 머지소트

5) \(\ O(n^2)\)

• 예시) 버블소트, 삽입정렬, 선택정렬

6) \(\ O(2^n)\) = 지수시간

• 최악의 방법으로 지양해야한다.

[정렬된 array과 linked list의 big-O 비교]

1) 삽입 시

• array = O(n)이다. 특정번째 자리에 자료를 넣어야 하기 때문에

• linked list = O(1). 특정자료를 특정자리에 넣고 링크만 바꿔주면 되기 때문에

2) 탐색 시

• array = O(1)

• linked list = O(n)이다. 왜냐하면 링크를 순회하면서 일일히 비교하며 찾아야 하기 때문에

3) 삭제 시

• array = O(n)이다. 공석이 생기면 n번만큼 공석을 매워야 하기 때문에

• linked list = O(1). 특정자료를 삭제하고 링크만 바꿔주면 되기 때문에