시간복잡도

• 알고리즘 문제를 풀다 보면 문제에 대한 해답을 찾는 것이 주요 관건이다. 문제를 풀다가,
  효율적인 방법을 고민한다는 것은 시간 복잡도 를 고민한다는 것과 같은 말이다.

• 시간 복잡도를 표기하는 방법은 다음과 같다.

  Big-O(빅-오)
  Big-Ω(빅-오메가)
  Big-θ(빅-세타)

  위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법으로, 이 중에서 Big-O 표기법 가장 자주 사용된다. 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직하기 때문에 다른 표기법보다 Big-O 표기법을 많이 사용한다.

Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가 를 표기하는 방법이다.

---

---

O(1)

• O(1)는 constant complexity 라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

public int O_1_algorithm(int[] arr, int index) {
  return arr[index];
}

int[] arr = new int[]{1,2,3,4,5};
int index = 1;
int results = O_1_algorithm(arr, index);
System.out.println(results); // 2

• 위 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다. 예를 들어 arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있다.

---

O(n)

• O(n)은 linear complexity 라고 부르며 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

public void O_n_algorithm(int n) {
	for(int i = 0; i < n; i++) {
	// do something for 1 second
	}
}

public void another_O_n_algorithm(int n) {
	for(int i = 0; i < n * 2; i++) {
	// do something for 1 second
	}
}

O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가한다. 즉, 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다.

another_O_n_algorithm 은 입력값이 1 증가할 때마다 코드의 실행 시간이 2초씩 증가한다. 이 알고리즘 또한 Big-O 표기법으로는 O(n)으로 표기한다. 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다.

O(log n)

O(log n)은 logarithmic complexity 라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다. 이해하기 쉬운 게임으로 비유해 보자면 up & down 을 예로 들 수 있다.
BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다.

O(n^2)

O(n^2)은 quadratic complexity 라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

public void O_quadratic_algorithm(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			// do something for 1 second
		}
	}
}

public void another_O_quadratic_algorithm(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			for(int k = 0; k < n; k++) {
				// do something for 1 second
			}
		}
	}
}

2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n^3과 n^5 도 모두 O(n^2)로 표기한다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기한다.

O(2^n)

O(2^n)은 exponential complexity 라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다. 구현한 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.

public int fibonacci(int n) {
	if(n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci (n - 2);
}

• 재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘이다.

class Stack {

  private ArrayList<Integer> listStack = new ArrayList<Integer>();

  public void push(Integer data) {
    listStack.add(data);
  }

  public Integer pop() {
    return listStack.remove(listStack.size() - 1);
  }

  public boolean contains(Integer data) {
    return listStack.contains(data);
  }
}

Stack stack = new Stack();

💡

• 시간 복잡도 빠른 순서

  O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) < O(n!)

• stack 에서 찾을 수 있는 시간 복잡도는
  • 스택에 새로운 요소를 넣거나 뺄 때 발생하는 O(1) 이 있다. (넣을 때와 뺄 때 가장 마지막 요소를 넣거나 뺀다.)
  • 스택을 탐색하는 O(n) 이 있다. (스택 한 번 순회)