✏️ 추상 자료형과 시간복잡도

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

📌 추상 자료형(Abstract Data Type)이란?

기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열하는 것을 추상 자료형이라고 한다.

예를 들면, 제품의 사용 설명서와 같다. 선풍기의 사용 설명서를 생각해보자.

선풍기의 사용 설명서에는 정지, 실행, 회전, 미풍, 약풍, 강풍 버튼의 기능 설명과 사용 방법이 나와있다.
하지만 버튼을 눌렀을 때 선풍기 내부 회로에서 어떤 일이 발생하는지에 대해서는 전혀 나와있지 않다.

있어도 안본다.

추상 자료형은 선풍기의 사용 설명서와 같다. 그저 기능이 무엇인지, 사용 방법은 무엇인지 정의한 것이 추상 자료형이다.

✔︎ 추상 자료형의 필요성

추상 자료형은 구현자와 사용자를 분리한다. 라이브러리를 가져다 쓰거나 내장 함수를 사용하는 것도 추상 자료형이 정의되어 있기 때문이다. 또한 추상 자료형에 대한 구현은 외부로 부터 숨겨져 정보 은닉(Information Hiding)이 이루어지게 된다.

숫자형, 문자열, 리스트, 셋 등의 데이터 타입 등이 있다. 나는 각 자료형이 어떤 형태로 데이터가 저장이 되는지, 자료의 삽입/삭제/탐색 등 필요한 작업은 어떠한 것이 있는지 정도만 안다. 이것이 바로 추상 자료형이다.

추상 자료형을 구체적으로 어떻게 구현하는가에 대해서 고민하고 정리하는 것은 자료 구조의 영역이다.

추상 자료형 중 선형 자료 구조의 대표적인 예인 스택(Stack)에 대해서 생각해보자.
나는 '스택'이라는 자료형이 push로 자료를 삽입하고, pop를 사용해서 가장 마지막에 삽입된 자료를 꺼낸다는 것은 알고 있다.
하지만 각 메서드가 어떻게 구현되어 있는지는 알지못한다.

⭐️ 알고리즘 분석 방법

알고리즘을 비교 분석하는 이유
알고리즘을 왜 비교 분석할까? 실생활의 예를 들어보자.
만약 노트북을 사러 갔다고 하자. 노트북 매장에 들어갔더니 세 종류의 노트북이 보인다.

1. 맥북
2. 갤럭시북
3. LG 그램
   우리는 세 종류의 노트북 중 어떤 것을 고를지 고민이 된다. 이때 우리는 각 노트북을 비교하고 분석하며 나에게 잘 맞고 필요한 노트북을 고른다.
   이와 마찬가지로, 데이터를 처리할 때 순차 검색을 쓸지 이진 검색을 쓸지 고민할 때 뭐가 더 좋은지를 따지고 분석하는 이유와 같다. 그래서 알고리즘을 분석해야한다.

📌 알고리즘 실행 시간 측정 방법

알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터 상에서 실행 시켜 실행 시간을 측정하는 방법이다.
이때, 똑같은 하드웨어를 사용해서 알고리즘 수행 시간을 측정해야 한다.

자바의 경우

long beforeTime = System.currentTimeMillis(); //코드 실행 전 시간 받아오기

/** 측정할 코드 */
int sum = 0;
for (int i = 0; i < 1000000; i++) {
    for (int j = 0; j < 50000; j++) {
        sum += i*j;
    }
}
// System.out.println(sum);

long afterTime = System.currentTimeMillis(); //코드 실행 후 시간 받아오기
long secDiffTime = (afterTime - beforeTime)/1000; //전, 후 시간 차이 계산
System.out.println("시간차이(m) : "+secDiffTime);

//출력 결과: 시간차이(m) : 19 <- 오차 범위가 존재

실행시간 측정 방법은 알고리즘을 프로그래밍 언어로 구현한 뒤에 실행시켜 실행 시간을 측정하는 방법이기 때문에 수학적인 지식이 필요없다는 장점이 있다.

그러나
일반적인 기준에 부적합하다.

