시간복잡도

0. 알고리즘

• 복잡도
  1. 시간복잡도
  2. 공간복잡도

1. 시간복잡도(Time Complexity)

• 알고리즘이 실행될 때 필요한 입력값과 연산 수행 시간에 따라 효율적인 알고리즘을 나타내는 척도
• 즉, 입력값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는지에 따른 지표
  • Big O 표기법 사용. >> 수치가 작을수록 효율적인 알고리즘.

2. 공간 복잡도(Space Complexity)

• 알고리즘이 실행될 때 필요한 메모리 공간의 양을 의미.
• 즉, 알고리즘의 효율성을 판단하는 데 사용. 일반적으로 메모리 사용량이 적을수록 효율적인 알고리즘이라 판단.

공간 복잡도는 일반적으로 시간 복잡도와 함께 고려되며 알고리즘이 실행되는 환경에 따라 달라질 수 있다. 예를들어 일부 알고리즘은 실행될 때 추가적인 메모리를 필요로 하지 않지만 다른 알고리즘은 입력 데이터의 양에 따라 필요한 메모리 공간이 증가할 수 있다.

따라서 알고리즘을 설계할땐 시간, 공간 복잡도를 함께 고려해야한다.

3. Big O notation

• 알고리즘의 입력 크기에 대해 수행 시간이 어떤 방식으로 증가하는지 표기하는 것으로 최악의 경우의 시간 복잡도를 의미.

  • 최악의 경우의 시간복도란 알고리즘이 입력 크기에 따라 가장 오래 걸리는 경우를 의미.

• 3-1. 빅오 복잡성 차트(Big-O Complexity Chart)

표기법	이름	시간 복잡도	설명	예시
O(1)	상수	상수 시간	입력 크기와 상관없이 일정한 실행 시간을 가진다.	배열에서 원소 하나 찾기
O(logn)	로그	로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가.	이진 탐색 알고리즘
O(n)	선형	선형 시간	입력 크기와 비례하는 실행 시간	선형 탐색 알고리즘
O(nlogn)	로그 선형	선형 로그 시간	입력 크기가 증가함에 따라 실행시간이 로그함수와 선형함수의 곱 형태로 증가	병합, 힙 정렬 알고리즘
O(n^2)	이차	이차 시간	입력 크기의 제곱에 비례하는 실행 시간	선택, 버블, 퀵 정렬 알고리즘
O(2^n)	지수	지수 시간	입력 크기의 지수에 비례하는 실행 시간	부분 집합
O(n!)	계승	팩토리얼 시간	입력 크기의 팩토리얼에 비례하는 실행 시간	외판원 문제

• 3-2. 표기법 예시

1. O(n)

   // O(1)
   public static int getFirst(int[] nums) {
       return nums[0];
   }

2. O(log n)

   // O(log n) 이진 탐색 알고리즘
   public static int binarySearch(int[] nums, int target) {
       int left = 0, right = nums.length - 1;
       while (left <= right) {
           int mid = left + (right - left) / 2;
           if (nums[mid] == target) {
               return mid;
           } else if (nums[mid] < target) {
               left = mid + 1;
           } else {
               right = mid - 1;
           }
       }
       return -1;
   }

3. O(n)

   // O(n)
   public static int[] reverse(int[] nums) {
       int[] reversed = new int[nums.length];
       for (int i = 0; i < nums.length; i++) {
           reversed[nums.length - i - 1] = nums[i];
       }
       return reversed;
   }

4. O(nlog n)

   // O(nlog n) 병합 정렬
   public static void mergeSort(int[] nums, int left, int right) {
       if (left < right) {
           int mid = left + (right - left) / 2;
           mergeSort(nums, left, mid);
           mergeSort(nums, mid + 1, right);
           merge(nums, left, mid, right);
       }
   }

5. O(n^2)

   // O(n^2) 선택 정렬
   public static void selectionSort(int[] nums) {
       for (int i = 0; i < nums.length - 1; i++) {
           int minIdx = i;
           for (int j = i + 1; j < nums.length; j++) {
               if (nums[j] < nums[minIdx]) {
                   minIdx = j;
               }
           }
           int tmp = nums[i];
           nums[i] = nums[minIdx];
           nums[minIdx] = tmp;
       }
   }

6. O(2^n)

   // O(2^n) 피보나치 수열
   public static int fibonacci(int n) {
       if (n <= 1) {
           return n;
       }
       return fibonacci(n - 1) + fibonacci(n - 2);
   }