초심자를 위한 알고리즘과 자료구조 2편 - 알고리즘의 효율성, 시간 복잡도, 빅오 표기법(Big-O Notation)

- 해당 글은 비전공자 혹은 개발 초심자를 대상으로 하는 글입니다. 다소 비전문적이고 구어체에 가까운 표현이 등장하더라도 양해 부탁드립니다.

- 이번 글은 수학적 정의를 포함하고 있습니다. 최대한 쉽게 풀어쓰고자 노력했으나 이해하기 어려울 수 있습니다.

 

 

해당 글은 전 편의 내용과 이어집니다.

전편 보기 : https://dev-nicitis.tistory.com/2

초심자를 위한 알고리즘과 자료구조 1편 - 알고리즘

 

 

이번 글에서는 알고리즘의 효율성, 시간 복잡도, 빅 O 표기법에 관해 알아보도록 하겠습니다.

 

 

전편에서 알고리즘을 정의할 때 '문제를 해결하기 위한 방법으로 일련의 절차와 방법이 존재하는 표현한 것'이라고 말했습니다. 여기에 덧붙여서 알고리즘은 명료하고 모호하지 않은 표현을 사용해 표현하곤 합니다.

 

우리는 문제를 해결할 때 가능한 효율적인 방법을 따라 해결하려고 합니다.

알고리즘 또한 마찬가지로, 주어진 문제나 작업을 컴퓨터로 해결하려고 할 때 보다 효율적이고 보다 간단한 알고리즘을 사용하여 문제를 해결합니다.

 

1. 알고리즘의 효율성

알고리즘에서 효율성은 알고리즘이 사용하는 시간적 측면과 공간적 측면을 고려하여 평가합니다.

 

시간의 측면에서, 알고리즘이 적은 시간을 사용한다는 것은 알고리즘이 문제를 빠르게 해결하는 것입니다. 정렬 알고리즘을 보면 같은 성능, 같은 컴퓨터에서도 성능이 극명하게 갈리게 됩니다. 자료의 크기가 충분히 커지게 되면 정렬의 속도가 200배까지도 차이가 날 수 있습니다.

 

 

"삽입, 합병, 퀵, 힙, 기수 정렬 별 성능 테스트" (2020년 08년 25일) 까망눈연구소 블로그. 2019년, https://wogh8732.tistory.com/68

삽입, 합병, 퀵, 힙, 기수 정렬 별 성능 테스트

(궁금하신 분들은 위 블로그의 하단에 정리된 표를 확인해보세요. 다만 CPU 성능에 따라 실제 테스트 결과는 바뀔 수 있습니다.)

 

공간의 측면에서, 알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 것입니다. 보편적으로 속도가 빠른 알고리즘은 메모리 공간을 더 많이 사용하게 됩니다. 컴퓨터에서 메모리의 용량은 한계가 있기 때문에, 용량에 비해 알고리즘이 너무 많은 메모리 공간을 요구한다면 그 알고리즘은 실행할 수 없습니다. 아무리 빠른 속도로 문제를 해결하는 알고리즘이 있다고 해도 그만큼 메모리를 많이 사용하게 되면 사용할 수 없는 알고리즘인 것이죠.

 

1980년대를 화려하게 장식한 패밀리 컴퓨터, 이른바 패미컴에는 메모리 공간이 32KB밖에 존재하지 않았습니다. 지금으로 따지면 이미지 파일 하나, 소설과 같이 장문으로 되어 있는 텍스트 파일 하나 열기도 힘든 셈입니다. 이렇게 작은 메모리를 이용해 게임 하나를 구동시키기 위해서는 코드 한 줄 한 줄을 짜는 데에도 메모리 공간을 신경 써야만 했지요.

북미판 닌텐도 엔터테인먼트 시스템(NES). 위키백과 이미지 참조.

 

하지만 현재 상용 게이밍 컴퓨터에 사용되는 메모리 카드의 용량은 16GB~32GB에 달합니다. 16GB 메모리만 해도 32KB의 패미컴에 비하면 524,288배의 메모리 용량을 갖고 있지요.

(16GB = 17,179,869,184 Byte)

(32KB = 32,768 Byte)

 

그래서 최근에는 알고리즘의 메모리 공간 점유율은 이전보다 덜 중요하게 되었습니다. 메모리를 좀 더 사용해서 시간을 줄이더라도 충분히 많은 메모리 공간이 남기 때문입니다.

 