• 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등 수많은 변수가 존재
• 위의 문제를 모두 해결해도 문자열 구현, 함수 인자 전달 방식 등에 의해 최종 수행 시간의 편차가 커질 수 있음
• 프로그래밍의 실제 수행 시간이 입력의 크기나 특성에 따라 달라질 수 있음.

📌 알고리즘 복잡도 분석방법

실제 알고리즘을 구현해서 실행하지 않아도 알고리즘의 효율성을 따져보는 방법이다. 구현하지 않고도 모든 입력을 고려하는 방법으로 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

시간 복잡도와 공간 복잡도 측면을 고려할 수 있음.

• 시간 복잡도: 알고리즘 수행 시간 분석 -> 얼마나 빠른가?
• 공간 복잡도: 알고리즘이 사용하는 기억 공간 분석 -> 얼마나 많은 공간을 차지하는가?

그러나 대게 알고리즘 복잡도는 시간 복잡도를 의미한다.

✔︎ 시간복잡도(time complexity) 함수

시간복잡도(Time Complexity)는 알고리즘이 '얼마나 빠른가'를 나타내는 함수이며, 보통 함수 이름으로 T(n)을 사용한다. 즉, n과 T(n)의 관계를 구하는 것인데, 이 때 n은 input size가 된다.

시간 복잡도는 알고리즘을 이루는 연산들이 몇 번이나 수행되는지 숫자로 표시한다. '연산의 횟수'에 관심을 가지는 것이다.

시간 복잡도는 가장 널리 사용되는 알고리즘의 수행 시간 기준이다.

• 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력에 크기에 대한 함수로 표현한 것
• 시간 복잡도가 높다 = 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다.
• 가장 깊이 중첩된 반복문의 수행 횟수를 계산하는 것이 시간 복잡도의 대략적인 기준

시간 복잡도는 보통의 경우 점근적 표기법으로 사용되는데 주로 사용되는 점근적 표기법(Asymptotic notation)은 아래와 같이 3가지가 있다.

• Big-O 표기법 / O(N) : 최악의 실행시간을 표기한다
• Ω 표기법 / Ω(N) : 최상의 실행시간을 표기한다
• Θ 표기법 / Θ(N) : 평균 실행시간을 표기한다

점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미다.

[최선, 최악, 평균의 경우]

알고리즘의 효율성을 평가할 때는 3가지의 경우로 나누어서 평가한다.

최선의 경우(Best Case), 최악의 경우(Worst Case), 평균의 경우(Average Case)

• 최선의 경우(Best Case): 알고리즘의 수행시간이 가장 적게 걸리는 경우를 의미
• 최악의 경우(Worst Case): 알고리즘의 수행 시간이 가장 오래 걸리는 경우를 의미
• 평균의 경우(Average Case): 알고리즘의 모든 입력을 고려한 후, 입력이 발생하는 확률을 고려해 평균 수행시간을 구한다

정렬 알고리즘의 경우

---

예시로 선형 탐색 알고리즘에서의 최선, 최악, 평균의 경우를 알아보자.

선형 탐색 알고리즘

public static int LinearSearch(int[] arr, int find) {
    for (int i = 0; i < arr.length; i++) {
        if (find == arr[i]) { // 찾는 값이 배열에 있으면
          return i; // 위치를 반환함.
        }
    }
    return -1; // 찾는 값이 없음.
}

선형 탐색(Linear Search)을 간단히 설명하면 배열이 존재할 때 찾고 싶은 수를 맨 앞부터 하나하나 살펴보면서 찾는 방법이다.

경우	설명	수행 횟수	시간 복잡도
최선의 경우	찾으려는 원소가 배열의 맨 앞에 있을 때 알고리즘은 한 번만 실행되고 종료	1	O(1)
최악의 경우	배열에 해당 원소가 없을 때 알고리즘은 N번 반복하고 종료	N	O(N)
평균의 경우	주어진 배열이 항상 찾는 원소를 포함한다고 가정하면 반환 값의 기대치는 N/2	N/2	O(2/N)

