Algorithm Analysis (+자료구조를 배워야 하는 이유)

1. 자료구조, 왜 배워야 할까?

 자료구조(Data Structures)란 단순히 데이터를 욱여넣는 것이 아니라, 목적에 맞게 '효율적으로' 저장하는 방법을 의미한다.

좋은 자료구조란 데이터가 늘어날 때 다양한 연산을 얼마나 빠르게(효율적으로) 수행하는지로 결정된다. 여기서 말하는 연산은 다음과 같다.

• 원하는 데이터를 찾는 것(Finding stuff)
• 새로운 데이터를 추가하는 것(Adding stuff)
• 기존 데이터를 삭제하는 것(Deleting stuff)

똑같은 결과를 내는 프로그램이라도 어떤 자료구조와 알고리즘을 쓰느냐에 따라 135ms 만에 끝날 수도, 3일이 걸릴 수도 있다.

그렇다면 이 속도, 즉 효율성은 어떻게 측정해야 할까?

 

 

2. 알고리즘의 속도 측정: 실험적 분석 vs 이론적 분석

1) 실험적 분석(Experimental Studies)과 그 한계

 가장 직관적인 방법은 코드를 직접 구현해서 time() 함수 등을 이용해 실제 걸린 시간을 재보는 것이다. 하지만 이 방법에는 한계가 존재한다.

• 하드웨어나 소프트웨어 환경에 따라 속도가 매번 다르게 측정된다.
• n이 100억, 1000억일 때 등 모든 입력 크기 n에 대해 일일이 테스트해 볼 수 없다.
• 성능을 테스트하려면 무조건 코드를 끝까지 다 구현해야만 한다.

 

2) 이론적 분석(Theoretical Analysis)과 원시 연산

 실제 걸린 시간을 재는 대신, 코드를 눈으로 보며 원시 연산(Primitive Operations)의 개수를 센다. 원시 연산이란 프로그래밍 언어와 무관하게 수행되는 가장 기본적인 계산을 말한다.

• 변수에 값 할당하기 ex) biggest = 10
• 객체 참조 따라가기 ex) student.name
• 산술 연산 한 번 하기 ex) 1+1
• 두 숫자 비교하기 ex) val > biggest, i == 0
• 인덱스로 배열 원소 접근하기 ex) data[0]
• 메서드 호출하기 ex) len(data), print(val)
• 메서드에서 반환하기 ex) return biggest

이 연산들이 총 몇 번 실행되는지 n에 대한 수식으로 표현하는 것이 바로 이론적 분석이다.

 

* Best case와 Worst case를 나누는 이유

알고리즘에서 최악/최선은 입력 데이터의 상태(분포)때문에 발생한다. 예를 들어 최댓값을 찾는 함수에서, 맨 앞에 최댓값이 있다면 연산을 적게 하니 Best case가 되고, 오름차순으로 정렬되어 있어 매번 최댓값을 갱신해야 한다면 Worst case가 된다. 자료구조에서는 어떤 악조건의 데이터가 들어와도 프로그램이 버틸 수 있도록 보통 Worst case를 기준으로 분석한다.

 

 

3. 점근적 표기법(Big-Oh, Big-Omega, Big-Theta)

1) Big-Oh: 상한선 '아무리 느려도 얘보다는 같거나 빠르다.'

• 정의: n ≥ n_0인 모든 n에 대해 f(n) ≤ c · g(n)을 만족하는 상수 c > 0와 n_0 ≥ 1가 존재하면, f(n)은 O(g(n))이다.
• 빅오 규칙(Big-Oh Rules):

• f(n)이 d차 함수일 경우 빅오는 O(n^d)이다.
• 가능한 가장 작은 단계의 함수를 사용한다. ex) 2n = O(n) instead of 2n = O(n^2)
• 가능한 가장 간단한 표현을 사용한다. ex) 3n + 5 = O(n) instead of 3n + 5 = O(3n)

 

2) Big-Omega: 하한선 '아무리 빨라도 얘보다는 같거나 느리다.'

• 정의 n ≥ n_0인 모든 n에 대해 f(n) ≥ c · g(n)을 만족하는 상수 c > 0와 n_0 ≥ 1가 존재하면, f(n)은 Ω(g(n))이다.

 

3) Big-Theta:

• c' · g(n) ≤ f(n) ≤ c'' · g(n)처럼 상한선과 하한선이 같은 함수 g(n)으로 샌드위치처럼 꽉 막힌 상태를 의미한다.

 

자료구조에서는 보통 최악의 경우를 대비해야 하므로 Big-Oh(O)를 가장 많이 사용하게 될 것이다.