[자료구조] 자료 구조와 알고리즘 기본 개념 / 시간 복잡도 / 빅오 표기법

01. 자료구조(Data Structure)란?

자료구조란, 일련의 동일한 타입의 데이터를 정리하여 저장한 구성체를 뜻한다. 이는 크게 선형 자료구조와 비선형 자료구조 두 가지로 나뉜다.

1. 선형 자료구조
: 이름 그대로, 선형의 모형을 띄고 있는 데이터로 구성된 자료구조를 의미힌다. 데이터를 한 줄로 나열하여 순차적으로 표현하였으며, 선형 리스트, 연결 리스트, 스택, 큐 등이 이에 속한다.

선형 자료구조의 형태

2. 비선형 자료구조
: 비선형 모형을 띄고 있는 데이터로 구성된 자료구조를 의미한다. 하나의 데이터 뒤에 여러 개가 이어지는 형태이며, 트리나 그래프 등이 이에 속한다.

비선형 자료구조의 형태

---

02. 알고리즘(Algorithm)이란?

알고리즘이란, 문제를 "유한한 시간동안" 해결하는 단계적 절차를 의미한다. 만약 무한루프에 걸려 무한한 시간이 걸린다면, 해당 문제는 해결될 수 없기 때문에 "유한한 시간 내에" 해결되어야 한다는 것이 중요하다.

앞서 간단히 공부한 자료구조와 알고리즘의 개념 두 가지가 합쳐저 지칭하는 포괄적인 개념을 프로그램이라고 한다.

프로그램 = 자료구조 + 알고리즘

그렇다면, 알고리즘의 성능은 어떻게 판단할까?
해당 알고리즘이 효율적인지를 판단하는 방법은 크게 두 가지이다. 하나는 메모리가 적절히 활용되었는가, 그리고 또 다른 것은 실행 시간이 얼마나 되는가. 여기서 메모리 활용을 판단하는 방식은 공간 복잡도가, 실행시간을 판단하는 방식은 시간복잡도가 대표적이다. 

하지만 최근에는 메모리의 가성비가 매우 좋아져 메모리 공간 문제는 크게 중요하지 않게 되었다. 따라서, 시간 복잡도를 중심으로 알아보고자 한다.

---

03. 시간 복잡도 (Time Complexity)

1. 시간 복잡도의 개념

시간 복잡도란, 알고리즘을 수행하기 위해 실행해야 하는 연산을 수치화한 것이다. 즉, 기본적인 연산 횟수를 입력 크기의 함수로 표현하는 방식이다. 그렇다면 왜 시간이 아닌 연산 횟수로 표현하는 것일까? << 라는 개인적이 호기심이 생겨 찾아본 결과, 컴퓨터 사양마다 실행 시간은 상이하기 때문에 객관적 지표인 연산 횟수를 기반으로 판단하는 것이라는 답변을 얻을 수 있었다.

2. 실행시간의 접근 표기법

그렇다면, 이 실행시간은 어떻게 표현하는 것일까? 
이를 표현하기 위한 방법은 대표적으로 세 가지가 있다. 바로 빅오(Big-Oh) 표기법, 빅오메가(Big-Omega) 표기법, 세타(Theta) 표기법이다. 각각에 대해 더 자세하게 알아보자.

01) O (Big-Oh) 표기법
가장 대표적인 방식인 빅오 표기법은 함수 증가율의 상한을 표현한 방식이다. 다시 말해 "이 정도의 시간까지 소요될 수 있다!" 와 같은 느낌으로 최악의 실행 시간을 계산하여 표현해준다. 필자는 이 부분에서 많이 헷갈렸는데 이런 식으로 이해하면 쉬울 것이다.
알고리즘의 경우, 시간이 많이 소요될수록 효율족이지 못한 것이기 때문에 최대로 걸릴 수 있는 시간을 파악하는 빅오표기법은 최악을 파악하는 시간 복잡도 방식이다. 그리고 알고리즘 시간 표기에 있어서 가장 이상적인 것은 최악의 실행 시간을 표기하는 것이기 때문에, 빅오 표기법은 가장 대표적으로 사용되는 접근 표기법이다.
이에 대한 더욱 구체적인 내용은 아래에서 다루도록 하겠다.

