시간 복잡도 (Time Complexity), 그리고 공간 복잡도 (Space Complexity)

자료 구조와 알고리즘이 뭔지는 다 알고 오셨죠 ?!

 

모르겠다고요 ..??

 

제가 설명 잘 해뒀으니 한 번 보고 오시죠!  (블로그 홍보 😎) 

자료구조, 알고리즘

---

 

본론으로 돌아와서 !

자료 구조와 알고리즘이 뭔지는 이제 알았으니

 

우리는 어떤 알고리즘이

빠르고 효율적인지를 판단할 수 있는 능력을 길러야 합니다.

 

그러기 위해서는

시간 복잡도와 공간 복잡도에 대해 먼저 알아야 해요.

 

---

 

그런데 잠깐 !

 

 

위에 개념을 배우기 전, 한 가지 생각해 봐야 할 것이 있습니다.

우리는 왜 빠르고 효율적인 알고리즘을 찾아야 할까요?

 

그건 바로

우리에게 주어진 자원은 한정되어 있기 때문입니다.

---

예를 들어,

수학 문제를 푼다고 생각해봅시다.

 

누구는 빠르고 효율적인 풀이 방식(공식)으로 단 시간에 문제를 풀 것이고,

 

다른 누군가는 계산 과정 하나 하나를 직접 손으로 세면서 풀고 있어

제한 시간 내에 답을 내지 못할 것입니다.

 

알고리즘 또한 마찬가지입니다.

 

효율적인 알고리즘(풀이 방식)을 이해하고 구현할 수 있다면,

우리는 효율적인 프로그램을 개발할 수 있고, 유지 보수하기 쉬운 코드를 작성할 수 있습니다.

 

알고리즘을 공부하다보면 

문제를 해결하기 위한 논리적인 사고를 배울 수도 있습니다.

 

그러면 이제 알고리즘을 배워야 하는 이유도 알았겠다,

시간 복잡도와 공간 복잡도에 대해서 알아 보러 가시죠 !

 

---

📝 시간 복잡도 (Time Complexity)

 

시간 복잡도는 알고리즘의 실행이 얼마나 오래 걸리는지를 나타내는 표현입니다.

 

다시 말해,

우리는 시간 복잡도를 이용하여 알고리즘의 실행 속도를 나타내는 것이고,

특정 입력에 대해 수행되는 알고리즘의 기본 연산 횟수로 수행 시간을 표현하는 것 입니다.

---

예를 들어, 아래 함수에 대해 생각해봅시다.

// Swift
func printHello() {
    var count = 10
    for _ in 0..<count {
        print("Hello")
    }
}

 

 

 

위에 함수는 정수 count의 값에 따라 Hello를 반복하여 출력하는 함수입니다.

입력 값은 없고, 출력 값은 반복되어 나타나는 print문인 것이죠.

 

다시말해, 

'printHello() 함수는 10번의 print문이 실행되고, 10의 시간복잡도를 갖는다'라고 나타낼 수 있습니다.

(물론 count 변수를 정의하는 것도, 실행과정에 포함이 되지만,

우리가 원하는 출력 값에는 크게 영향을 끼치지 않기 때문에 무시합니다 !)

---

또 다른 함수를 보겠습니다.

 

아래 함수는 몇 번의 기본 연산이 진행될까요?

// Swift
func findMaxValue(numbers: [Int]) -> Int {
    // 배열의 첫 번째 원소를 초기 최대값으로 설정
    var maxValue = numbers[0]

    // 나머지 원소들과 비교하여 최대값 갱신
    for number in numbers {
        if number > maxValue {
            maxValue = number
        }
    }

    return maxValue
}

 

 

해당 함수는 입력으로 받은 정수 배열에서 최대값을 찾아 반환하는 함수입니다.

 

초기 최대값을 배열의 첫 번째 원소로 설정하고,

반복문을 통해 모든 원소를 비교하여 최대값을 갱신합니다.

 

이러한 과정에서 기본적인 대소 비교와 변수 갱신이 주요 연산입니다.



 

그럼, 아까 위에서 봤던 printHello() 함수와는 다른게 무엇일까요?

 

findMaxValue(numbers:) 함수는

어떤 입력값이 들어 올지 알 수 없고, 몇 개의 정수를 갖는 배열이 파라미터로 들어 올지 알 수 없습니다.

 

따라서, 정확한 시간복잡도를 구할 수 없습니다.

---

 

조금 더 자세히 설명해보겠습니다..!

 

예를 들어, findMaxValue(number:)함수에

파라미터로 [1, 2, 3]과 [3, 2, 1]을 전달하여 실행했다고 해봅시다!

 

[1, 2, 3]의 경우,

최대값인 3이 배열의 마지막에 위치하기 때문에 반복문 내에서 if 조건문이 여러 번 실행됩니다. 

따라서 for 문에서 3번의 if문 연산 과정이 발생하게 됩니다.

 

[3, 2, 1]의 경우는,

최대값이 배열의 첫 번째에 위치하므로 if 조건문이 항상 false를 반환하게 됩니다.

따라서 if문 내에서는 어떠한 연산 과정도 실행되지 않습니다.

 

 

이런 경우에

