시간복잡도(Time Complexity) 란 ?

 

 

 

알고리즘 문제를 풀다보면 가끔 결과값은 올바르게 도출 되지만 시간 제한에 걸린다거나

연산 횟수가 기준 횟수를 초과하여 불합격 처리 되는 경우가 가끔 생긴다.

 

알고리즘을 사용해 코드를 구현할때 해당 방법이 효율적인지 고민한다는것은 이 시간복잡도를 

고려하는것과 같다고 볼 수 있다.

 

 

시간 복잡도 란 ?

 

• 코드를 실행할때 입력값과 해당 연산을 수행하는데 걸리는 시간과의 상관관계를 나타내는 척도이다.

 

• 주로 이 시간복잡도를 나타낼때는 빅-오(Big-O)* 표기법을 이용해 나타낸다. 

 

• 시간 복잡도 표기법은 입력값의 크기에 따라 걸리는 시간이 최선(오메가), 평균(세타), 최악(빅오)으로 나뉘지만 이 중 빅-오는 최악을 기준으로 한다.

 

 

빅-오(Big-O) 란 ?

 

 

• Big-O란 알고리즘이 수행되는데에 걸리는 시간이 얼마나 효율적인가를 표기하는 표기법이다.

 

• 그래프의 상한선을 기준으로 알고리즘의 성능을 모든 경우의 수를 포괄하여 표기한다.

 

• 표기법의 종류에는 [빠름] O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ) [느림] 등이 있다.

 

 

 

 

 

소모 시간 별 예제코드 계산 및 예시

 

 

• O(1) [상수 시간 복잡도]

 

- n과 상관 없이 항상 일정한 실행시간을 가지는 알고리즘 표현 방식이다.

보통 연산이 없거나 단순한 연산만 계산하며 탐색, 출력을 담당하는 경우가 많다.

 

 

namespace BigOTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int number = 10;

            PrintNum(number);
        }

        static public void PrintNum(int num)
        {
            Console.WriteLine("숫자는 : " + num);
        }
    }
}

 

 

 

 

• O(log n) [로그 시간 복잡도]

 

- 이진 탐색(Binary Search) 과 같이 배열을 반으로 쪼개나가며 각 단계의 절반 이상을 탐색하지 않고 지나가는 경우가 로그 시간 복잡도를 가진다.

 

- 일반적으로는 O(log n) 은 밑이 2인 O(log2n) 을 나타낸다.

 

 

 public static void Main()
 {
     int number = 1024;
     Console.WriteLine("최종적으로 나눈 횟수 : " + CountDivisions(number));
 }

 // 주어진 수를 2로 반복하여 나누고, 나눗셈이 수행된 횟수를 반환합니다.
 public static int CountDivisions(int num)
 {
     int count = 0;
     while (num > 1)
     {
         num /= 2;  // num을 2로 나눕니다.
         count++;   // 나눗셈이 수행된 횟수를 셉니다.
     }
     return count;
 }

 

 

 

 

 

• O(n) [선형 시간 복잡도]

 

- 입력 자료의 데이터 수(n) 에 비례해서 시간이 증가하는 알고리즘인 경우

 

- n에 따라 알고리즘 성능이 직관적으로 결정됨

 

 

public static void Main()
{
    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int sum = SumArray(array);
    Console.WriteLine("배열 요소들의 합은 : " + sum);
}

// 배열의 모든 요소의 합을 계산하는 메소드
public static int SumArray(int[] elements)
{
    int total = 0;
    for (int i = 0; i < elements.Length; i++)
    {
        total += elements[i];
    }
    return total;
}

 

 

 

 

• O(n²) [2차 시간 복잡도]

 

- 입력 데이터의 제곱 [O(n2)] 에 비례해서 시간이 증가하는 경우

 

- 입력값이 1일때 1초가 걸리던 알고리즘에 입력값일 5를 넣으면 25초가 걸리는 경우.

 

- 2중 for문, 버블 정렬등이 2차 시간 복잡도가 걸리는 알고리즘임.

 

 

public static void Main()
{
    int n = 5; // 예를 들어 n이 5라고 가정
    PrintAllPairs(n);
}

// 가능한 모든 숫자 쌍을 출력하는 메소드
public static void PrintAllPairs(int n)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            Console.WriteLine("Pair: (" + i + ", " + j + ")");
        }
    }
}

 

 

 

 

 

 

• O(2ⁿ) [지수 시간 복잡도]

 

-  알고리즘의 수행 시간이 입력 크기에 대해 지수적으로 증가하는 경우를 말함

• 2 x 1 = 2
• 2 x 2 = 4
• 2 x 3 = 8
• 2 x 10 = 1024
• 2 x 20 = 1,048,576

 

- 재귀 함수를 사용하는 피보나치 수열 계산 방식도 지수 시간 복잡도를 가짐

 

public int Fibonacci(int n)
{
    if (n <= 1)
        return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

 

 

 

 

- 부분 집합을 출력하는 예시 코드 역시 지수 시간 복잡도를 가짐

 

public static void Main()
    {
        char[] set = { 'a', 'b', 'c' };
        PrintSubsets(set);
    }

    // 주어진 집합의 모든 부분집합을 출력하는 함수
    public static void PrintSubsets(char[] set)
    {
        int n = set.Length;
        int subsetCount = 1 << n; // 2^n

        for (int i = 0; i < subsetCount; i++)
        {
            Console.Write("{ ");
            for (int j = 0; j < n; j++)
            {
                if ((i & (1 << j)) != 0) // i의 j번째 비트가 1이면 set[j]를 포함
                {
                    Console.Write(set[j] + " ");
                }
            }
            Console.WriteLine("}");
        }
    }

 

 

 

 

 

사진 출처 : https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/