026 | Time Complexity

💙 시간 복잡도

알고리즘에서는 문제에 대한 해답을 찾는 것과 함께 얼마나 효율적인 방법으로 문제를 해결했는지도 중요하다. 문제를 풀다가 더 효율적인 방법은 뭐가 있을지, 이게 제일 좋은 방법이 맞을지 고민하는 것은 시간 복잡도를 고민한다는 것과 같다.

🤍 개념

• 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 얼만큼의 시간이 걸리는지를 고려하는 것
• 효율적인 알고리즘을 구현하는 것 = 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 것

🤍 분류

• 최악의 경우(Worst Case): 최악의 시나리오로, 빅 오(Big-O) 표기법 사용
• 최선의 경우(Best Case): 최선의 시나리오로, 빅 오메가(Big-Ω) 표기법 사용
• 평균적인 경우(Average Case): 평균 시간을 나타내며, 빅 세타(Big-θ) 표기법 사용

💙 Big-O 표기법

🤍 목적

• 불필요한 연산을 제거하고 알고리즘 분석을 쉽게 함

🤍 복합성

• 시간 복잡도
• 공간 복잡도
• 오른쪽으로 갈 수록 시간 복잡도가 크며(수행 시간이 김), 시간 복잡도를 낮출 수록 프로그램 성능이 향상됨
• 시간 복잡도에서 중요한 것은, 정해진 표현식에서 가장 큰 영향을 미치는 n의 단위
• 시간 복잡도를 분석한다는 것은 입력값 n으로 알고리즘이 문제를 해결하는 데 얼마나 오랜 시간이 걸리는 지를 분석하는 것 ⇒ Big-O로 정의

💫 O(1) - 상수/일정한 복잡도 (Constant Complexity)

입력값이 증가해도 시간이 늘어나지 않음

💫 O(log n) - 로그 복잡도 (Logarithmic Complexity)

자료구조에서 배웠던 BST(Binary Search Tree)에서 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어드는 것과 같은 논리

• 예시
  • n이 주어졌을 때 계속해서 반씩 줄어들기 때문에 연산 횟수는 log2(n)이고 빅오표기법으로 나타내면 O(log n)

int i = n;
while (i > 0) {
  i /= 2;
}

💫 O(n) - 선형/직선적 시간 (Linear Complexity)

입력값의 증가와 시간이 같은 비율로 증가

• 예시_1
  • for문 내 코드가 arr 길이만큼 실행됨. arr 길이를 n이라고 하면 O(n)이라고 빨리 파악할 수 있음

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

int[] arr = new int[]{1, 2, 3, 4, 5};
for(int i = 0; i < arr.length; i += 1){
  int result = chooseOne(arr, i);
  System.out.println(result);
}

• 예시_2
  • 첫번째 반복문은 n번을 실행하고, 두번째 반복문은 n-1번 반복

int a = 0, 
int b = 0;

for(int i = 1; i < n; i+=1) {
    a += 1;
}

for(int j = 2; j < n; j+=1) {
    b += 1;
}

💫 O(n^2) - 2차 시간 (Quadratic Complexity)

입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것

예를 들어, 입력값이 1일 때, 1초가 걸리던 알고리즘에 5라는 입력값을 줄 때 25초(5^2)가 걸리면 이 알고리즘의 시간 복잡도는 O(n^2)라고 표현한다.

• 예시
  • n개의 i에 대해 각각 n개의 j를 가지고 로직을 수행함. Big-O notation에서는 계수와 상수항을 제외하고 표현

for(int i = 0; i < n; i++) {
  for(int j = 0; j < n; j++) {
    // do something with i and j
  }
}

💫 O(2^n) - 지수/기하급수적 시간 (Exponential Complexity)

가장 느린 복잡도로, 구현한 알고리즘의 시간 복잡도가 지수 시간이라면 다른 방식을 고려하는 것이 좋음

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

🤍 퀴즈

❓두 알고리즘 A, B의 시간 복잡도가 각각 O(n), O(log n)이면, 알고리즘 B는 알고리즘 A보다 항상 빠르다?

❗항상 빠른 것은 아님

• n이 점점 커질수록 B가 더 빨라짐
  • input 1개:  둘 다 1
  • input 2개:  1 / 2
  • input 4개: 2 / 4
  • input 8개: 3 / 8

❓ 다음 스택을 표현한 코드에서 나올 수 있는 시간 복잡도는?

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(n)

• O(1): 스택에 새로운 요소를 넣거나 뺄 때 발생 (넣을 때와 뺄 때 가장 마지막 요소를 넣거나 뺌)
• O(n)스택을 탐색 (스택 한 번 순회)