따라서 알고리즘의 효율성을 측정할 때에는 일반적으로 알고리즘의 시간적 측면을 중점적으로 평가하게 됩니다.

 

 

 

2. 시간 복잡도 (Time Complexity)

알고리즘의 효율성을 이야기할 때에는 시간 복잡도와 공간 복잡도라는 단어가 나옵니다.

시간 복잡도는 시간이 얼마나 걸리느냐와 관련되어 있고, 공간 복잡도는 메모리 공간을 얼마나 차지하느냐와 관련이 있습니다. 앞 파트에서 이야기했듯 최근에는 프로그램의 메모리 사용량은 상대적으로 덜 중요하게 다뤄지므로 이번 파트에서는 시간 복잡도를 중심적으로 다룰 겁니다.

 

위키백과의 정의에 따르면, 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킵니다.

알고리즘이 입력에 비해 얼마나 많은 시간이 걸리느냐를 통해 평가한다는 말이지요.

 

여기서 알고리즘의 입력이라는 말에 의아해 할 수 있는데요, 알고리즘의 입력이란 '자료의 개수'를 뜻합니다. 10명의 사람을 키 순으로 세우는 일과 100명의 사람을 키 순으로 세우는 일이 있다고 칩시다. 그러면 여기서 10명의 사람과 100명의 사람이 해당 정렬 알고리즘의 입력이 되겠지요.

 

알고리즘과 자료구조를 처음 공부하는 학생에겐 '시간과 입력의 함수 관계'라는 말이 무척 생소할 겁니다. 아마 다음과 같은 궁금증을 품은 사람도 있을 겁니다.

 

"알고리즘의 실행에 걸리는 시간이 궁금하니까 정확하게 '몇 초 걸린다'라고 말하면 되는 것 아닌가요?"

 

안타깝게도 그렇지 않습니다. 사람 두 명을 키순으로 세우는 경우와 사람 백 명을 키순으로 세우는 경우 무엇이 더 시간이 걸릴까요? 당연히 백 명을 세우는 데에 더 시간이 많이 걸립니다.

사과 하나를 깎는 것보다는 백 개를 깎는 편이 더 시간이 걸리겠지요. 컴퓨터도 마찬가지로, 10개의 숫자를 정렬하는 일은 0.1초도 되지 않아 끝나지만 1,000,000개의 숫자를 정렬하는 일은 10초가 넘게 걸릴 수도 있습니다.

 

즉, 입력의 크기에 따라 알고리즘이 실행되는 시간이 달라집니다. 따라서 알고리즘 실행에 걸리는 시간을 나타내는 척도 시간 복잡도는 입력의 크기를 고려하여 계산합니다.

 

그럼 알고리즘의 수행 시간은 어떤 기준으로 측정해야 할까요?

 

알고리즘 실행에 걸리는 시간은 알고리즘을 구성하는 명령어들이 실행되는 횟수에 명령어의 실행시간을 곱하면 구할 수 있습니다.

 

$(수행 시간) = (명령어의 수) \times (명령어 실행 시간)$

 

명령어의 실행 시간은 명령어마다, 컴퓨터의 성능에 따라 천차만별로 달라집니다.

 

다음과 같은 상황을 가정해볼까요?

명령어 $A$를 실행하는 데에 0.1초가 걸리고 명령어 $B$를 실행하는 데에 10초가 걸린다고 가정합시다.

명령어 $A$에 비해 명령어 $B$는 100배나 오래 걸리지요.

 

그러면 프로그램에서 걸리는 시간을 측정해봅시다.

 

(1) 명령어 $A$를 한 번 실행하는 프로그램 : 0.1초

(2) 명령어 $B$를 한 번 실행하는 프로그램 : 10초

(3) 명령어 $A$와 $B$를 각각 한 번 실행하는 프로그램 : 10.1초

(4) 명령어 $A$를 1만 번, 명령어 $B$를 한 번 실행하는 프로그램 : 1010초

 

명령어를 한 번씩 실행하는 (1)과 (2)를 비교하면 $B$ 명령어를 사용하는 프로그램 (2)의 실행 속도가 훨씬 느립니다.

(3)에서도 명령어 $A$는 $B$에 비해 시간이 별로 걸리지 않아 프로그램의 실행 속도에 큰 영향을 주지 못합니다.

그러나 프로그램 (4)에서 명령어 $A$를 1만 번 실행하니 상대적으로 느린 연산인 명령어 $B$가 주는 영향보다 $A$의 속도와 $A$를 얼마나 많이 실행하느냐가 중요해졌지요.

 

