📒 갈무리 - 시간 복잡도(Time complexity)

📌 시간 복잡도란?

- 알고리즘이 문제를 해결하는데 걸리는 시간(연산)의 횟수를 말한다.

Big-Ω(빅 오메가) : 알고리즘의 최상의 실행 시간을 표기한다.(Best Case)

Big-O(빅 오) : 알고리즘의 최악의 실행 시간을 표기한다.(Worst Case)

Big-θ(빅 세타) : 알고리즘의 평균 실행 시간을 표기한다.(Average Case)

- Best Case 또는 Average Case로 시간 복잡도를 구한다면 최악의경우 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하기 때문에 문제 해결에 필요한 시간이 많이 필요하게 된다. 그렇기 때문에 항상 최악의 경우도 고려하여 대비하는 것이 좋기 때문에 Big-O(빅 오) 표기법을 주로 사용한다.

 

📌 Big-O 표기법이란?

- Big-O 알고리즘의 성능을 수학적으로 표현해주는 표기법

- 알고리즘의 시간과 공간 복잡도를 표현할 수 있다.

- 알고리즘의 실제 러닝 타임을 표현하는 것이 아니라 데이터나 사용자의 증가율에 따라 알고리즘의 성능을 예측하는 것이 목표

 

📌 Big-O 표기법의 특징

- 데이터나 사용자의 증가율이 무한대만큼 커질 수 있는 경우를 예상해야 하기 때문에 미미한 영향을 주는 것들은 배제하고 표기한다.

- 상수항을 무시한다.

- 계수를 무시한다.

- 최고차항만 표기한다.

 

📌 O(1)(Constant Time)

- 입력 데이터의 크기와 상관 없이 항상 일정한 처리시간이 걸리는 알고리즘

- 스택에서의 Push와 Pop

// C#
      public bool BigONotation(int[] data)
        {
            return (data[0] == 0) ? true : false;
        }

📌 O(n)(Linear Time)

- 입력 데이터의 크기에 비례하여 처리시간이 늘어나는 알고리즘

for문

// C#
       public void BigONotation(int[] data)
        {
            for (int i = 0; i < data.Length; i++) // 데이터의 개수 만큼
            {
                Console.WriteLine(i);
            }
        }

📌 O(n²)(Quadratic Time)

- 입력 데이터의 크기에 비례하여 처리시간이 n²인 알고리즘

- 이중 for문, 삽입정렬, 거품정렬, 선택정렬

// C#
        public void BigONotation(int[] data)
        {
            for (int i = 0; i < data.Length; i++) // data의 개수만큼
            {
                for (int j = 0; j < data.Length; j++) // data의 개수만큼
                {
                    Console.WriteLine(i + j);
                }
            }
        }

📌 O(2ⁿ)(Exponential Time)

- 입력 데이터가 하나 증가할 때마다 처리시간이 두배가 늘어나는 알고리즘

- 피보나치 수열

// C#
        public int Fibonacci(int value) // 피보나치 수열
        {
            if (value <= 2)
            {
                return 1;
            }
            return Fibonacci(value - 1) + Fibonacci(value - 2);
        }

📌 O(logN)(Logarithmic Time)

- 입력 데이터의 크기가 커질수록 처리시간이 로그만큼 짧아지는 알고리즘

- 이진 탐색

// C#
		// 이진 탐색
        public int BinarySearch(int key, int[] arr, int start, int end)
        {
            if (start > end)
            {
                return -1;
            }
            int mid = (start + end) / 2; // 중간값 찾음
            if (arr[mid] == key)
            {
                return mid;
            }
            else if (arr[mid] > key)
            {
                return BinarySearch(key, arr, start, mid - 1); // end를 중간지점 -1로 지정
            }
            return BinarySearch(key, arr, mid + 1, end); // start를 중간지점 +1로 지정
        }

📌 O(NlogN)(Linear-Logarithmic Time)

- 데이터의 크기가 커질수록 처리시간이 로그 배만큼 늘어나는 알고리즘

- 퀵정렬, 병합정렬, 힙정렬

// C#
		// 퀵정렬
        public void QuickSrot(int[] data, int start, int end)
        {
            if (start >= end)  // 원소가 1개인 경우
            {
                return;
            }
            int key = start; // 키는 첫번째 원소
            int i = start + 1;
            int j = end;
            int temp;

            while (i <= j) // 엇갈릴 때까지 반복
            {
                while (data[i] <= data[key]) // 피봇 값보다 큰 값을 만날 때까지
                {
                    i++;
                }
                while (data[j] >= data[key] && j > start) // 키 값보다 작은 값을 만날 때까지
                {
                    j--;
                }
                if (i > j) // 현재 엇갈린 상태면 키 값과 교체
                {
                    temp = data[j];
                    data[j] = data[key];
                    data[key] = temp;
                }
                else
                {
                    temp = data[j];
                    data[j] = data[i];
                    data[i] = temp;
                }
            }
            QuickSrot(data, start, j - 1); // end값을 -1
            QuickSrot(data, j + 1, end); /// start값을 +1
        }

📌 시간 복잡도에 따른 성능 비교

오른쪽으로 갈 수록 효율이 떨어진다.

O(1) < O(logN) < O(nLogn) < O(n²) < O(2ⁿ)