시간 복잡도와 공간 복잡도

시간 복잡도

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

 

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

// 시간 복잡도는 O(n)

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

// 시간 복잡도는 O(n^2)

int Fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

// 시간 복잡도는 O(2^n)

 

 

공간 복잡도

 - 코드의 메모리 사용량을 실제 메모리 크기로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장 공간의 양을 측정

 - 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)이라 할 수 있습니다.

public static int[] RemoveDuplicates(int[] array)
{
    List<int> distinctList = new List<int>();

    foreach (int num in array)
    {
        if (!distinctList.Contains(num))
        {
            distinctList.Add(num);
        }
    }

    return distinctList.ToArray();
}

// 시간 복잡도는 O(n)
// 공간 복잡도는 O(n)