즉, 시간 복잡도는 명령어 하나의 실행 속도보다는 얼마나 많은 명령문을 수행하느냐, 즉 연산 횟수가 더 중요합니다.

 

 

3. 빅오 표기법 (Big-O Notation)

3-1. 직관적인 정의

3-1, 3-2, 3-3은 수학적이고 다소 어려운 내용을 다루고 있으니 유의하며 읽어주세요.

 

빅오 표기법(Big-O Notation)은 함수의 증가 양상을 다른 함수로써 표현하기 위한 수학적 방법입니다.

 

알고리즘의 시간 복잡도는 입력이 커질수록 결과를 얻기 위해 더 많은 작업을 수행해야 하기 때문에, 대체적으로 증가하는 형태를 보입니다. 그래서 증가 양상을 나타내는 빅오 표기법을 통해 시간 복잡도를 표현하곤 합니다.

 

어떻게 사용하는지를 보기 위해 실 예시를 봅시다.

 

(1) n개의 입력이 주어질 때, 어떤 프로그램을 실행하는 데에 걸리는 시간이 $f(n) = 3n$이라고 해봅시다.

이때 $f(n)$은 빅오 표기법으로 $O(n)$으로 표현합니다.

$f(n)$에서 상수를 제외하고 보면 $n$에 비례하므로 $O(n)$으로 표기합니다.

 

이렇게 함수가 해당 빅오를 가질 때 다음과 같이 씁니다.

$f(n)=O(n)$ 또는 $f(n) \in O(n)$

$in$ 기호를 통해 정의한 것이 좀 더 정확하긴 하지만 보통은 $=$ 등호를 이용해 씁니다.

 

(2) 만약 실행시간이 $g(n)=2n^2 + 5n$ 라면 $g(n) = O(n^2)$으로 표기합니다.

 

(3) 만약 실행시간이 $h(n)=10$이라면 빅오 표기법으로 $h(n) = O(1)$으로 표기합니다.

 

 

직관적으로 보면, 가장 차수가 큰 입력에서 계수를 제외한 값을 적는다고 볼 수 있겠네요.

 

여기서 빅오는 함수의 집합의 개념이기 때문에 $O(n) = f(n)$과 같이 쓰면 안 됩니다.

그리고 이름이 빅오인 만큼 $f(n) = o(n)$과 같이 소문자 o로 표시해도 안 됩니다. 소문자 o(n)은 대문자 O(n)을 잘못 쓴 것이 아니라 따로 정의가 있기 때문입니다.

 

그런데 여기서 2번의 결과를 보다가 의아한 분이 계실 겁니다.

$g(n)$의 결과가 $O(n^2 + n)$이 아니라 $O(n^2)$인가요?라는 궁금증이 생기실 텐데요.

 

이는 빅오의 수학적 정의에 극한의 개념이 들어가 있기 때문입니다.

 

 

3-2. 수학적 정의

빅오는 점근 표기법 중 하나입니다.

다른 표기법에는 빅 오메가(Big-Ω), 빅 세타(Big-Θ)가 있습니다.

리틀오(Little-o), 리틀 오메가(little-ω)도 있지만 범용적으로 사용하진 않습니다.

 

빅오를 엄밀하게 이해하기 위해 수학적 정의를 한 번 봅시다. 다만 빅오의 정의는 비전공자분이나 수학에 익숙하지 않은 분에게는 상당히 어려울 수 있으므로 이해하지 못하고 넘어가셔도 괜찮습니다.

 

나중에 이해할 수 있을 때 다시 보면 되니까요!

 

 

 

함수 $f(x), g(x)$에 대해 $f(x)$가 $O(g(x))$라는 것은 다음과 같습니다.

$x > k$일 때 $|f(x)|<|cg(x)|$을 만족하는 양의 실수 $c$와 실수 $k$가 존재한다.

 

집합으로 표현하면 다음과 같습니다.

$O(g) \equiv \{f| \exists c>0 \exists k \forall x>k:|f(x)|\leq|cg(x)|\}$

 

 

해석해보자면, $x$가 충분히 커졌을 때 $f(x)$보다 상수 c를 곱한 $cg(x)$가 절댓값이 더 커지게 되면

$f(x)=O(g(x))$(또는 $f(x) \in O(g(x))$)라고 할 수 있다는 겁니다.

 

여기서 $c$는 양의 실수이고, $x$가 충분히 커지는 기점은 $x$가 어떤 실수 $k$보다 커지는 때입니다.

 

 

