C# 5주차 - 시간복잡도와 공간복잡도

시간복잡도

• 시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도입니다.
• 코드의 실행 시간을 실제 시간(초)으로 측정하는 것이 아니라, 입력 크기에 대한 "연산 횟수" 로 측정합니다.
• Big-O 표기법을 사용하여 표시함

예제1

int Sum(int n)
{
    int sum = 0;
    for (int i = 0; i <= n; i++)
    {
        sum += i;
    }
    return sum;
}

위 예제에서 for 루프문이 0부터 n까지 순회하며 합계를 계산합니다.
따라서 n번의 연산이 필요하며 시간복잡도는 O(n)이라고 할 수 있습니다.

예제2

void PrintPairs(int n)
{
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            Console.WriteLine(i + ", " + j);
        }
    }
}

두개의 중첩된 for루프를 포함하고 있습니다. 루프는 0부터 n까지 순회하고 있으므로 n의 제곱 (n^2)이며
시간복잡도는 O(n^2)입니다.

---

공간복잡도

• 코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명합니다.
• Big-O 표기법을 사용하여 표시합니다.

// 시간 복잡도: O(n)
int FindMax(int[] arr)
{
    int max = arr[0];

    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }

    return max;
}

// 시간 복잡도: O(n^2)
int FindMax2(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        bool isMax = true;

        for (int j = 0; j < arr.Length; j++)
        {
            if (arr[j] > arr[i])
            {
                isMax = false;
                break;
            }
        }

        if (isMax)
        {
            return arr[i];
        }
    }

    return -1;
}

int[] arr = new int[] { 1, 2, 3, 4, 5 };

// FindMax 메서드의 시간 복잡도: O(n), 공간 복잡도: O(1)
int max = FindMax(arr);

// 배열의 크기에 비례하여 실행 시간이 증가하므로 O(n)이라 할 수 있습니다. 또한 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다.

// FindMax2 메서드의 시간 복잡도: O(n^2), 공간 복잡도: O(1)
int max2 = FindMax2(arr);

// 이중 반복문을 사용하기 때문에 배열의 크기에 제곱에 비례하여 실행 시간이 증가하므로 O(n^2)이라 할 수 있습니다. 이 알고리즘은 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다.