시간 복잡도
시간 복잡도란 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간입니다.
로직의 반복 횟수를 중점으로 측정되고, 보통 빅오 표기법으로 나타냅니다.
for (int i = 0; i < 10; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (true) {
System.out.println(k);
}
}
}
}
for (int i = 0; i < n; i++) {
if (true) {
System.out.println(i);
}
}가령 위 코드와 같이 로직이 짜여져 있다고 가정해 보겠습니다.
시간 복잡도는 10회 반복로직 안에 n회 반복 로직이 총 두개 즉 10 * n * n 으로 계산할 수 있습니다.
그리고 두번째 로직에서는 n회 반복이므로 총 두개를 합치면 10n^2 + n으로 계산할 수 있습니다.
빅오 표기법
빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것입니다.
위에서 말한 코드의 시간 복잡도를 빅오 표기법으로 나타낸다면 O(n^2)이 됩니다.
그럼 여기서 의문점이 생길 수 있다고 생각합니다.
"왜 O(n^2)+O(n)이 아니라 O(n^2)이지??"
빅오 표기법의 이론은 입력 크기가 커질수록 연산량이 가장 많이 커지는 항만 신경 쓰면 된다는 이론을 전재로 하기 때문에 가장 영향을 많이 끼치는 제곱항만 표시하는 것입니다.
그럼 자료구조에서 각각의 평균 시간 복잡도는 어떻게 되는지 한눈에 표로 알아보겠습니다.
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택, 큐, 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리, AVL, 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
많은 자료구조 중, 오늘은 스택, 큐, 이중 연결 리스트에 대해서 간단한 예제와 함께 더 알아보겠습니다.
스택
스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질인 LIFO(Last In First Out)를 가진 자료 구조입니다.
삽입 및 삭제에서 0(1), 탐색에 O(n)이 걸립니다.
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> stk = new Stack<>();
for (int i = 0; i < 10; i++) {
stk.push(i);
}
while (!stk.isEmpty()) {
System.out.print(stk.peek() + " ");
stk.pop();
}
}
}
위 코드는 가장 기본적인 스택 자료 구조를 구현한 코드라고 볼 수 있습니다.
분명 스택에 들어간 순서는 0 -> 9까지 이지만, 실제로 위 코드를 실행해보면 LIFO 구조대로 역순인
9 8 7 6 5 4 3 2 1 0 가 출력됩니다.
큐
큐는 먼저 집어넣은 데이터가 먼저 나오는 성질인 FIFO(First In First Out)를 지닌 자료구조 입니다.
먼저 집어넣은 데이터가 먼저 나오는 개념을 가졌고, 삽입 및 삭제에서 O(1), 탐색에서 O(n)이 걸립니다.
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < 10; i++) {
queue.add(i);
}
while (!queue.isEmpty()) {
System.out.print(queue.peek() + " ");
queue.poll();
}
}
}
위 코드는 가장 기본적인 큐 자료 구조를 구현한 코드라고 볼 수 있습니다.
스택과는 다르게 들어간 순서대로 결과가 출력되는 걸 볼 수 있습니다.
이중 연결 리스트
이중 연결 리스트는 각 노드가 앞뒤로 연결된 형태로, 양방향 접근이 가능한 자료 구조입니다.
각 노드는 이전 노드를 가리키는 prev 포인터와 다음 노드를 가리키는 next 포인터를 포함하여 리스트 양쪽 방향으로 순회할 수 있는 구조를 가집니다.
보통 삽입 및 삭제에서 O(1), 탐색에서 O(n)이 걸립니다.
class DoublyLinkedList {
private class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node head;
private Node tail;
// 이중 연결 리스트에 노드 추가 (맨 뒤에 추가)
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// 이중 연결 리스트의 노드 삭제 (맨 앞에서 삭제)
public void remove() {
if (head == null) {
System.out.println("리스트가 비어있습니다.");
return;
}
if (head == tail) {
head = tail = null;
} else {
head = head.next;
head.prev = null;
}
}
// 이중 연결 리스트의 모든 요소 출력 (앞에서부터 순차 출력)
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
// 노드 추가
list.add(10);
list.add(20);
list.add(30);
System.out.print("리스트 추가 후: ");
list.printList(); // 10 20 30
// 노드 삭제
list.remove();
System.out.print("노드 하나 삭제 후: ");
list.printList(); // 20 30
// 다시 노드 추가
list.add(40);
System.out.print("다시 추가 후: ");
list.printList(); // 20 30 40
}
}
- 출력 결과
리스트 추가 후: 10 20 30
노드 하나 삭제 후: 20 30
다시 추가 후: 20 30 40
일단 노드를 정의하고, 각 메서드(add, remove, printList)를 정의합니다.
add : 이중 연결 리스트의 끝에 새로운 노드를 추가
remove : 리스트의 맨 앞 노드를 삭제
printList : 리스트의 모든 노드를 순서대로 출력
오늘 예제와 함께 알아본 3가지 자료구조 이외에 이진 탐색 트리, AVL, 레드 블랙 트리는 다음에 예제와 함께 더 알아보는 시간을 가져보겠습니다.