이해하기 어려우신 분이 많을 거예요. 저 또한 처음 공부할 때는 이 정의를 듣는 순간 뇌 정지가 왔으니까요.

 

쉽게 예시를 들어서 보자면, $f(x)=3x$와 $g(x)=x^3$라는 함수가 있습니다.

편의를 위해 정의역을 x > 0이라고 가정하겠습니다.

 

해당 그래프는 Geogebra 그래픽 계산기를 통해 구성했습니다.

위의 그림에서 녹색 선은 $y = 3x$의 그래프, 붉은 곡선은 $y = x^3$의 그래프입니다.

두 그래프를 보시면 $x=\sqrt{3}\approx{1.732}$에서 만나고 있죠.

$x=1$에서는 $f(x)$의 그래프가 $g(x)$의 그래프보다 더 값이 크므로 $f(x)$의 절댓값이 $g(x)$의 절댓값보다 크죠.

 

그런데 $x>\sqrt{3}$에서는 모든 x에서 $f(x)$의 절댓값보다 $g(x)$의 절댓값이 커지게 됩니다.

 

즉, $x$가 $\sqrt{3}$보다 커지면 $f(x)$보다 $g(x)$가 절댓값이 더 커지게 됩니다.

 

위의 내용이 바로 빅오의 정의입니다.

빅오의 정의를 만족하니 $f(x)=O(g(x))=O(x^3)$가 성립하게 됩니다.

 

어느 정도 이해가 되시나요?

x의 값이 일정 이상으로 커지게 되었을 때 $f(x)$보다 $g(x)$에 상수를 곱한 것이 더 커지게 되면 $g(x)$는 $f(x)$의 상한 점근이 되게 됩니다.

 

 

일정 이상 커진다는 것은 극한의 엄밀한 정의와도 같습니다. 그래서 빅오 표기법은 다음과 같이 극한으로 정의할 수도 있습니다.

 

$\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} < \infty$

 

이 말은 즉, $f(n)=O(g(n))$이라는 말은 $f(n)$이 $g(n)$보다 차수가 작거나 같다는 뜻이기도 합니다.

 

(여기서 차수란 다항식의 지수가 될 수도 있고 아닐 수도 있습니다. 증가율이 클수록 차수가 크다고 말합니다.

$f(x)=\log_2 x$보다는 $g(x)=x$가, $g(x)=x$보다는 $h(x)=2^x$가 차수가 큽니다.

$f(x)=3x^2$와 $f(x)=7x^2+3n$는 가장 큰 차수의 항이 $x^2$로 같으므로 차수가 간주합니다.)

 

극한에 관한 자세한 설명을 했다가는 이미 수학이 잔뜩 묻은 이 포스팅에 미적분을 갖다 대는 꼴이 될 거 같아 생략하겠습니다.

 

여기서 주목할 만한 점은 두 함수의 차수가 같을 수도 있지만 $f(n)$이 더 작을 수도 있다는 겁니다.

 

 

3-3. 빅오의 특징

빅오의 특징은 상한 점근을 나타낸다는 것입니다.

 

빅오는 정확한 수치를 나타내지 않고 전체적인 추이를 나타내는 점근 표현입니다.

그런데 여기서 상한 점근이라는 것은, 함수가 자신보다 작다는 것은 나타낼 수 있지만 반대로 정확한 변화를 나타낼 수는 없습니다.

 

쉽게 말하면 빅오는 "이것보단 작을 것이다"를 나타냅니다.

 

이를 시간 복잡도에 적용해보면, 빅오 표기법은 알고리즘의 수행 시간이 '이 함수보다는 낮을 것'을 기대할 수는 있지만 정확하게 '이 정도의 시간이 걸릴 것이다'를 나타낼 수는 없다는 말입니다.

 

$f(n) = 7n$일 때 $f(n)=O(n)$이라고 말할 수 있습니다.

그런데 빅오는 상한 점근을 나타내므로 $f(n)=O(n^2)$ 또한 맞는 말입니다.

$f(n)=O(n^100)$ 또한 옳은 식이 될 수 있습니다.

 

그래서 $f(n)=O(g(n))$이지만 좌항과 우항을 바꾸게 되면 $g(n) \neq O(f(n))$으로 성립하지 않을 수 있으니 주의해야 합니다.

 

본론으로 돌아와서, 어떤 함수가 $O(n)$의 증가율을 갖는다고 써 놓았다고 해도, 실제 함수는 더 작은 차수의 증가율을 가질 수도 있습니다.

 

