[자료구조] - 1. 개요, 원시작업, Big-Oh 표기법

자료구조 개요, 원시작업, Big-Oh 표기법

 

 

• 용어 정리
  • 알고리즘(algorithm) : 주어진 문제를 유한한 시간 내에 해결하는 단계적 절차
  • 데이터구조(data structure) : 데이터를 조직하고 접근하는 체계적 방식
  • “좋은” 알고리즘과 데이터구조 : 작업에 소요되는 실행시간과 기억장소 사용량이 작다.

 

 자료구조를 공부하기에 앞서, ‘알고리즘’과 ‘자료구조(=데이터 구조)’라는 용어에 대해 먼저 정리해보았습니다. 우리의 목표는 “좋은” 알고리즘과 자료구조, 즉 작업에 소요되는 실행시간과 기억장소 사용량이 작은 알고리즘과 자료구조를 만드는 것입니다.

 

 좀 더 쉽게 설명을 해보자면, 자료구조는 말 그대로 “자료(data)를 담는 구조”를 말합니다. 자료(data)를 어떻게 저장하고, 꺼내올 것인지를 배우는 것이 바로 자료구조 공부라고 할 수 있습니다. 기초 코딩 공부에서 배우는 배열(array) 역시 자료구조의 예시입니다.

 예를 들어 int x[5] = {1,2,3,4,5}; 의 경우는 1,2,3,4,5 라는 자료(data)를 연속적인 메모리 공간에 순차적으로 저장한 자료구조입니다.

 

---

• 실행시간 : 입력의 크기와 함께 증가, 최악실행시간 (worst case running time)에 집중

 

• 실행시간 구하기
  • 실험적 방법 : 동일한 하드웨어, 소프트웨어 환경 필요, 완전한 구현 어려움
  • 이론적 방법 : 모든 입력 가능성 고려, 하드웨어나 소프트웨어에 무관한 평가 가능,  실행시간을 입력 크기 n의 함수로 규정, 의사코드 사용

 

 알고리즘의 실행시간은 입력된 데이터가 커질수록 함께 증가하게 됩니다. 일반적으로 알고리즘을 작성할때는 결과를 출력하는데 가장 오랜 시간이 걸리는 최악실행시간에 집중합니다.

 그렇다면 최악 실행시간은 어떻게 구할까요? 알고리즘을 실제로 작성하고 실행시켜서 시간을 재는 방법이 가장 편리하겠지만, 위와 같은 한계가 있기 때문에 잘 사용하지 않습니다. 따라서, 대안으로 이론적 방법을 사용합니다. 이론적 방법은 실험적 방법의 문제점을 극복한 방법으로, 주로 의사코드를 사용해 실행 시간을 입력크기 n의 함수로 나타냅니다.

 

---

• 의사코드(pseudo-code)
  • 알고리즘을 설명하기 위한 고급언어 ( 알고리즘을 설명하는데 선호되는 표기법 )
  • 컴퓨터가 아닌 인간에게 읽히기 위해 작성됨
  • 자연어 문장보다 더 구조적이지만, 프로그래밍 언어보다 덜 상세

 

 의사코드에는 정해진 문법이 없기 때문에, 사용하는 사람마다 문법이 다릅니다. 따라서 이 게시글에는 따로 의사코드의 문법을 정의하지 않고, 부득이하게 의사코드가 필요한 내용의 경우 C언어 코드로 작성해서 업로드 하겠습니다.

 의사코드에 대해서 더 자세히 알고 싶으시면 아래 링크를 확인해주세요.

https://ko.wikipedia.org/wiki/%EC%9D%98%EC%82%AC%EC%BD%94%EB%93%9C

 

---

• 임의접근기계 모델 ( Random Access Machine, RAM )
  • 이론적 방법에 대한 실행시간 측정에 사용되는 가상의 컴퓨터 모델
  • 하나의 CPU와 무제한의 메모리 셀로 구성, 메모리 셀은 임의 데이터를 저장
  • 어떤 메모리 셀에 접근하던지 모두 동일한 시간 (상수시간 단위) 소요된다고 가정

 

• 원시작업(primitive operation)
  • 알고리즘에 의해 수행되는 기본적인 계산들
  • 프로그래밍 언어와 대체로 무관, 정밀한 정의는 중요하지 X
  • RAM 모델에서 수행시 상수시간이 소요된다고 가정
  • 일반적으로 치환, 접근, 호출, 반환, 평가 등이 있음

 

• 원시작업 수 세기
  • 의사코드를 조사해서 원시작업의 최대 개수를 입력크기의 함수 형태로 결정할 수 있다.

 

 이론적 방법으로 실행시간을 측정하는 방법은 다음과 같습니다. 먼저 가상의 컴퓨터 모델 (RAM)을 가정하고, 그 모델에 대한 원시 작업을 찾습니다. 그런 다음, 코드를 조사해서 원시작업의 최대 개수(최악실행시간 가정)를 계산하는 방법으로 실행시간을 측정합니다. 이때, 원시작업의 최대 개수는 입력크기의 함수 형태로 결정할 수 있습니다. 