02) Ω (Big-Omega) 표기법
빅 오메가 표현법은 최선을 표기하는 방식이다. 예를 들어 한 알고리즘이 실행되는 데에 최소 1초에서 최대 100초가 걸린다고 했을 때, 빅 오메가 표현법은 1초가 걸린다고 표기한다. 모든 N ≥ N0에 대해서 f(N) ≥ cg(N)이 성립하는 양의 상수 c와 N0이 존재하면, f(N) = Ω(g(N))이다. 그리고 g(N)을 f(N)의 하한(Lower Bound)이라고 한다.

빅오메가 표기법

03) Θ (Theta) 표기법
마지막은 세타 표기법이다. 이는 실행 시간의 평균을 표기한다. 예를 들어 한 알고리즘의 실행시간이 최소 1초, 평균 30초, 최대 100초가 소요된다고 했을 때, 세타 표기법은 30초라고 표기하는 방식이다. 이는 모든 N ≥ N0에 대해서 c1g(N) ≥ f(N) ≥ c2g(N)이 성립하는 양의 상수 c1, c2, N0가 존재하면, f(N) = Θ(g(N))으로 본다. 

세타 표기법

---

04. O (빅오, Big-Oh) 표기법

빅오 표기법에 대한 이론적 설명은 위에서 진행했기 때문에, 이번에는 빅오 표기법의 종류와 각각의 예시 코드를 알아보도록 하겠다. 우선 빅오 표기법의 종류에는 대표적으로 7가지가 있다.

- O(1) : 상수시간
- O(logN) : 로그(대수)시간
- O(N) : 선형시간
- O(NlogN) : 로그선형시간
- O(N^2) : 제곱시간
- O(N^3) : 세제곱시간
- O(2^N) : 지수시간

그래프로 나타내면 아래와 같은데, O(1) - 즉, 상수시간 - 이 가장 효율이 좋고, 그 다음 순서로 갈수록 (그래프 기준 좌상단으로 갈수록) 시간이 오래 걸린다고 보면 이해하기 쉬울 것이다.

---

05. 빅오 표기법 계산 예제

## O(log n)
i = 1
while i < n:
    i *= 2


## O(n log n)
for i in range(n):          # n번
    j = 1
    while j < n:            # log n번
        j *= 2
        print(i, j)


## O(n)
for i in arr:
    print(i)


## O(n)
def func17(n):
    if n <= 1:
        return
    func17(n - 1)
    
    
## O(n²)
for i in range(n):
    for j in range(n):
        print(i, j)


## O(n³)
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)


## O(2ⁿ)
def func15(n):
    if n <= 1:
        return
    func15(n - 1)
    func15(n - 1)

요약하자면 아래와 같다.

패턴	시간복잡도	예시
상수 반복	O(1)	for i in range(20)
로그 반복	O(logN)	while i < n:     i *= 2
선형 반복	O(n)	for i in range(n)
이중 반복	O(n^2)	for i in range(n) :    for j in range(n)
삼중 반복	O(n^3)	3중 for문
선형 + 로그 반복	O(NlogN)	for i in range(n):    while j < n:       j *= 2
이진 재귀 호출	O(2^n)	func(n-1) func(n-1)

끝으로 꿀팁 하나를 기록하자면, 필자의 경우 위의 예제 코드들 중에서 가장 헷갈렸던 것은 O(logN) 계산 식이었다. O(logN)의 경우, 2씩 나누거나 곱하는 문제에서 주로 등장하는데, 이는 n을 2로 계속 나누면 몇 번의 나누기 연산을 해야 1이 되는지를 생각하면 쉽다. (곱하기의 경우, 2를 몇 번 곱해야 주어진 숫자에 도달하는지)

---

그럼 이번 포스팅은 여기서 마무리하도록 하겠다.
1년간의 휴학 기간을 마치고 처음으로 작성하는 글이었는데, 오랜만이어서 그런지 생각보다 시간이 많이 소요된 것 같기도 하다. 시험기간이라 공부도 할 겸 작성해보았더니 재미도 있고 정리도 되었다. 앞으로도 이런 식으로 종종 업로드하도록 하겠다.