그래서 정확한 차수를 나타내는 빅 세타(Big-Θ)를 사용하여 표현하는 편이 안전합니다.

빅 세타(Big-Θ)는 $f(n) \in O(g(n))$이고 $g(n) \in O(f(n))$일 때 $f(n)=Θ(g(n))$(혹은$f(n) \in Θ(g(n))$)이라 할 수 있습니다.

 

빅 세타에서는 서로가 서로의 상한 점근이기 때문에 둘은 차수가 같게 되어 보다 정확하게 함수의 증가를 표현할 수 있습니다.

그러나 정확한 함수의 증가를 구하기는 어렵기 때문에 컴퓨터 과학(Computer Science) 분야에서는 시간 복잡도를 표현할 때 빅 세타(Big-Θ) 대신 주로 빅오(Big-O)를 사용합니다.

 

(관습적으로 빅오는 최대한 가장 작은 차수를 고르도록 되어 있습니다. 위의 경우와 같이 $O(n^{100})$으로 부풀려 표현하는 경우는 잘 없고, $f(n)=7n$이면 가장 낮은 상한 점근인 $O(n)$을 고르도록 되어 있습니다.)

 

 

간단하게 특징을 정리하면 빅오는 다음 특징을 갖습니다.

 

1. 상수 계수를 무시한다

- 빅오 표기법은 함수의 차수를 확인하는 데에 더 중점을 두고 있습니다. $O(log_2 n)$이냐 $O(n)$이냐를 비교하므로 앞에 붙는 상수 계수는 무시합니다.

- $O(3n)$으로 표시하는 대신 $O(n)$으로 표시하는 셈입니다.

 

2. 가장 차수가 높은 항을 확인한다

- 빅오 표기법은 가장 높은 차수의 함수만을 표시합니다. 충분히 데이터의 입력인 n이 크다고 가정하기 때문입니다.

- $O(n^2 + 2n + 1)$는 $O(n^2)$으로 간추려 표현합니다.

- 다만 $O(|V| + |E|)$처럼 여러 변수가 섞여 있는 것은 그대로 표현합니다.

 

3. 좌항과 우항을 바꾸었을 때 성립하지 않을 수 있다

- 빅오는 상한 점근을 나타냅니다. $f(n)=O(g(n))$은 $f(n) \in O(g(n))$과 같다고 했죠? 실제로 빅오는 함수의 집합이라서 $f(n)=O(g(n))$이라는 건 둘이 같다는 것이 아니라 $f(n)$이 $O(g(n))$에 포함된다($\in$)는 의미입니다.

- $f(n)=O(g(n))$이라고 해서 $g(n)=O(f(n))$처럼 좌우를 바꾸면 성립할 수도, 성립하지 않을 수도 있습니다.

 

 

4. 빅오의 성능 비교

이 복잡하고 난해한 내용을 끝까지 읽느라 고생 많으셨습니다.

 

마지막으로 빅오 표기법 별 성능과 특별한 이름에 대해서 그래프를 보고 마칠게요.

 

이미지 출처 : Understanding Big-O Notation With JavaScript

위는 빅오 표기법을 통해 본 시간 복잡도를 그래프 화한 것입니다.

 

일부 빅오 표기법은 특별한 이름을 갖습니다. 가장 자주 사용하는 빅오 표기법의 이름을 알아봅시다.

 

- $O(1)$ - 상수 시간 (Constant)

- $O(log n)$ - 로그 시간 (Logarithmic)

(정보 이론에 영향을 받아 로그의 밑은 2를 사용함)

- $O(n)$ - 선형 시간 (Linear)

- $O(n^c)$ - 다항 시간 (Polynomial) (c는 상수)

- $O(2^n)$ - 지수 시간 (Exponential)

(지수를 적당히 조절하면 $O(c^n)$꼴로 만들 수 있다)

- $O(n!)$ - 계승 시간 (Factorial)

 

 

여기서 보셔야 할 것은,

상수 시간 $O(1)$ < 로그 시간 $O(log n)$ < 선형 시간 $O(n)$ < 다항 시간 $O(n^c)$ < 지수 시간 $O(c^n)$ < 계승 시간 $O(n!)$

딱 이 순서대로 시간 복잡도가 커진다는 것입니다.

 

데이터 입력(Data Input)의 크기가 일정 이상이 되면 상수 시간, 로그 시간, 선형 시간, 다항 시간, 지수 시간, 계승 시간의 순서대로 크기가 커지게 되죠.