함수는 입력 배열의 특성에 따라 연산 횟수가 달라집니다. 

 

이처럼, 입력에 따라 동적으로 동작하는 함수는 실행 시점에서 연산 횟수를 정확히 예측하기 어렵기 때문에

정확한 시간 복잡도를 구할 수 없다고 표현한 것 입니다.

 

그럼 어떻게 구해야 할까요 ??

---

 

 

우리는 두 가지 방식을 생각해 볼 수 있습니다 !

 

첫 번째로는,

모든 입력에 대해 기본 연산 수를 더해서 평균을 내볼 수 있습니다.

 

두 번째로는,

가장 최악의 경우의 입력(worst-case input)을 가정하여,

최악의 경우의 입력에 대한 알고리즘의 수행 시간을 측정하는 것 입니다.

 

 

가장 이상적인 방식은 첫 번째 방식인, 평균을 내는 방법입니다. 

 

하지만,

예시에서 본 것처럼 모든 입력에 대한 평균은 내는 것은 현실적으로 불가능합니다.

 

따라서, 알고리즘의 성능평가는

대부분 2번인, Worstcase Time Complexity를 이용합니다.

 

제일 오래걸리는 상황을 가정하고 시간 복잡도를 구했으니,

알고리즘이 이것보단 빠르게 실행되겠지?! 하는 생각으로 구하는 것 입니다.

 

 

---

결론적으로 !

시간 복잡도는 알고리즘의 실행속도를 나타내는 개념이며,

이 실행 속도는 가장 오래 걸리는 상황을 가정하고 구하면 되는 것 입니다.

 

따라서, 알고리즘의 성능평가는 대부분 최악의 경우를 가정하고 시간 복잡도를 분석합니다 !!

 

---

그런데, 이쯤되서 드는 생각이...

똑같은 알고리즘이여도 제일 좋은 컴퓨터에서 돌리는 게 제일 빠른 거 아닌가요 ?!

 

(그렇게 생각 안해도... 읽어보세요..!)

---

그럴 줄 알고,

똑똑하신 분들이 이미 가정을 뒀습니다 !

 

바로, 시간 복잡도의 측정은

'가상 컴퓨터'에서 '가상 언어'로 작성된 '가상 코드'를 실행(시뮬레이션)한다.

 

엥??

가상 컴퓨터? 가상 언어? 가상 코드?

그게 뭐죠..? 

 

간단하게 설명하자면 !

 

만약 우리가 성능 측정을 할 때, 

컴퓨터나 코드(C, Pytho, Swift 등) 종류가 매번 바뀐다면

결과 값도 매번 바뀔 수 있기 때문에 정확한 성능을 알 수 없습니다.

 

그렇기 때문에,

자료 구조와 알고리즘의 성능 평가는

가상 컴퓨터 위에서 가상 언어를 이용한 가상 코드를 이용해서 진행이 되는 것 입니다.

(실제가 아닌 가상에서 똑같은 환경에서 비교하고 측정한다.)

 

(나중에 가상 컴퓨터, 가상 언어, 가상 코드에 대해 자세히 게시물로 작성해볼게요. 🤓)

 

---

요정도로

시간 복잡도는 마무리해도 되겠죠..?

---

📝공간 복잡도 (Space Complexity)

 

공간 복잡도는 요즘 시간 복잡도에 비해 중요도가 떨어지고 있습니다.

 

왜냐하면, 요즘 메모리의 발전으로 공간 복잡도에 중요도가 점차 낮아지면서, 

시간 복잡도를 조금 더 중요시 생각하고 있어요.

(but, 데이터를 많이 다루는 빅데이터 분야에서는 여전이 중요해요!)

 

---

 

그래도 간단하게 설명하자면 !

 

눈치가 빠르신 분들은  이미 아시겠지만,

공간 복잡도는 메모리과 관련된 개념입니다!

 

알고리즘의 메모리 사용량이 입력 크기에 대해 어떻게 증가하는지를 분석하는 것 입니다.

 

다시 말해,

알고리즘이 실행될 때 메모리를 얼마나 사용하는냐를 나타내는 것입니다.

---

추가로,

알고리즘을 실행시키기 위해 필요한 공간(Space)를

우리는 두 가지로 나눠 볼 수 있습니다.

 

알고리즘의 실행에 필요한 고정된 크기의 메모리를 나타내는 고정 공간 개념과,

알고리즘 실행에 따라 크기가 변하는 메모리를 나타내는 가변 공간이 있습니다.

 

즉, 고정 공간은 알고리즘과는 무관한 공간을 나타내고,

가변 공간이 알고리즘과 밀접한 공간을 나타내는 것입니다.

 

---

간단하게 쓰고 넘어가려고 했는데..

쓰다보니 욕심이 나서 글이 길어졌네요..

 

---

잘못된 내용이나 궁금하신 점이 있다면 댓글 남겨주세요. 🤓

읽어주셔서 감사합니다.

---

📝 참고 자료

한국외대 신찬수 교수님의 Data Structures with Python 강의

https://velog.io/@welloff_jj/Complexity-and-Big-O-notation

https://babbab2.tistory.com/88

https://www.gklibrarykor.com/1395/