시간복잡도, 공간복잡도 (Time complexity, Space complexity)

코딩을 할 때 꼭 알아야 하는 개념인 "시간 복잡도"와 "공간 복잡도"

 

코딩을 하다보면 알고리즘과 데이터 구조를 선택할 때, 코드의 성능과 효율성을 고려해야 하는데 이때 시간 복잡도와 공간 복잡도는 중요한 평가 지표로 사용된다.

 

시간복잡도는 알고리즘이 동작하는 데 걸리는 시간의 양을 나타내는데 알고리즘이 얼마나 빠른지를 측정하는 것으로, 대개 Big O 표기법을 사용한다. (Big O notation)

 

공간복잡도는 알고리즘이 사용하는 메모리 공간의 양을 나타낸다.

알고리즘이 얼마나 많은 메모리를 사용하는지를 측정하는 것으로, 또한 Big O 표기법을 사용하여 표현한다.

 

시간복잡도와 공간복잡도는 알고리즘의 성능을 평가하는 중요한 지표로 사용한다.

 

 

leetcode의 문제를 보면 제약조건에 시간복잡도나 공간복잡도에 제한이 있는 경우가 있다.

 

 

 Two Sum 문제만 보더라도

Follow-up에 O(n^2)보다 속도가 빠른 알고리즘으로 문제를 풀이하도록 유도하고 있다.

 

 

 

그럼 Two Sum 문제로 시간복잡도와 공간복잡도에 대해 설명해보겠다.

 

Link : https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

 

 

Two Sum은 주어진 nums 배열에서 target을 만들 수 있는 두 개의 원소의 index를 반환하는 문제이다.

 

 

1. Brute Force Search - 시간복잡도 O(n^2) , 공간복잡도 O(1)

Brute Force Search란 가능한 모든 경우를 일일이 시도하여 해답을 찾는 방법이다.

간단하고 직관적인 방법이지만 입력의 크기가 크거나 가능한 경우의 수가 많은 경우에는 비효율적이며 시간 제한에 걸리게 된다.

 

- 시간복잡도 : 중첩 반복문을 사용했으므로 O(n^2)가 된다.

- 공간복잡도 : 추가 적인 데이터 구조를 사용하지 않으므로 O(1)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result = vector<int>{};
        int n = size(nums);
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                if(nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return result;
    }
};

 

 

 

 

2. hash map - 시간복잡도 O(n), 공간복잡도O(n)

- 시간복잡도 : nums 배열을 한 번만 순회하므로 O(n)

- 공간복잡도 : map 컨테이너의 추가적인 공간이 nums 벡터의 크기에 비례하므로 O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> m;
        int i = 0;        
        while(i < nums.size()){
            int diff = target - nums[i];            
            if(m.find(diff) != m.end()){
                return{i, m[diff]};
            }
            m[nums[i]] = i;
            i++;
        }        
        return {};
    }
};