✔︎ Big-O 표기법

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용되는 시간 복잡도 성능 표기법

• 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적
• 입력 자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도
• n의 값에 다른 함수의 상한 값을 나타내는 방법

빅오 표기법을 나타내는 방법은 기본 연산의 횟수가 다항식으로 표현되어 있을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수를 버리는 것이다. 이때 최고차항의 계수도 버리고 단지 차수만 사용한다.

특징

• 상수항 무시: 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.
  • 예를 들어, O(2N) -> O(N)
• 영향력 없는 항 무시: 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항 이외에 영향력이 없는 항들은 무시한다.
  • 예를 들어, O(N^2+2N+1) -> O(N^2)와 같이 영향력이 지배적인 N^2 이외에 영향력이 없는 항들은 무시한다.

수학적 정의

예시
f(n) = n^2 + 2n +3, g(n) = n^2이라고 가정하자.

f(n) <= kg(n) ->
즉, n^2 + 2n +3 <= kn^2 가 성립하는 k 값이 존재하기 때문에 알고리즘 다항식 f(n)은 빅오 표기법을 사용하여 O(n^2)로 나타낼 수 있다.

간단하게 f(n)의 최고차랑의 차수가 n^2이기에 O(n^2)으로 생각할수도 있다.

성능 비교

가장 왼쪽 O(1)으로 갈수록 실행 횟수가 적은 것 / 시간 복잡도가 낮은 것 이라 말할 수 있고, 가장 오른쪽 O(n!)으로 갈수록 실행 횟수가 많은 것 / 시간 복잡도가 높은 것 이라고 말할 수 있다.

O(1) 상수 시간

• 알고리즘이 입력에 관계 없이 연산이 수행된다. 즉 입력 데이터의 크기에 상관없이 일정한 시간이 걸린다.
• public void BigO(int n){ System.out.println("Hello Big-O"); }
• O(n) 선형 시간*
• 알고리즘이 입력한 개수인 n만큼 수행된다. 즉 입력 데이터가 증가할수록 처리시간도 증가한다.
• public void BigO(n){ for(int i=0; i<n; i++){ System.out.println(i); } }
• O(n^2) 2차 시간*
• 알고리즘이 입력한 개수의 n^2만큼 수행된다. 즉 입력 데이터가 증가할수록 처리시간이 제곱 배로 증가한다.
• public void BigO(n){ for(int i=0; i<n; i++){ Sysytem.out.println(i); for(int j=0; j<n; j++){ System.out.println(j); } } }

---

✔︎ 이외의 표기법

Big-Ω(오메가 표기법)

• 시간의 하한을 표기한 방법으로, 특정 알고리즘의 최선의 경우 시간 복잡도를 나타낸다.
  • Big-O 표기법의 경우와 큰 차이는 없다. 단지 상한 값을 나타내는지, 하한 값을 나타내는지 차이이다.
    k*g(n) <= f(n)

Big-Θ(세타 표기법)

• 시간의 상한과 하한을 동시에 표기한 방법으로, 특정 알고리즘의 평균의 경우 시간 복잡도를 나타낸다.
  • 간단하게 생각하면 빅오 표기법과 오메가 표기법을 합친 것이다.
    k1*g(n) <= f(n) <= k2*g(n)

3가지 표기법 중 가장 정밀한 것은 평균인 '세타 표기법'이다. 그러나 평가하기가 까다롭기에 통상적으로 'Big-O 표기법'을 주로 사용한다.
알고리즘이 최악일때의 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽기때문이다.

---

출처
https://ledgku.tistory.com/41
https://ybdata-sci.tistory.com/16
https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%84%A0,_%EC%B5%9C%EC%95%85,_%EA%B7%B8%EB%A6%AC%EA%B3%A0_%ED%8F%89%EA%B7%A0%EC%9D%98_%EA%B2%BD%EC%9A%B0
https://yurimkoo.github.io/algorithm/2020/05/09/time-complexity-1.html
https://eunguru.tistory.com/48
https://ooeunz.tistory.com/30
https://noahlogs.tistory.com/27