위 그래프에서는 상수, 로그, 다항 시간만 나와 있지만 어느 정도 수가 커지면 다항 함수보다 지수 함수, 계승 함수의 크기가 커진다는 걸 고려하시면 상상하기 어렵지 않을 거예요.

 

따라서 입력이 어느 정도 커지면 지수 시간과 계승 시간의 알고리즘은 사용이 불가능할 정도로 시간이 오래 걸립니다.

 

데이터가 5개가 주어졌을 때는,

다항 : $5^{3} = 125$

지수 : $2^5 = 32$

계승 : $5! = 120$

으로 다항 함수가 좀 더 크게 나타납니다.

 

그런데 데이터가 100개가 주어지게 되면

다항 : $100^3 = 1,000,000$

지수 : $2^{100} = 1,267,650,600,228,229,401,496,703,205,376$

계승 : $100! = 9.3326215443944152681699238856267e+157$

이렇게 지수 함수와 계승 함수는 다항 함수와 비교할 수 없이 커지게 돼죠.

 

이를 역으로 생각해보면, 입력이 어느 정도 커지기 전까지는 상수 시간, 로그 시간의 시간 복잡도는 다항 시간, 지수 시간보다 더 느릴 수 있습니다.

아무리 상수 시간이 걸린다고 해도 하나를 실행하는 데에 10000초가 걸린다면 그 알고리즘은 의미가 없겠죠.

이 경우에는 상수 시간보다 선형 시간, 다항 시간의 알고리즘이 더 적합할 수도 있습니다.

 

 

 

그러므로 알고리즘과 자료구조를 사용할 때에는 각 알고리즘별로 어떤 시간 복잡도를 갖는지, 시간 복잡도는 어떤 특징을 갖는지를 충분히 이해하고 사용해야 사용해야 합니다.

 

이에 꼭 유의하시길 바라요.

 

 

오늘 포스팅은 여기까지입니다. 저번 포스팅에 비해 난이도가 급격하게 올라갔네요. 쉽게 풀어서 쓸 수 있었을 텐데 그러지 못해서 아쉽기도 하고 독자분들께 죄송하네요.

 

읽느라 수고하셨습니다.

 

만약 더 자세하게 공부하고 싶으시다면 'C언어로 쓴 자료구조론(Fundamentals of Data Structure in C)'이라는 책을 추천드립니다. 그걸로 자료구조를 처음 공부하기는 힘들지만, 더 자세하게 공부하고 싶을 땐 도움이 많이 될겁니다.

 

 

 

출처 및 참고 문헌

구종만, "알고리즘 문제해결전략", 인사이트, 2012년 11월 21일.

윤성우, "윤성우의 열혈 자료구조", 오렌지미디어, 2012년 1월 16일.

"삽입, 합병, 퀵, 힙, 기수 정렬 별 성능 테스트," 까망눈연구소 블로그. 2019년 수정, 2020년 8월 25일 접속, https://wogh8732.tistory.com/68

"멀티 메모리 컨트롤러", 위키백과, 2020년 8월 9일 수정, 2020년 8월 25일 접속, https://ko.wikipedia.org/wiki/%EB%A9%80%ED%8B%B0_%EB%A9%94%EB%AA%A8%EB%A6%AC_%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC

"패밀리 컴퓨터", 위키백과, 2020년 8월 12일 수정, 2020년 8월 25일 접속, https://ko.wikipedia.org/wiki/%ED%8C%A8%EB%B0%80%EB%A6%AC_%EC%BB%B4%ED%93%A8%ED%84%B0

"시간 복잡도", 위키백과, 2020년 5월 10일 수정, 2020년 8월 25일 접속, https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

"차 (수학)", 위키 백과, 2020년 7월 13일 수정, 2020년 8월 27일 접속, https://ko.wikipedia.org/wiki/%EC%B0%A8_(%EC%88%98%ED%95%99)

"점근 표기법", 위키백과, 2019년 11월 25일 수정, 2020 8월 27일 접속, https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

"Big O Notation", Wikipedia, last modified August 23, 2020, accessed Aug 27, 2020, https://en.wikipedia.org/wiki/Big_O_notation

"Understanding Big-O Notation With JavaScript", last modified February 17, 2020, accessed Aug 27, 2020, https://dev.to/b0nbon1/understanding-big-o-notation-with-javascript-25mc

이산치수학, 자료구조 시간 복습.