공간 복잡도

✔오늘 배운 중요한 🔑 point

• 시간 복잡도가 알고리즘이 실행되는 시간에 따른 효율성을 뜻한다면 공간 복잡도는 알고리즘을 실행시키고 완료까지 사용한 공간의 양을 뜻한다
• 공간 복잡도의 경우 메모리가 부족한 경우에는 상대적으로 저렴한 비용으로 해결이 가능하지만 시간 복잡도의 경우 시스템의 성능이 느려지는 경우에는  비싼 비용이 필요하기 때문에 상대적으로 공간 복잡도 보다는 시간 복잡도의 중요성이 더 크다

🎯 오늘 배운 내용

 

공간 복잡도

프로그램을 실행시키고 완료까지 사용한 공간의 양을 뜻하며 Big-O 표기법을 그대로 사용한다

 

공간 복잡도 평가

고정 공간 요구: 알고리즘이 실행되는 동안에도 항상 필요한 고정된 공간이 있는지 확인 (변수, 상수, 배열 등의 메모리 공간을 할당하는 고정된 요구 )

가변 공간 요구: 알고리즘이 실행되는 동안에 메모리를 동적으로 할당하거나 사용하는 경우 최대 메모리 사용량을 고려

추가적인 자료구조: 알고리즘이 실행되는 동안에 추가적인 자료구조(예: 스택, 큐, 트리 등)를 사용하는 경우에도 이에 따른 메모리 공간을 고려

 

공간 복잡도와 시간 복잡도를 왜 고려해야할까?

 

 

시간 복잡도는 알고리즘을 실행하는 데 필요한 시간, 공간 복잡도는 알고리즘을 실행하는데 필요한 공간을 의미하는데 데이터의 크기가 크거나 제한된 자원을 가진 환경에서는 알고리즘의 실행시간과 사용하는 메모리의 양이 시스템의 성능에 매우 직접적으로 영향을 끼치기 때문에  시스템의 성능을 높이기 위해서는 시간복잡도와 공간복잡도를 최대한 고려해서 알고리즘을 개발해야만 한다.

따라서 백엔드 개발자는 데이터를 어떻게 저장하고 적재하는지, 그 데이터를 어떻게 활용하는지에 따라 시스템의 성능에 큰 영향을 주기 때문에 백엔드 개발자는 시간 복잡도와 공간 복잡도를 최대한 낮춰서 알고리즘을 설계할 필요가 있다.

 

 

공간복잡도 예시

fun main() {
    val arr = intArrayOf(1, 2, 3, 4, 5)
    val sum = arraySum(arr)
    println("배열의 합: $sum")
}

fun arraySum(arr: IntArray): Int {
    var sum = 0 // 합을 저장할 변수
    for (num in arr) {
        sum += num
    }
    return sum 
}

상수 크기의 변수를 저장하는 데에는 고정된 메모리 공간만 사용되기 때문에 공간복잡도는  O(1)


이 함수는 각 요소를 한번씩 접근해서 합을 저장하는데만 변수 sum을 사용하므로 공간 복잡도는 O(1) 이다.

 

 

 

 

 

 

🤔 어떻게 활용할까?

우리가 실제로 작업하는 환경은 무한한 메모리와 무한한 성능의 컴퓨터를 사용하는 것이 아니기 때문에 제한된 환경에서도 활용할 수 있을려 면 시간복잡도와 공간 복잡도를 고려해서 알고리즘을 설계하는것이 중요하다 . 내가 작성한 코드가 시간 복잡도와 공간 복잡도가 어떤지 확인하고 싶을땐 Big O calculator등을 이용해서 현재 나의 시간 복잡도와 공간 복잡도를 확인하여 코드를 복잡도를 더 낮추는 방향으로 설계하는것이 시스템의 성능을 높이는데 도움이 될것이다.

내가 작성한 코드의 시간 복잡도와 공간 복잡도를 한번에 확인 할 수 있다

Big O calculator(https://www.bigocalc.com/) : 시간 복잡도와 공간 복잡도 계산

LeetCode (https://leetcode.com/) : 작성한 코드의 실행시간과 메모리 사용량 측정

 

 

📓 오늘의 한줄

Remember that time is money

- Benjamin Franklin -