int arrayMax(int A[], int n) {				// 배열 A 최댓값 찾기

	int currentMax = A[0];				// 치환 1번, 접근 1번		→ 2
	for (int i = 1; i <= n - 1; i++) {		// 치환 1번, 접근 n번		→ n + 1
		if (A[i] > currentMax) {		// 접근 n-1번, 평가 n-1번	→ 2n - 2
			currentMax = A[i];		// 접근 n-1번, 치환 n-1번	→ 2n - 2		
			i = i + 1;			// 평가 n-1번, 치환 n-1번	→ 2n - 2	
		}
	}
	return currentMax;				// 반환 1번			→ 1
}							//			   총합 → 7n-2

 예를 들어보면, 위의 알고리즘 arrayMax는 최악의 경우 7n – 2개의 원시작업을 실행한다고 할 수 있습니다.

---

• Big-Oh 표기법
  • 함수의 증가율의 상한(upper bound)을 나타낸다
  • f(n) = O(g(n)) : f(n)의 증가율은 g(n)의 증가율을 넘지 않음

 

• Big-Oh 계산 요령
  • f(n)이 상수이면, f(n) = O(c), 또는 O(1)
  • f(n)이 차수 d의 다항식이면, f(n) = O(n^d), 즉
    • 1. 낮은 차수의 항들을 탈락시킨 후
    • 2. 상수계수를 탈락시킨다
  • 최소한의 함수계열을 사용 : 2n = O(n2) 대신 2n = O(n)
  • 해당 함수계열 중 가장 단순한 표현을 사용 : 3n + 5 = O(3n) 대신 3n + 5 = O(n)

 

• 점근분석(asymptotic analysis)
  • 점근분석 수행과정
    • 1. 최악의 원시작업 실행회수를 입력크기의 함수로 나타낸다.
    • 2. 이 함수를 big-Oh 표기법으로 나타낸다.
  • 예) 알고리즘 arrayMax
    • 1. 알고리즘 arrayMax는 최대 7n – 2개의 원시작업을 실행한다.
    • 2. “알고리즘 arrayMax는 O(n) 시간에 수행된다”

 

 그렇다면 실행시간은 어떻게 표기할까요? 앞서 계산한대로 ‘7n-2개의 원시작업' 으로 표기할 수도 있으나, 일반적으로 Big-Oh 표기법을 사용합니다. 예를 들어 f(n) = O(g(n))은 “f(n)의 증가율은 g(n)의 증가율을 넘지 않는다” 라는 것을 의미합니다. 앞서 계산한 알고리즘 arrayMax의 경우, f(n)=7n-2이므로, 알고리즘 arrayMax은 O(n)시간에 수행된다고 말할 수 있습니다.

 

---

• 점근분석 계산 방법
  • 하나의 식에 나타나는 여러 개의 원시작업은 하나로 계산
  • 예: a = a + (b + c) * (d – e) → O(c)
  • 반복문 → O(n) // 중첩 반복문 → O(n)
  • 연속문 : 각 문의 실행시간 중 가장 큰 것을 선택
  • 조건문 : 조건검사의 실행시간 중 가장 큰 것을 선택

 

 알고리즘의 실행시간을 구하기 위해서 하나하나 원시작업의 수를 세는 것은 매우 번거롭습니다. 점근분석을 이용하면 알고리즘의 실행시간을 Big-O 표기법으로 구할 수 있습니다.

for (i=0;i<=n-1;i++){			// {O(n)}	
	A[i]=0;
}
for (i=0; i<=n-1; i++){			// {O(n^2)}	
	for (j=0; j<=n-1; j++){		
    	A[i]=A[i]+A[j];
	}
}

  연속문의 예시입니다. 이 경우, 실행시간은 O(n^2) 입니다.

if (k==0) return 0;			// {O(c)}
else {					// {O(n)}	
	for (i=0; i<=n-1; i++){
		j++;
	}
}

  반복문의 예시입니다. 이 경우, 실행시간은 O(n) 입니다.

 

---

• Big-Oh의 친척들
  • Big-Oh (상한) : 점근적으로 f(n) ≤ g(n)이면, “f(n) = O(g(n))”
  • Big-Omega (하한) : 점근적으로 f(n) ≥ g(n)이면, “f(n) = Ω(g(n))”
  • Big-Theta (동일) : 점근적으로 f(n) = g(n)이면, “f(n) = Θ(g(n))”

 

 Big-Oh와 유사한 점근분석 표기법으로 Big-Omega, Big-Theta가 있습니다. Big-Oh가 함수의 증가율의 상한(upper bound)을 나타내는 반면, Big-Omega는 함수의 증가율의 하한(lower bound)을 나타냅니다. Big-Theta는 함수의 증가율의 상한과 하한을 모두 나타냅니다. 즉, f(n) = O(g(n)) = Ω(g(n)) 이면 f(n) = Θ(g(n))입니다.

 

---

 

* 이 게시글은 데이터구조 원리와 응용(국형준, 21세기사)을 읽고 개인 학습용으로 정리한 내용입니다.